Last time we saw a number of coin-tossing related interview questions. In this post we look at two types of more advanced coin-related problems:
1) (possibly) unfair coins with odds drawn from a continuous distribution, and
2) games involving trying to obtain a specific sequence of Heads and Tails
1) Coins with odds drawn from a continuous distribution
If we cannot be sure about the odds of the coin, there would be another extra degree of randomness.
CT05
Suppose you have an unfair coin with P(Tail) = p, p is an unknown constant. What is the probability distribution of N, where N is the event: 'The first Head shows up at the N-th toss', and what is the expectation value of N?
CT05 - Answer:
The probability distribution is simply the Geometric Distribution p^(N-1) (1-p).
The expectation value of N is E[N] = 1/(1-p), which can be found by
E[N] = Sum_(i=1)^(inf) i*p^(i-1) (1-p)
Noting that
i*p^(i-1) = (d/dp)p^i
Using this and exchanging the order of summation and differentiation, we get
E[N] = 1/(1-p)
Meanwhile, if the odds of Head itself is drawn from a known distribution, then we can compute the desired expected values with integrals:
CT06
Suppose you have an unfair coin, with probability of a head p ~ uniform(0,1). What is the probability of getting 2 (or n) heads with 2 (or n) tosses?
CT06 - Answer:
If the coin is fair, then P(2 Heads) = 1/4. But now we would have to integrate
\int_0^1 p^n U(0,1) dp = 1/(n+1)
So for 2 tosses P(2 Heads) = 1/3.
Note that while for a fair coin with n tosses, the probabilites of obtaining {1,2,3,...,n} Heads are binomial coefficients, in this case the probabilites of obtaining {1,2,3,...,n} Heads are identical.
2) Games involving trying to obtain a specific sequence of Heads and Tails
This is yet another popular genre of interview questions, possibly because the questions can be varied easily (for example, by modifying the desired sequence of H and T). There are two sub-types: i) what is the probability that sequence A would show up before sequence B does? and ii) what is the probability that sequence A would be obtained during the first/second player's turn? (assuming that the two take turns) The two sub-types are to be solved in different ways. Let's start with the expected number of toss for obtaining a particular sequence.
CT07
Keep flipping a fair coin. What is the expected number of toss such that the sequence HH appears for the first time? What about HT and HHH?
CT07 - Answer:
One can take the most general coute and solve this as a Markov chain problem. For short sequences, especially for repeating sequences (i.e. HH, TT, HHH, etc.), writing down a recursive formula should be faster. Let N(A) be the expected number of toss to obtain the sequence A. Then
N(T) = N(H) = 2
N(HH) = N(H) + 0.5 * 1 + 0.5 * (1 + N(HH)) => N(HH) = 6
The recursive formula can be understood as the two possible outcomes upon obtaining the first H: either another H immediately, in which case the sequence HH is complete, or a T, in which case one has to start over from scratch, hence the N(HH) on the right hand side. It is not hard to prove by induction that, for B = k consecutive H,
N(B) = 2^(k+1) - 2
is a close-form solution. For general sequences, the recursive formula approach still works, though you would have to know the expected number of tosses for the sub-swquences. For instance:
N(HT) = N(H) + 0.5 * 1 + 0.5 * (1 + N(T))
N(HTH) = N(HT) + 0.5 * 1 + 0.5 * (1 + 0.5 * N(HTH))
N(HHT) = N(HH) + 0.5 * 1 + 0.5 * (1 + N(T))
What if we want to know the probability that sequence A would show up before sequence B does? We'll discuss that next time.
See here for more interview questions/brainteasers
No comments:
Post a Comment