Peeter Joot's (OLD) Blog.

Math, physics, perl, and programming obscurity.

Limit of unfair coin distribution, the hard way

Posted by peeterjoot on February 7, 2013

[Click here for a PDF of this post with nicer formatting]

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).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: