UK
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
50%
Since I discover last week that maximum kudos was not chocolate, I decided that I won’t be participating anymore.
Swiss people don’t work just for glory!
I would still say a 50% probability as I am for the neutrality.
- 1,000,000,000 euros (only if you are Irish, Greek or work in PE)
n / (2n + 1)
e&1/2k+1
n/2n+1
Let’s denote the Probabilty of having an Odd number of Heads with n coins as POH(n). Assuming the coin-tosses are independent, for n > 1 we have
POH(n) = POH(n-1)*(1-H(n)) + (1-POH(n-1))*H(n) (eq.1)
where H(n) is the probability to get a Head on the nth (last) toss, ie H(n) = 1/(2n+1).
We can prove that POH(n) = n/(2n+1) by induction:
1) it is trivially true for n = 1 (when POH(n) = H(n) = 1/3)
2) if you assume it is true for n-1, applying eq.1 proves that it holds for n as well
hence POH(n) = n/(2n+1) is true for all n.
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.
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.
K&2
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
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.