Results 1 to 2 of 2

Thread: Stirling's approximation to estimate n choose m

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    40

    Stirling's approximation to estimate n choose m

    Let $\displaystyle m$ be an integer with $\displaystyle m/m = p + o(1)$ for $\displaystyle 0 < p < 1$. Show $\displaystyle {n\choose{m}} = 2^{n(H+o(1))}$ where $\displaystyle 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 $\displaystyle m$ be an integer with $\displaystyle m/n = p + o(1)$ for $\displaystyle 0 < p < 1$. Show $\displaystyle {n\choose{m}} = 2^{n(H+o(1))}$ where $\displaystyle 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: $\displaystyle \log (n!)=k\log k-k+o(k)$ (log in base e).

    Write $\displaystyle {n\choose m}=\frac{n!}{m!(n-m)!}$, take logarithms, use $\displaystyle m=np+o(n)$ (hence $\displaystyle n-m= n(1-p)+o(n)$) and the above formula. After simplifications, you'll get your formula (i.e. $\displaystyle \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: Jul 20th 2011, 05:19 AM
  2. Replies: 1
    Last Post: Mar 9th 2010, 04:56 AM
  3. Combinatorial estimate using Stirling's formula
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Aug 30th 2009, 04:15 AM
  4. Probability using Stirling's Approximation
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: Aug 11th 2009, 02:13 AM
  5. Replies: 1
    Last Post: Dec 13th 2008, 01:19 PM

Search tags for this page

Search Tags


/mathhelpforum @mathhelpforum