Results 1 to 2 of 2

Math Help - Stirling's approximation to estimate n choose m

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    36

    Stirling's approximation to estimate n choose m

    Let m be an integer with m/m = p + o(1) for 0 < p < 1. Show {n\choose{m}} = 2^{n(H+o(1))} where H = -p \log p - (1-p) \log (1-p) where the logs are to the base 2.

    I've tried using the binomial tail but can't get this to work...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by Boysilver View Post
    Let m be an integer with m/n = p + o(1) for 0 < p < 1. Show {n\choose{m}} = 2^{n(H+o(1))} where H = -p \log p - (1-p) \log (1-p) where the logs are to the base 2.

    I've tried using the binomial tail but can't get this to work...
    This is a consequence of Stirling's approximation formula, in a weaker form: \log (n!)=k\log k-k+o(k) (log in base e).

    Write {n\choose m}=\frac{n!}{m!(n-m)!}, take logarithms, use m=np+o(n) (hence n-m= n(1-p)+o(n)) and the above formula. After simplifications, you'll get your formula (i.e. \frac{1}{\log 2}\log{n\choose m}=n H +o(n))
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Stirling's approximation
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: July 20th 2011, 05:19 AM
  2. Replies: 1
    Last Post: March 9th 2010, 04:56 AM
  3. Combinatorial estimate using Stirling's formula
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 30th 2009, 04:15 AM
  4. Probability using Stirling's Approximation
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: August 11th 2009, 02:13 AM
  5. Replies: 1
    Last Post: December 13th 2008, 01:19 PM

Search Tags


/mathhelpforum @mathhelpforum