# Challenge 12b: Flipping Coins

D H
Staff Emeritus
I'm not sure I understand mathematically why you can claim that R=1 is not the correct solution.
The solution R=1 is not just a mathematical artifact. The expression pRn-R+1-p=0 has either two or zero positive solutions when p>0. Since R=1 is always a solution, this expression must have two positive solutions when p>0. One cannot reject the solution R=1 out-of-hand because this is the correct solution when p<1/n. In the case p<1/n, the other solution to pRn-R+1-p=0 is greater than one, which obviously is incorrect. When p=1/n, the solution R=1 is a double root. When p>1/n, the other solution is between 0 and 1.

Note that in the extreme case of p=1, the two solutions are R=0 and R=1. The R=0 solution is obviously correct in this extreme case. If the coin always comes up heads, the probability of ruin is 0, not 1.

This plus continuity suggests a way around the dilemma: The correct solution is the lesser of the two solutions to pRn-R+1-p=0.

This is consistent with my unwieldy sums. Those sums can be expressed in closed form for small n:
• n=2: ##R=\frac{1-|2p-1|}{2p}##, or
$$R=\begin{cases} 1 & p\le \frac 1 2 \\[4pt] \frac{1-p} p & p > \frac 1 2 \end{cases}$$
• n=3: ##R = \frac{2\sin(\frac 1 3 \sin^{-1}(\frac 3 2 (1-p)\sqrt{3p}))}{\sqrt{3p}}##, or
$$R=\begin{cases} 1 & p\le \frac 1 3 \\[4pt] \frac{\sqrt{(4-3p)p}-p} {2p} & p > \frac 1 3 \end{cases}$$

Staff Emeritus
Gold Member
OK, to make clear what my protest was: The solution R=1 always is a continuous solution that seems like it could be feasible without further analysis; I do not believe that it is clear without further analysis that when n > 1/p that the other root is the solution. Showing through another means that for n=3 that when p is large enough the R=1 root is not the correct answer (and in particular for that value of p plus a larger n R=1 is not correct either through direct comparison), plus continuity of the solution for other values of n does seem good enough for me. I think mfb and you have combined to form a solution there.

From how I read mfb's post however he seemed to be arguing that the derivative of his polynomial could tell us which root was the correct answer, and I don't understand that part.

D H
Staff Emeritus
OK, to make clear what my protest was: The solution R=1 always is a continuous solution that seems like it could be feasible without further analysis; I do not believe that it is clear without further analysis that when n > 1/p that the other root is the solution.
I understand your concern, particularly when it's obvious that the R=1 solution is not just an artifact. It is an essential part of the equation. R=1 is the correct solution in the case pn<1, so rejecting it in the case np>1 is an interesting problem.

The rest of this post describes how I got those multipliers ##\frac 1 {(n-1)k+1} \binom{nk}k## in my unwieldy sums.

Those multipliers result from counting the number of permutations of a sequence of flips that result in losing. Here's a graph of the number of permutations for the case n=2. The nodes in the graph are labeled by the number of permutations. The terminal nodes go nowhere. Each non-terminal node (stack size > 0) goes to two nodes, downward and to the left representing a tails on a coin flip, downward and to the right for a heads.

Code:
      |    stack size
flip# | 0 1 2 3 4 5 6 7 8
--------------------------
0 |   1
|  / \
1 | 1   1
|    / \
2 |   1   1
|  / \ / \
3 | 1   2   1
|    / \ / \
4 |   2   3   1
|  / \ / \ / \
5 | 2   5   4   1
|    / \ / \ / \
6 |   5   9   5   1
|  / \ / \ / \ / \
7 | 5   14  14  6   1
|    / \ / \ / \ / \

The above graph is a bit problematic. There are holes in the graph (e.g., there's no node at flip#=1, stack size=1). Those holes get bigger as n increases. This makes it hard to generate and hard to analyze. It helps to reorganize the tree so that vertical represents the number of heads and horizontal the number of tails. With this, we can delete the edges, and we can delete the terminal nodes. There's an implied vertical edge from an node to the node below, and except for the stack size=1 nodes, there's an implied horizontal edge to the node to the right. Here are the starts of these reoriented graphs for n=2, n=3, and n=4:

Code:
  N=2  |            #tails
#heads |   0   1   2   3   4   5   6   7
----------------------------------------
0 |   1
1 |   1   1
2 |   1   2   2
3 |   1   3   5   5
4 |   1   4   9  14  14
5 |   1   5  14  28  42  42
6 |   1   6  20  48  90 132 132
7 |   1   7  27  75 165 297 429 429

Code:
  N=3  |                   #tails
#heads |   0   1   2   3   4   5   6   7   8   9  10
----------------------------------------------------
0 |   1
1 |   1   1   1
2 |   1   2   3   3   3
3 |   1   3   6   9  12  12  12
4 |   1   4  10  19  31  43  55  55  55
5 |   1   5  15  34  65 108 163 218 273 273 273

Code:
  N=4  |                         #tails
#heads |   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
------------------------------------------------------------------------
0 |   1
1 |   1   1   1   1
2 |   1   2   3   4   4   4   4
3 |   1   3   6  10  14  18  22  22  22  22
4 |   1   4  10  20  34  52  74  96 118 140 140 140 140
5 |   1   5  15  35  69 121 195 291 409 549 689 829 969 969 969 969

The first table (graph), n=2, is Catalan's triangle. The set of numbers comprising the last number in each row of the first table are the Catalan numbers. The other tables and their terminal numbers are extensions of the concept of Catalan's triangle and the Catalan numbers. All tables are generated the same way: Ch,t=Ch-1,t+Ch,t-1, with implied zeros for entries that aren't in the table. The only difference between the tables is the number of entries on each row, with the last entry on a row for t=(n-1)h. It's those terminal numbers (the last entry on a row) that are of concern. These represent the number of paths leading to a stack size of one. The value of that last entry is ##\frac 1 {(n-1)h+1} \binom{nh}h##.