An Extremely Biased Coin - III

Let $X$ be the number of heads obtained after tossing the coin 10000 times. We see that $X$ has a binomial distribution.

Its mean is $\mu = np = 10^{ 4 } \times \frac{ 99 } { 100 } = 9900$ .
Its standard deviation is $\sigma = \sqrt{ n p ( 1 - p ) } = \sqrt{ 10^{ 4 } \times \frac{ 99 } { 100 } \times \frac { 1 } {100 } } = \sqrt { 99 }$ .

Since $np \geq 5$ and $n( 1- p ) \geq 5$ , we can approximate $X$ to be a normal distribution.

The binomial distribution $X \sim B(10000, 0.99 )$ can be approximated to the normal distribution $V \sim N(9900, \sqrt{ 99 } )$ . The probability of getting less than 100 tails is equivalent to getting more than $9900$ heads i.e. $P ( X > 9900)$ . Since we are approximating a binomial distribution to a normal distribution, we will need to use continuity correction. We must calculate $P ( V > 9900.5)$ .

This is a normal distribution, but not a standard one since its mean and sd are not $0$ and $1$ respectively. We need to standardize it so that we can look up values from a standard normal distribution table. We now find the $Z$ -score to standardize the normal distribution.

$Z = \frac{ V - \mu } { \sigma } = \frac{ 9900.5 - 9900 } { \sqrt { 99 } } \approx 0.050$

This means that $P ( V > 9900.5)$ is equivalent to $P ( Z > 0.050 )$ .

Now we find its value. $P ( Z > 0.050 ) = 1 - P( Z < 0.050 )$ . From a standard normal distribution table we see that $P( Z < 0.050 ) \approx 0.5199$ . Therefore $1 - P( Z < 0.050 ) \approx 1 - 0.5199 \approx \boxed{ 0.480 }$ $_\square$

The exact value of the probability can be found by using the binomial theorem. The probability of getting $n$ tails in $10000$ tosses is

$P ( Y = n ) = \binom{ 10000 } { n } \ ( 0.01) ^ { n } \ ( 0.99 ) ^ { 10000 - n }$

The probability of getting less than $100$ tails is

$P ( Y < 100 ) = \sum _ { i = 0 } ^ { 99 } P ( Y = i )$

This is very tedious to calculate by hand, so we usually use an approximation to the find the probability. However WolframAlpha can calculate it easily. The actual probability evaluates to about $0.4865007 \ldots$ Our approximation is pretty good, our approximate probability is within $1.33 \%$ of the actual one.

The first thing to notice here is that the case with the highest probability is 100 tails and 9900 heads. Let's begin by writing a function for calculating the odds of getting $h$ heads and $t$ tails:

$f(h,t)=(.99^h)(.01^t)(10000!/h!/t!)$

Out of curiosity, let's calculate the most-likely result that flipping our biased coin 10,000 times will yield:

$f(9900,100)=(.99^{9900})(.01^{100})(10000!/9900!/100!)=0.0400618...$

(I used WolframAlpha for that...)
We now know the most-likely outcome. But our question doesn't include the case of 100 tails. We need to find all cases where the number of tails are less than 100 and add them together. So let's get started:

$f(9901,99)=(.99^{9901})(.01^{99})(10000!/9901!/99!)=0.0400577595...$

$f(9902,98)=(.99^{9902})(.01^{98})(10000!/9902!/98!)=0.0396491720...$

Ok, this is getting tiresome to even write out. Let's create a function to do this for us:

1
2
3
4
5
6
7
8

var ar=[];
for(var t=99;t>=0;t--)
{
    //starting with the case of 99 tails
    var h=(10000-t);
    ar.push('(.01^'+t+')*(.99^'+h+')*(10000!/'+h+'!/'+t+'!)'+((t%5==0)?'\n':''));
}
console.log(ar.join('+'));

We now have:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

(.01^99)*(.99^9901)*(10000!/9901!/99!)+(.01^98)*(.99^9902)*(10000!/9902!/98!)+(.01^97)*(.99^9903)*(10000!/9903!/97!)+(.01^96)*(.99^9904)*(10000!/9904!/96!)+(.01^95)*(.99^9905)*(10000!/9905!/95!)
+(.01^94)*(.99^9906)*(10000!/9906!/94!)+(.01^93)*(.99^9907)*(10000!/9907!/93!)+(.01^92)*(.99^9908)*(10000!/9908!/92!)+(.01^91)*(.99^9909)*(10000!/9909!/91!)+(.01^90)*(.99^9910)*(10000!/9910!/90!)
+(.01^89)*(.99^9911)*(10000!/9911!/89!)+(.01^88)*(.99^9912)*(10000!/9912!/88!)+(.01^87)*(.99^9913)*(10000!/9913!/87!)+(.01^86)*(.99^9914)*(10000!/9914!/86!)+(.01^85)*(.99^9915)*(10000!/9915!/85!)
+(.01^84)*(.99^9916)*(10000!/9916!/84!)+(.01^83)*(.99^9917)*(10000!/9917!/83!)+(.01^82)*(.99^9918)*(10000!/9918!/82!)+(.01^81)*(.99^9919)*(10000!/9919!/81!)+(.01^80)*(.99^9920)*(10000!/9920!/80!)
+(.01^79)*(.99^9921)*(10000!/9921!/79!)+(.01^78)*(.99^9922)*(10000!/9922!/78!)+(.01^77)*(.99^9923)*(10000!/9923!/77!)+(.01^76)*(.99^9924)*(10000!/9924!/76!)+(.01^75)*(.99^9925)*(10000!/9925!/75!)
+(.01^74)*(.99^9926)*(10000!/9926!/74!)+(.01^73)*(.99^9927)*(10000!/9927!/73!)+(.01^72)*(.99^9928)*(10000!/9928!/72!)+(.01^71)*(.99^9929)*(10000!/9929!/71!)+(.01^70)*(.99^9930)*(10000!/9930!/70!)
+(.01^69)*(.99^9931)*(10000!/9931!/69!)+(.01^68)*(.99^9932)*(10000!/9932!/68!)+(.01^67)*(.99^9933)*(10000!/9933!/67!)+(.01^66)*(.99^9934)*(10000!/9934!/66!)+(.01^65)*(.99^9935)*(10000!/9935!/65!)
+(.01^64)*(.99^9936)*(10000!/9936!/64!)+(.01^63)*(.99^9937)*(10000!/9937!/63!)+(.01^62)*(.99^9938)*(10000!/9938!/62!)+(.01^61)*(.99^9939)*(10000!/9939!/61!)+(.01^60)*(.99^9940)*(10000!/9940!/60!)
+(.01^59)*(.99^9941)*(10000!/9941!/59!)+(.01^58)*(.99^9942)*(10000!/9942!/58!)+(.01^57)*(.99^9943)*(10000!/9943!/57!)+(.01^56)*(.99^9944)*(10000!/9944!/56!)+(.01^55)*(.99^9945)*(10000!/9945!/55!)
+(.01^54)*(.99^9946)*(10000!/9946!/54!)+(.01^53)*(.99^9947)*(10000!/9947!/53!)+(.01^52)*(.99^9948)*(10000!/9948!/52!)+(.01^51)*(.99^9949)*(10000!/9949!/51!)+(.01^50)*(.99^9950)*(10000!/9950!/50!)
+(.01^49)*(.99^9951)*(10000!/9951!/49!)+(.01^48)*(.99^9952)*(10000!/9952!/48!)+(.01^47)*(.99^9953)*(10000!/9953!/47!)+(.01^46)*(.99^9954)*(10000!/9954!/46!)+(.01^45)*(.99^9955)*(10000!/9955!/45!)
+(.01^44)*(.99^9956)*(10000!/9956!/44!)+(.01^43)*(.99^9957)*(10000!/9957!/43!)+(.01^42)*(.99^9958)*(10000!/9958!/42!)+(.01^41)*(.99^9959)*(10000!/9959!/41!)+(.01^40)*(.99^9960)*(10000!/9960!/40!)
+(.01^39)*(.99^9961)*(10000!/9961!/39!)+(.01^38)*(.99^9962)*(10000!/9962!/38!)+(.01^37)*(.99^9963)*(10000!/9963!/37!)+(.01^36)*(.99^9964)*(10000!/9964!/36!)+(.01^35)*(.99^9965)*(10000!/9965!/35!)
+(.01^34)*(.99^9966)*(10000!/9966!/34!)+(.01^33)*(.99^9967)*(10000!/9967!/33!)+(.01^32)*(.99^9968)*(10000!/9968!/32!)+(.01^31)*(.99^9969)*(10000!/9969!/31!)+(.01^30)*(.99^9970)*(10000!/9970!/30!)
+(.01^29)*(.99^9971)*(10000!/9971!/29!)+(.01^28)*(.99^9972)*(10000!/9972!/28!)+(.01^27)*(.99^9973)*(10000!/9973!/27!)+(.01^26)*(.99^9974)*(10000!/9974!/26!)+(.01^25)*(.99^9975)*(10000!/9975!/25!)
+(.01^24)*(.99^9976)*(10000!/9976!/24!)+(.01^23)*(.99^9977)*(10000!/9977!/23!)+(.01^22)*(.99^9978)*(10000!/9978!/22!)+(.01^21)*(.99^9979)*(10000!/9979!/21!)+(.01^20)*(.99^9980)*(10000!/9980!/20!)
+(.01^19)*(.99^9981)*(10000!/9981!/19!)+(.01^18)*(.99^9982)*(10000!/9982!/18!)+(.01^17)*(.99^9983)*(10000!/9983!/17!)+(.01^16)*(.99^9984)*(10000!/9984!/16!)+(.01^15)*(.99^9985)*(10000!/9985!/15!)
+(.01^14)*(.99^9986)*(10000!/9986!/14!)+(.01^13)*(.99^9987)*(10000!/9987!/13!)+(.01^12)*(.99^9988)*(10000!/9988!/12!)+(.01^11)*(.99^9989)*(10000!/9989!/11!)+(.01^10)*(.99^9990)*(10000!/9990!/10!)
+(.01^9)*(.99^9991)*(10000!/9991!/9!)+(.01^8)*(.99^9992)*(10000!/9992!/8!)+(.01^7)*(.99^9993)*(10000!/9993!/7!)+(.01^6)*(.99^9994)*(10000!/9994!/6!)+(.01^5)*(.99^9995)*(10000!/9995!/5!)
+(.01^4)*(.99^9996)*(10000!/9996!/4!)+(.01^3)*(.99^9997)*(10000!/9997!/3!)+(.01^2)*(.99^9998)*(10000!/9998!/2!)+(.01^1)*(.99^9999)*(10000!/9999!/1!)+(.01^0)*(.99^10000)*(10000!/10000!/0!)

Toss it into wolfram alpha one line at a time, due to the input character limit, and write down the results a few digits after the decimal place. You'll notice right around the outcome for 60 tails or less, the probability sinks much lower than the 3 significant figures after the decimal place which this problem requires. So we can stop here and add it up. In my case I wrote down:

1

0.19235427+0.14904499+0.08845506+0.03963003+0.0131879+0.0032006+0.0005548+0.00006

Computing that gave me 0.48648765 which was accurate enough for me to pass the problem without adding further. If not for WolframAlpha, I would have probably written some code for solving it with the GNU Multiple Precision Arithmetic Library which is available to almost every decent programming language out there.