You have n biased coins with the kth coin having probability 1/(2k + 1) of coming up heads. What is the probability of getting an odd number of heads in total? (Thanks to FV.)
I include this as a classic example of the induction method. Use pn to denote the required probability.
After n — 1 tosses there is a probability pn-1 that there have been an odd number of heads. And therefore a probability of 1 — pn— 1 of there having been an even number of heads. To get the probability of an odd number of heads after another toss, n in total, you multiply the probability of an odd number so far by the probability of the next coin being tails and add this to the product of the probability of an even number and the probability of getting a head next:
Now we just have to solve this difference equation, with the starting value that before any tossing we have zero probability of an odd number, so po = 0. If we write pn = an/(2n + 1) then the difference equation for an becomes the very simple
The solution of this with a0 = 0isjustn and so the required probability is
When flipping an unbiased coin, how long do you have to wait on average before you get two heads in a row? And more generally, how long before n heads in a row. (Thanks to MikeM.)
It turns out that you may as well solve the general problem for n in a row. Let Nn be the number of tosses needed to get n heads in the row. It satisfies the recursion relationship
This is because with probability | we get the required head, and with probability we get a tail and will have to start the whole thing anew. Therefore we obtain
This has solution
This means six tosses on average to get two heads in arow.
Balls in a bag
Ten balls are put in a bag based on the result of the tosses of an unbiased coin. If the coin turns up heads, put in a black ball, if tails, put in a white ball. When the bag contains ten balls hand it to someone who hasn't seen the colours selected. Ask them to take out ten balls, one at a time with replacement. If all ten examined balls turn out to be white, what is the probability that all ten balls in the bag are white? (Thanks to mikebell.)
This is a test of your understanding of conditional probability and Bayes' theorem again. First a statement of Bayes' theorem.
Prob(A) is the probability of A, without any information about B, this is unconditional probability. Prob(A|B) means probability of A with the extra information concerning B, this is a conditional probability.
In the balls example, A is the event that all of the balls in the bag are white, B is the event that the balls taken out of the bag are all white. We want to find Prob(A|B).
Clearly, Prot>04) is just W = 0.000976563. Trivially Prob(£|>l) is 1. The probability that we take ten white balls out of the bag is a bit harder. We have to look at the probability of having n white balls in the first place and then picking, after replacement, 10 white. This is then Prob(B). It is calculated as
And so the required probability is 0.000976563/0.01391303 = 0.0701905. Just over 7%.
Sums of uniform random variables
The random variables xi,xi,X3,... are independent and uniformly distributed over 0 to 1. We add up n of them until the sum exceeds 1. What is the expected value of n? (Thanks to balaji.)
There are two steps to finding the solution. First what is the probability of the sum of n such random variables being less than 1. Second, what is the required expectation.
There are several ways to approach the first part. One way is perhaps the most straightforward, simply calculate the probability by integrating unit integrand over the domain in the upper right 'quadrant' between the point (0,0, ... ,0) and the plane X1 + xi + • • • + xn = 1. This is just
After doing several of the inner integrals you will find that the answer is simply ^.
From this it follows that the probability that the sum goes over 1 for the first time on the nth random variable is
The required expectation is the sum of n(n — 1)/n! = 1/(n — 1)! from i to infinity, or equivalently the sum of 1/n!for n zero to infinity. And this is our answer, e.