[latexpage]
While I’m at it, I might as well write up the problem that inspired the last post. Here it is:
Flip a coin until you get consecutive heads, then stop. Let X represent the number of flips it took. Then flip another coin until you get three consecutive heads. Let Y represent the total number of flips there. Find Pr(X>Y).
We started this problem in the previous post. There we found that \(Pr(X=k)=F_{k-1}/2^k\) where \(F_k\) is the k-th Fibonacci number. From the homework problem in the last post, we can get that \(Pr(X>k)=F_{k+2}/2^k\). And the distribution of Y is fairly easy to derive along the same lines as X: it turns out to be
\[Pr(Y=k)=\frac{G_{k-2}}{2^k}\]
where \(G_k\) is the k-th Tribonacci number.
So!
\[Pr(X>Y)=\sum_{k=3}^{\infty}Pr(X>k)Pr(Y=k)=\sum_{k=3}^{\infty}\frac{F_{k+2}G_{k-2}}{2^{2k}}\]
which is approximately 0.21. Can anyone find a nice closed form solution of this? There are closed form solutions for the Fibonacci and Tribonacci numbers but they’re complicated. There are also matrix representations, which might help. Any ideas?
July 28, 2012 at 9:11 pm
As I haven’t opened my copy since right after the book came out, I can’t recall if its techniques would be useful here, but at the very least I remember this book as having some similar stuff in it: http://www.math.upenn.edu/~wilf/AeqB.pdf (now free online from the author).
November 11, 2012 at 5:38 pm
Rather than simplify your answer, maybe you can make a fresh start using a net with eight nodes. Think of the coin tosses as being performed simultaneously, until one of these conditions is met: coin 2 wins if it gets to three consecutive heads before, or at the same time as, coin 1 gets to two consecutive heads; and coin 1 wins if it gets to two consecutive heads before coin 2 gets to three consecutive heads. Thus at every stage before the end we are in one of six states (a,b), where a records how many heads have just been thrown consecutively by coin 1, and b records how many heads have just been thrown consecutively by coin 2. A tails resets the number to 0. The possible states are (0,0), (0,1), (0,2), (1,0), (1,1), (1,2). There are also two end states: Coin 1 wins and Coin 2 wins. The nonzero transition probabilities are always 1/4 or 1/2. I think this leads to a system of linear equations in eight indeterminates, which is probably a mess to solve. But I think one can at least infer that the probability you seek is a rational number.