FRIDAY'S KILLER QUESTION: You have some biased coins...

26 November 2010

2 minute read

FRIDAY'S KILLER QUESTION: You have some biased coins...

Every Friday we'll be posting challenging and cryptic questions for you to answer, provided for us by 7city Learning. Post your answers in the comments box at the bottom of the page. Maximum kudos will be provided to the person who provides the correct answer first. We'll add the correct answer to the bottom of this article on Monday afternoon.

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?

ANSWER:

Use Pn to denote the required probability. After n-1 tosses there is a probability of Pn-1 that there have been an odd number of heads. Therefore a probability of 1-Pn-1 of there having been an even number of heads. To get the probability of an even 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:

This becomes

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

then the difference equation for 'an' becomes the very simple

The solution of this with ao=0 is just n and so the required probability is

AUTHOR7cityLearning

Insider Comment

Ma
Madhatter
27 November 2010
And there I was thinking the City was about building trust and relationships to do good business over time. You want maths geeks, you get meltdown. Recent history proves it. Keep them in the back room to check numbers. Don't let them anywhere near clients.
Reply
Go
GoodQuestion
27 November 2010
True. If you conveniently know the answer already...
Solving your original recurrence equation for POH(n) from first principals is less trivial. But there is a general solution (see wikipedia) which if you follow through will give the right answer
good question this week.
Reply
Gi
GianMario
27 November 2010
K&2
Reply
Ni
Niv
27 November 2010
Let OH(n) = {odd numbers of heads counted from first n coins}
EH(n) = {even numbers of heads counted from first n coins}
H(n) = {nth coin lands on heads}
T(n) = {nth coin lands on tails}
Then
P[OH(n)] = P[OH(n) n EH(n-1)] + P[OH(n) n OH(n-1)]
= P[H(n) n EH(n-1)] + P[T(n) n OH(n-1)]
= P[H(n)]*P[EH(n-1)] + P[T(n)]*P[OH(n-1)]
= P[H(n)]*{1 - P[OH(n-1)]} + {1 - P[H(n)]}*P[OH(n-1)]
= P[H(n)] + {1 - 2P[H(n)]}*P[OH(n-1)]
This is the key recursive relation
P[OH(n)] = P[H(n)] + {1 - 2P[H(n)]}*P[OH(n-1)] (a)
The idea here is that for large n, P[OH(n)] converges to some fraction f on [0, 1], in which case P[OH(n-1)] becomes approximately equal to P[OH(n)]. Putting this into (a) gives lim P[OH(n)] = 1/2. Subtracting this limit from both sides of (a) gives
P[OH(n)] - 1/2 = {1 - 2P[H(n)]}*P[OH(n-1)] - 1/2 + P[H(n)]
= {1 - 2P[H(n)]}*{P[OH(n-1)] - 1/2}
=> P[OH(n)] - 1/2 = [(2n-1)/(2n+1)]*{P[OH(n-1)] - 1/2}
sinc
Reply
Ni
Niv
27 November 2010
Continuing from the relation
P[OH(n)] - 1/2 = [(2n-1)/(2n+1)]*{P[OH(n-1)] - 1/2} (b)
we can build up a relation from n = 2
P[OH(2)] - 1/2 = [3/5]*{P[OH(1)] - 1/2}
P[OH(3)] - 1/2 = [5/7]*{P[OH(2)] - 1/2}
= [3/7]*{P[OH(1)] - 1/2};
P[OH(4)] - 1/2 = [3/9]*{P[OH(1)] - 1/2}
and so on, so that
P[OH(n)] - 1/2 = [3/(2n+1)]*{P[OH(1)] - 1/2}
=> P[OH(n)] = 1/2 + [3/(2n+1)]*{1/3 - 1/2}; P[OH(1)] = 1/(2*1 + 1) = 1/3
= 1/2{1 - [1/(2n+1)]}
= 1/2[2n/(2n+1)]
= n/(2n + 1)
havoc's solution is brief and better, especially if you already know what the answer is.
Reply