Peeter Joot's (OLD) Blog.

• 324,651

Limit of unfair coin distribution, the hard way

Posted by peeterjoot on February 7, 2013

We calculated the distribution for the sum of random variables associated with $N$ unfair coin tosses, where the probabilities were $r$, and $s = 1 - r$ for heads and tails respectively. Assigning heads and tails values of $-1$ and $+1$ respectively, the probability distribution of the sum $X$ of the total numbers of heads and tails values for $N$ such tosses was found to be

\begin{aligned}P_N(r, k) = \binom{N}{k} r^{N-k} s^k,\end{aligned} \hspace{\stretch{1}}(1.0.1a)

\begin{aligned}k = \frac{N + X}{2}\end{aligned} \hspace{\stretch{1}}(1.0.1b)

Part of the problem was to calculate the limit for $N \gg 1$ and $N \gg X$. I did this with the central limit theorem, but we were apparently not allowed to do it that way. Here’s a bash at it the hard way, using Stirling’s approximation and Taylor series expansion for the logs.

Application of Stirling’s approximation gives us

\begin{aligned}P_N(r, k) &\approx \frac{ \sqrt{2 \pi N} \not{{e^{-N}}} N^N }{\sqrt{2 \pi (N - k)} \not{{e^{-N + k}}} (N - k)^{N-k}\sqrt{2 \pi k} \not{{e^{-k}}} k^{k}}r^{N-k} s^k \\ &= \sqrt{\frac{N}{2 \pi k(N-k)}}N^{N\underbrace{-k + k}_{\text{Add and subtract}}}\left( \frac{r}{N-k} \right)^{N-k} \left( \frac{s}{k} \right)^k \\ &= \sqrt{\frac{N}{2 \pi k(N-k)}}\left( \frac{N r}{N-k} \right)^{N-k} \left( \frac{N s}{k} \right)^k\end{aligned} \hspace{\stretch{1}}(1.0.2)

The $N r/(N-k)$ term looks like it can probably be coersed into $1/(1 - y/N)$ form that will allow for Taylor expansion of the log. With that change of variables, we find

\begin{aligned}k = N(1 - r) - y r = N s + y r\end{aligned} \hspace{\stretch{1}}(1.0.3)

so

\begin{aligned}\frac{k}{Ns} = 1 + \frac{y r}{N s}\end{aligned} \hspace{\stretch{1}}(1.0.4a)

\begin{aligned}\frac{N - k}{N r} = 1 - \frac{y}{N}\end{aligned} \hspace{\stretch{1}}(1.0.4b)

This is a bit unsymmetrical, so let’s write $y r = x$ so that

\begin{aligned}\frac{N - k}{N r} = 1 - \frac{x}{N r}\end{aligned} \hspace{\stretch{1}}(1.0.5a)

\begin{aligned}\frac{k}{Ns} = 1 + \frac{x}{N s}\end{aligned} \hspace{\stretch{1}}(1.0.5b)

We’ve also got terms in $k$ and $N - k$ above that we need to express. With $k = N s + x$, we have $N - k = N r - x$, and

\begin{aligned}\frac{(N - k) k}{N} &= \frac{1}{{N}}(N r - x)(N s + x) \\ &= \frac{1}{{N}}( -x^2 + N^2 r s + x N(r - s) ) \\ &= -\frac{x^2}{N} + N r s + x( 2 r - 1 ) \\ &\approx N r s\end{aligned} \hspace{\stretch{1}}(1.0.6)

Taking logs of 1.0.2 we have

\begin{aligned}\ln P_N(r, k) &\approx \ln \sqrt{\frac{1}{2 \pi N r s}}- (N r - x)\ln \left( 1 - \frac{x}{N r} \right)- (N s + x)\ln \left( 1 + \frac{x}{N s} \right) \\ &\approx\ln \sqrt{\frac{1}{2 \pi N r s}}+ (x - N r)\left( - \frac{x}{N r} - \frac{1}{{2}} \left( \frac{x}{N r} \right)^2 \right)- (x + N s)\left( \frac{x}{N s} - \frac{1}{{2}} \left( \frac{x}{N s} \right)^2 \right) \\ &= \ln \sqrt{\frac{1}{2 \pi N r s}}+ \frac{1}{{2}} \frac{x^2}{N}\left( \frac{1}{{r}} + \frac{1}{{s}} \right)- \frac{x^2}{N}\left( \frac{1}{{r}} + \frac{1}{{s}} \right)+ \frac{x^3}{(N)^2}\left( \frac{1}{{r^2}} - \frac{1}{{s^2}} \right)\end{aligned} \hspace{\stretch{1}}(1.0.7)

Dropping the $O(1/N^2)$ term and noting that

\begin{aligned}-\frac{1}{{2}} \left( \frac{1}{{r}} + \frac{1}{{s}} \right)=-\frac{1}{{2 r s}} (r + (1 - r)=-\frac{1}{{2 r s}}\end{aligned} \hspace{\stretch{1}}(1.0.8)

We have

\begin{aligned}P_N(r, k) \approx\frac{1}{{\sqrt{2 \pi N r s}}} \exp\left( -\frac{x^2}{2 N r s} \right).\end{aligned} \hspace{\stretch{1}}(1.0.9)

With

\begin{aligned}x &= k - N s \\ &= \frac{1}{{2}} ( N + X ) - N s \\ &= \frac{1}{{2}} ( N + X - 2 N s ) \\ &= \frac{1}{{2}} ( X + N ( 1 - 2 s) ) \\ &= \frac{1}{{2}} ( X - N ( 1 - 2 r) ),\end{aligned} \hspace{\stretch{1}}(1.0.10)

we have

\begin{aligned}\boxed{P_N(r, k) \approx\frac{1}{{\sqrt{2 \pi N r s}}} \exp\left( -\frac{ \left( X - N (1 - 2r) \right)^2 }{8 N r s} \right). }\end{aligned} \hspace{\stretch{1}}(1.0.11)

This recovers the result obtained with the central limit theorem (after that result was adjusted to account for parity).