Coin Problems

Question

Are there patterns A and B of heads and tails such A is longer than B, yet A appears before B more than half the time when a fair coin is being flipped? The textbook has already found one: A=TTHH and B=HHH, in exercise 8.59. The question is:

(1) are there other solutions?

(2) is there a generalized way to produce these solutions?

(3) prove or disprove: the length of A is just 1 more than that of B.

Answer

One Generalized Solution

Of course there are other solutions to this question, here is one of the generalized ways to produce these solutions:

$A=TTHH\cdots HH_{n-1}$，$B=HH\cdots HH_n$

Sequence B consists of n H’s, while sequence A consists of two T’s and n-1 H’s where n is greater than two.

Prove the Solution

We can notate the probation of sequence A and B appears as $S_a$ and $S_b$, while the probation of other sequence which can’t be identified as A or B as $N$.

Then, we can get equations as follows:

$$1+N(H+T)=N+S_a+S_b\\ NB=S_b+\sum_{i=1}^{n-1}(S_a+S_b)H^i \\NA=S_a$$

Obviously, $H=T=\frac{1}{2}$ when we consider a fair coin is being flipped. Finally, we can get $S_b=\frac{1+2^{n-1}}{2^{2n+1}-2^{n+1}}N$ and $S_a=\frac{1}{2^{n+1}}N$.

When n is greater than 2, $S_a$ is greater than $S_b$, which means A appears before B more than half the time.

Take A=TTHH and B=HHH as example, we find $S_{TTHH}=\frac{1}{16}N$ and $S_{HHH}=\frac{5}{112}N$ which check the result mentioned above.

Prove the Length Relation between A and B

As we have found one generalized way to produce sequence A and B where the length of A is just 1 more than that of B, we just need to disprove the existence of solution where the length of A is 2 or greater more than that of B.

To expand the solution proposed above, we modify the equations first:

$$1+N(H+T)=N+S_a+S_b\\ S_b\geq NB-\sum_{i=1}^{n-1}(S_a+S_b)(H|T)^i\geq \frac{1}{2}NB-\frac{1}{2}\sum_{i=1}^{n-1}S_a(H|T)^i \\NA\geq S_a$$

The first one is the same as before. The second one is limited to find the minimum of $S_b$. And the last one limits the maximum of $S_a$.

When the length of A is $k$ more tan that of B, we notate $|A|=k+n,|B|=n$. Then we find

$$S_a\leq \frac{1}{2^{n+k}}N\\ S_b\geq \frac{1}{2^{n+1}}N-S_a(\frac{1}{2}-\frac{1}{2^{n}})\\\geq \frac{1}{2^{n+1}}N-\frac{1}{2^{n+k}}N(\frac{1}{2}-\frac{1}{2^{n}})\\=(\frac{1}{2^{n+1}}+\frac{1}{2^{2n+k}}-\frac{1}{2^{n+k}})N$$

Obviously, $S_b-S_a\geq N\frac{1+2^{n+k-1}-2^{n+1}}{2^{2n+k}}=\frac{N}{2^{2n+k}}(1+2^{n+1}(2^{k-2}-1))$ which means $S_b>S_a$ when $k$ is euqal to or greater than 2.

As a result, we have proved the length of A is just 1 more than that of B.