The Four Lily Pad Problem

You are a frog in a pond with four lily pads, marked “$1$” through “$4$.” You are currently on pad $2$, and your goal is to make it to pad $1$. From any given pad, there are specific probabilities that you’ll jump to another pad:

• Once on pad $1$, you will happily stay there forever.
• From pad $2$, there’s a $1$-in-$2$ chance you’ll hop to pad $1$, and a $1$-in-$2$ chance you’ll hop to pad $3$.
• From pad $3$, there’s a $1$-in-$3$ chance you’ll hop to pad $2$, and a $2$-in-$3$ chance you’ll hop to pad $4$.
• Once on pad $4$, you will unhappily stay there forever.

Given that you are starting on pad $2$, what is the probability that you will ultimately make it to pad $1$ (as opposed to pad $4$)?

Let's solve this in two different ways: (a) one directly from the probability distributions and some easy combinatorics; and (b) from the Markov chain properties that we will then expand in the Extra Credit portion.

The most straightforward way of solving this is by looking at all of the possible transitions from pad $2$ to pad $1.$ Obviously in the first jump you have a $1/2$ probability of everlasting happiness on pad $1.$ If not, then you will have to make your way back to pad $2$ and try again, at some future point. In order to end up back on pad $2$ we will need a jump to pad $3$ followed by a jump back from pad $3$ to pad $2.$ The probability of this round trip occuring is $\frac{1}{2} \times \frac{1}{3} = \frac{1}{6}.$ So we can only arrive on paradise pad $1$ as the result of an odd numbered jump from pad $2$ to pad $1$, with some number of round trips, say $k$, between pads $2$ and $3$ intervening. So the the probability of landing on lily pad $1$ on the $(2k+1)$th jump is $\frac{1}{2 \cdot 6^k},$ meaning that the total probability of ever landing on lily pad $1$ having started on lily pad $2$ is $$p = \sum_{k=0}^\infty \frac{1}{2 \cdot 6^k} = \frac{1}{2} \frac{1}{1 - \frac{1}{6}} = \frac{3}{5} = 60 \%.$$

Of course another way of looking at the situation is that your location on pads $1,$ $2,$ $3,$ or $4$ can be modeled by a Markov chain with transition matrix given by $$T = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 1/2 & 0 & 1/2 & 0 \\ 0 & 1/3 & 0 & 2/3 \\ 0 & 0 & 0 & 1 \end{pmatrix} ,$$ where $T_{ij}$ is the probability of starting of pad $i$ and going to pad $j$. Obviously, pads $1$ and $4$ are absorbing, recurrent states of this Markov chain, while pads $2$ and $3$ are transient. We can then transform our transition matrix by reordering the states to put it into a canonical block form, so that now the rows and columns represent pads $3,$ $2,$ $1,$ and $4$, respectively: $$\hat{T} = \begin{pmatrix} 0 & 1/3 & 0 & 2/3 \\ 1/2 & 0 & 1/2 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} = \begin{pmatrix} Q & R \\ 0 & I \end{pmatrix}.$$ The fundamental matrix of this Markov chain is $$N = (I - Q)^{-1} = \begin{pmatrix} 1 & -1/3 \\ -1/2 & 1 \end{pmatrix}^{-1} = \begin{pmatrix} \frac{6}{5} & \frac{2}{5} \\ \frac{3}{5} & \frac{6}{5} \end{pmatrix}.$$ The resulting absorption probabilities are given by $$P = NR = \begin{pmatrix} \frac{6}{5} & \frac{2}{5} \\ \frac{3}{5} & \frac{6}{5} \end{pmatrix} \begin{pmatrix} 0 & \frac{2}{3} \\ \frac{1}{2} & 0 \end{pmatrix} = \begin{pmatrix} \frac{1}{5} & \frac{4}{5} \\ \frac{3}{5} & \frac{2}{5} \end{pmatrix}$$ where $P_{ij}$ is the probability of starting on lily pad $4-i$ and ending up at lily pad $\frac{5 + (-1)^j 3}{2}$ for $i, j = 1, 2.$ So in particular, the probability of starting on pad $2$ and ending up living a life of happiness on pad $1$ forever is, again, $P_{21} = 60\%.$

The Infinite Lily Pad Problem

Once again, you are a frog in a pond. But this time, the pond has infinitely many lily pads, which are numbered “1,” “2,” “3,” etc. As before, you are currently on pad $2$, and your goal is to make it to pad $1$, which you would happily stay on forever.

Whenever you are on pad $k$, you will hop to pad $k−1$ with probability $1/k$, and you will hop to pad $k+1$ with probability $(k−1)/k.$ Now, what is the probability that you will ultimately make it to pad $1$?

Taking off where we landed from the Classic Fiddler, let's expand the $4$ lily pad Markov chain to an $n$ state Markov chain and then see what happens when $n \to \infty.$ Skipping right to the canonical form of the transition matrix we get \begin{align*}\hat{T}_n &= \begin{pmatrix} 0 & \frac{1}{n-1} & 0 & 0 & \cdots & 0 & 0 & 0 & 0 & \frac{n-2}{n-1}\\ \frac{n-3}{n-2} & 0 & \frac{1}{n-2} & 0 & \cdots & 0 & 0 & 0 & 0 & 0 \\ 0 & \frac{n-4}{n-3} & 0 & \frac{1}{n-3} & \cdots & 0 & 0 & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \cdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & \frac{2}{3} & 0 & \frac{1}{3} & 0 & 0 \\ 0 & 0 & 0 & 0 & \cdots & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & 0 & 0 & 0 & \cdots & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & \cdots & 0 & 0 & 0 & 0 & 1 \end{pmatrix} \\ &= \begin{pmatrix} Q & R \\ 0 & I \end{pmatrix}.\end{align*} Again, we have the fundamental matrix $N = (I - Q)^{-1}$ and $P = NR,$ where here can focus of wanting $P_{n-2,1}.$ Instead of trying to code up an $(n-2) \times (n-2)$ matrix inversion, let's instead rewrite the matrix equation as a tridiagonal system of equations $$(I-Q) x = \begin{pmatrix} 1 & -\frac{1}{n-1} & 0 & 0 & \cdots & 0 & 0 & 0 \\ -\frac{n-3}{n-2} & 1 & -\frac{1}{n-2} & 0 & \cdots & 0 & 0 & 0 \\ 0 & -\frac{n-4}{n-3} & 1 & -\frac{1}{n-3} & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \cdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & -\frac{2}{3} & 1 & -\frac{1}{3} & \\ 0 & 0 & 0 & 0 & \cdots & 0 & -\frac{1}{2} & 1 \\ \end{pmatrix} x = \frac{1}{2} e_{n-2},$$ and use the Thomas algorithm to find the probability of ending up on pad $1$ forever in the case of $n$ lily pads as $p_{1,n} = x_{n-2} = P_{n-2,1}.$ In particular, the main diagonal entries are $b_i = 1, i = 1, 2, \dots, n-2.$ The upper diagonal is $c_i = -\frac{1}{n-i}, i = 1, 2, \dots, n-3$ and lower diagonal are $a_i = -\frac{n-i-1}{n-i}, i = 2, 3, \dots, n-2.$ The Thomas algorithm consists of two sweeps, first $c^\prime\in \mathbb{R}^{n-3}$ and $d^\prime \in \mathbb{R}^{n-2}$ and then another that starts with solving for $x_{n-2}$ and then sweeps backward from $i = n-1$ to $i=1.$ In particular, we define $c^\prime_1 = c_1 = -\frac{1}{n-1}$ and $$c^\prime_i = \frac{c_i}{1 - a_ic^\prime_{i-1}}, i = 2, \dots, n-3$$ and $d^\prime_1 = d_1,$ and $$d^\prime_i = \frac{d_i - a_id^\prime_{i-1}}{1 - a_ic^\prime_{i-1}}, i = 2, 3, \dots, n-2,$$ and finally $x_{n-2} = d^\prime_{n-2}$ and $$x_i = d^\prime_i - c^\prime_i x_{i+1}, i = n-1, n-2, \dots, 1.$$ Additionally, since $d_i = 0, i = 1, \dots, n-3,$ we have $d^\prime_i = 0, i = 1, \dots, n-3,$ with $$p_{1,n} = P_{n-2,1} = x_{n-2} = d^\prime_{n-2} = \frac{\frac{1}{2}}{1 - \left(-\frac{1}{2}\right) c^\prime_{n-3}} = \frac{1}{2 + c^\prime_{n-3}},$$ and since we only care about $x_{n-2},$ we don't have to do any of the backward sweep.

So we can simply code up one recursive function that sweeps through the $c^\prime_i$ variables for any $i = 1, \dots, n-3,$ for instance the following Python script:

def prob_zero(N):
    c = -1.0 / float(N - 1.)
    for i in range(2, N-2):
        c = (-1.0 / float(N - i)) / (1. - (-1. + 1.0 / float(N - i)) * c)
    return (0.5 / (1 + 0.5 * c))

We can just get the values of the probability of absorption at pad $1$ for many, many values of $n$ and emprically see that as $n$ gets large we get close (fairly quickly to $\lim_{n \to \infty} p_{1,n} = 63.21205588285577....\%,$ which is disturbingly close to $1 - e^{-1}.$ So much so, that if we wanted we could likely call it quits here and claim that the probability of ending up forever on pad $1$ in the inifinite lily pad case is $p_{1,\infty} = 1 - e^{-1}.$

# of Lily Pads	Absorption Prob.
4	60%
5	62.5%
6	63.07692307692307%
7	63.19018404907976%
8	63.20899335717935%
9	63.21167883211679%
10	63.21201448891889%
11	63.21205178374104%
12	63.21205551321910%
13	63.21205585226252%
14	63.21205588051614%
15	63.21205588268949%
16	63.21205588284473%
17	63.21205588285508%
18	63.21205588285572%
19	63.21205588285577%
20	63.21205588285577%

However, perhaps we can do better than just our anecdotal, experimental evidence. Let's start at $$p_{1,n} = \frac{1}{2+c^\prime_{n-3}(n)}.$$ Using the recursive formula, we get $$c^\prime_{n-3}(n) = \frac{c_{n-3}}{1 - a_{n-3} c^\prime_{n-4}(n)} = \frac{-\frac{1}{3}}{1 + \frac{2}{3} c^\prime_{n-4}(n)} = -\frac{1}{3 + 2 c^\prime_{n-4}(n)}.$$ Going a step further we get $$c^\prime_{n-4}(n) = \frac{ -\frac{1}{4} }{1 - \frac{3}{4} c^\prime_{n-5}(n)} = -\frac{1}{4 + 3c^\prime_{n-5}(n)},$$ which plugging back into the previous equation gives $$c^\prime_{n-3}(n) = - \frac{1}{3 + 2 \frac{ -1 }{4 + 3 c^\prime_{n-5}(n)} } = - \frac{4 + 3 c^\prime_{n-5}(n)}{10 + 9 c^\prime_{n-5}(n)}.$$ We see that we can define $c^\prime_{n-3}(n)$ as a rational function of $c^\prime_{n-k}(n),$ for each $k = 4, \dots, n-1.$ In particular, let's say that $$c^\prime_{n-3}(n) = -\frac{ \alpha_k + (\alpha_k - 1) c^\prime_{n-k}(n) }{\beta_k + (\beta_k - 1) c^\prime_{n-k}(n)},$$ where $\alpha_4 = 1$ and $\beta_4 = 3.$ From the recursion formula for $c^\prime$ we get that $$c^\prime_{n-3}(n) = - \frac{\alpha_k + (\alpha_k - 1) \frac{ - 1 }{k + (k-1) c^\prime_{n-k-1}(n)} }{ \beta_k + (\beta_k - 1) \frac{ -1}{ k + (k-1) c^\prime_{n-k-1}(n)}} = -\frac{ k \alpha_k - (\alpha_k - 1) + (k-1) \alpha_k c^\prime_{n-k-1}(n)} { k \beta_k - (\beta_k - 1) + (k-1) \beta_k c^\prime_{n-k-1}(n)},$$ so we can derive the recursion formulae for $\alpha_k$ and $\beta_k$ as \begin{align*}\alpha_{k+1} &= (k-1) \alpha_k + 1 \\ \beta_{k+1} &= (k-1) \beta_k + 1,\end{align*} for all $k \geq 4,$ with initial conditions $\alpha_4 = 1$ and $\beta_4 = 3.$

So, trying to organize the situation a bit, we notice that since $c_1^\prime(n) = -\frac{1}{n-1}$ we would then have to stop the recursion, we get $$c^\prime_{n-3}(n) = - \frac{ \alpha_{n-1} - \frac{\alpha_{n-1} - 1}{n-1} }{ \beta_{n-1} - \frac{\beta_{n-1} - 1}{n-1} } = \frac{ \alpha_{n-1} (n-2) + 1 }{\beta_{n-1} (n-2) + 1},$$ where $\alpha_{n-1}$ and $\beta_{n-1}$ can be read from the recursion formulae above. Plugging this back into the absorption probability, we see that \begin{align*}p_{1,n} &= \frac{1}{2 + c_{n-3}^\prime(n)} \\ &= \frac{1}{2 - \frac{ \alpha_{n-1} (n-2) + 1}{ \beta_{n-1} (n-2) + 1} } \\ & = \frac{ \beta_{n-1} (n-2) + 1 }{ (2 \beta_{n-1} - \alpha_{n-1}) (n-2) + 1 } \\ &= \frac{ \beta_{n-1} + O (n^{-1}) }{ (2 \beta_{n-1} - \alpha_{n-1}) + O(n^{-1}) }.\end{align*} Now, let's turn our attention to the growth of $\alpha_{n-1}$ and $\beta_{n-1}.$

Given the recursion formulae and initial conditions, we can show that in fact $$\alpha_k = \lfloor (e-2) (k-2)! \rfloor$$ and $$\beta_k = \lfloor (e-1) (k-2)! \rfloor$$ for all $k \geq 4.$ Clearly, the initial conditions hold since $\lfloor (e-2) \cdot (4-2)! \rfloor = \lfloor 1.436\dots \rfloor = 1$ and $\lfloor (e-1) \cdot (4-2)! \rfloor = \lfloor 3.436\dots \rfloor = 3.$ Assume that for some $j \geq 4$ that \begin{align*}\alpha_j &= \lfloor (e-2) (j-2)! \rfloor \\ \beta_j &= \lfloor (e-1) (j-2)! \rfloor.\end{align*} From the recursion formula, we get \begin{align*} \alpha_{j+1} &= (j-1) \alpha_j + 1 = (j-1) \lfloor (e-2) (j-2)! \rfloor + 1 \\ \beta_{j+1} &= (j-1) \beta_j + 1 = (j-1) \lfloor (e-1) (j-2)! \rfloor + 1.\end{align*} Now at this point we will rely on the following lemma (that can be proven using an application of the Taylor remainder theorem) that states that for any $\ell = 2, \dots, \infty,$ $$\sum_{k = \ell}^\infty \frac{1}{k!} \lt \frac{1}{(\ell - 1)!}.$$ So using this lemma we see that \begin{align*}\lfloor e (j-1)! \rfloor &= \left\lfloor \sum_{k=0}^{j-1} \frac{(j-1)!}{k!} + (j-1)! \sum_{k=j}^\infty \frac{1}{k!} \right\rfloor \\ &= (j-1)! \sum_{k=0}^{j-1} \frac{1}{k!} \\ &= (j-1)! \sum_{k=0}^{j-2} \frac{1}{k!} + 1 \\ &= (j-1) \left( (j-2)! \sum_{k=0}^{j-2} \frac{1}{k!} \right) + 1 \\ &= (j-1) \lfloor e (j-2)! \rfloor + 1.\end{align*} So plugging back into the recursion formulae above, since $j!$ and $2 \cdot j!$ are always integers for any $j,$ we confirm the induction step, since \begin{align*} \alpha_{j+1} &= (j-1) \lfloor (e-2) (j-2)! \rfloor + 1 = \lfloor (e-2) (j-1) ! \rfloor \\ \beta_{j+1} &= (j-1) \lfloor (e-1) (j-2)! \rfloor + 1 = \lfloor (e-1) (j-1)! \rfloor,\end{align*} thus proving the formulae $$ \alpha_k = \lfloor (e-2) (k-2)! \rfloor, \beta_k = \lfloor (e-1) (k-2)! \rfloor, \,\, \forall k \geq 4.$$

Finally, returning our attention to the formula for the absorption probability we get \begin{align*}p_{1,n} &= \frac{ \beta_{n-1} + O (n^{-1}) }{ (2 \beta_{n-1} - \alpha_{n-1}) + O(n^{-1})}\\ &= \frac{ \lfloor (e-1) (n-2)! \rfloor + O(n^{-1}) }{ ( 2 \lfloor (e-1) (n-2)! \rfloor - \lfloor (e-2) (n-2)! \rfloor + O(n^{-1}) } \\ &= \frac{ (n-2)! \sum_{k=1}^{n-2} \frac{1}{k!} + O(n^{-1}) }{ (n-2)! \left( 2 \sum_{k=1}^{n-2} \frac{1}{k!} - \sum_{k=2}^{n-2} \frac{1}{k!} \right) + O(n^{-1})} \\ &= \frac{ \sum_{k=1}^{n-2} \frac{1}{k!} + O\left( \frac{1}{ (n-1)!}\right) }{ \left(2 \sum_{k=1}^{n-2} \frac{1}{k!} - \sum_{k=1}^{n-2} \frac{1}{k!} \right) + O \left(\frac{1}{(n-1)!}\right)},\end{align*} so we have that the probability of ending up on pad $1$ in the infinite lily pad problem is \begin{align*}p_{1,\infty} = \lim_{n \to \infty} p_{1,n} &= \lim_{n\to \infty} \frac{ \sum_{k=1}^{n-2} \frac{1}{k!} + O\left( \frac{1}{ (n-1)!}\right)}{ \left(2 \sum_{k=1}^{n-2} \frac{1}{k!} - \sum_{k=1}^{n-2} \frac{1}{k!} \right) + O\left( \frac{1}{ (n-1)!}\right)}\\ &= \frac{\sum_{k=1}^\infty \frac{1}{k!}}{ 2 \sum_{k=1}^\infty \frac{1}{k!} - \sum_{k=2}^\infty \frac{1}{k!}} \\ &= \frac{e-1}{2(e-1) - (e-2)} = 1 - e^{-1},\end{align*} as experimentally derived.

Big Trapezoidal Bean Machine

Suppose you have the board below, which starts with a row with six pins (and five slots), followed by a row with five pins (and six slots), and then back to six pins in an alternating pattern. Balls are only allowed to enter through the middle three slots on top.

Your goal is to create a trapezoidal distribution along one of the rows with six slots, which have been highlighted with dotted lines in the diagram above. More precisely, the frequency of balls passing through the six slots from left to right should be $x−y, x, x+y, x+y, x, x−y,$ for some values of $x$ and $y$ with $x \geq y.$

Suppose the ratio by which you drop balls into the top three middle slots, from left to right, is $a : b : c,$ with $a + b + c = 1.$ Find all ordered triples $(a, b, c)$ that result in a trapezoidal distribution in at least one row with six slots.

As opposed to the classic bean machine, let's go back to assuming that beans have an equal probability of going either to the left or the right. In this case, given that we want to end up with a symmetric probability distribution, we can reasonably deduce that $a = c.$ In this case, we then can reduce the dimensionality by also recognizing that $a + b + c = 2a + b = 1,$ that is, $b = 1 -2a.$

Let's define $\pi_i^{(k)}$ as the probability of a bean passing through $i$th slot from the left on the $k$th dotted line row from the top. We can set up a recurrence formula by going through the various routes from one row to the next. In particular, we get \begin{align*} \pi^{(k+1)}_1 &= \frac{1}{2} \pi_1^{(k)} +\frac{1}{4} \pi_2^{(k)}\\ \pi^{(k+1)}_2 &= \frac{1}{2} \pi_1^{(k)} +\frac{1}{2} \pi_2^{(k)} +\frac{1}{4} \pi_3^{(k)}\\ \pi^{(k+1)}_3 &= \frac{1}{4} \pi_2^{(k)} +\frac{1}{2} \pi_3^{(k)} +\frac{1}{4} \pi_4^{(k)}\\ \pi^{(k+1)}_4 &= \frac{1}{4} \pi_3^{(k)} +\frac{1}{2} \pi_4^{(k)} +\frac{1}{4} \pi_5^{(k)}\\ \pi^{(k+1)}_5 &= \frac{1}{4} \pi_4^{(k)} +\frac{1}{2} \pi_5^{(k)} +\frac{1}{2} \pi_6^{(k)}\\ \pi^{(k+1)}_6 &= \frac{1}{4} \pi_5^{(k)} +\frac{1}{2} \pi_6^{(k)} \end{align*} If we have a trapezoidal distribution with $\pi^{(k)}_2 = x,$ then since $\sum_{i=1}^6 \pi^{(k)}_i = 6x = 1,$ it must mean that we have $\pi^{(k)}_2 = \frac{1}{6}.$

For the first dotted line, given ordered triples of $(a, 1-2a, a),$ we have $$\pi^{(1)} = \left(0, \frac{a}{2}, \frac{1-a}{2}, \frac{1-a}{2}, \frac{a}{2}, 0\right).$$ Solving $\pi_2^{(1)} = \frac{a}{2} = \frac{1}{6},$ we get the ordered triple $(\frac{1}{3}, \frac{1}{3}, \frac{1}{3}).$ For the second dotted line, we have $$\pi^{(2)} = \left( \frac{a}{8}, \frac{a+1}{8}, \frac{3-2a}{8}, \frac{3-2a}{8}, \frac{a+1}{8}, \frac{a}{8} \right).$$ Here again, solving $\pi^{(2)}_2 = \frac{a+1}{8} = \frac{1}{6},$ we get the ordered triple $(\frac{1}{3}, \frac{1}{3}, \frac{1}{3}).$ For the third dotted line, we have $$\pi^{(3)} = \left( \frac{3a+1}{32}, \frac{2a+5}{32}, \frac{10-5a}{32}, \frac{10-5a}{32}, \frac{2a+5}{32}, \frac{3a+1}{32} \right).$$ Solving $\pi^{(3)}_2 = \frac{2a+5}{32} = \frac{1}{6},$ we get the ordered triple $(\frac{1}{6}, \frac{2}{3}, \frac{1}{6}).$

Going further, we get $$\pi^{(4)} = \left(\frac{8a+7}{128}, \frac{5a+22}{128}, \frac{35-13a}{128}, \frac{35-13a}{128}, \frac{5a+22}{128}, \frac{8a+7}{128}\right).$$ Here though, we come to the equation $\frac{5a+22}{128} = \frac{1}{6},$ which cannot be solved by an $a \geq 0,$ since $\frac{22}{128} \gt \frac{1}{6}.$ So there are no ordered triples that can provide a trapezoidal distribution on the fourth dotted line. Similarly, we get $$\pi^{(5)} = \left( \frac{21a+36}{512}, \frac{13a+93}{512}, \frac{127-34a}{512}, \frac{127-34a}{512}, \frac{13a+93}{512}, \frac{21a+36}{512}\right),$$ where $\frac{93}{512} \gt \frac{1}{6}$ so again no ordered triple can provide a trapezoidal distribution on the fifth dotted line. Finally, we have $$\pi^{(6)} = \left( \frac{55a+165}{2048}, \frac{34a+385}{2048}, \frac{474-89a}{2048}, \frac{474-89a}{2048}, \frac{34a+385}{2048}, \frac{55a+165}{2048}\right),$$ where $\frac{385}{2048} \gt \frac{1}{6}$ so again no ordered triple can provide a trapezoidal distribution on the sixth dotted line.

Therefore, the only possible ordered triples that result in a trapezoidal distribution are $(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$ and $(\frac{1}{6}, \frac{2}{3}, \frac{1}{6}).$

Big Skewed Bean Machine

Suppose you have a board like the one shown below. The board’s topmost row has three pins (and two slots for a ball to pass through), while the bottommost row has two pins (and three slots for a ball to pass through). The remaining rows alternate between having three pins and two pins. But instead of the $12$ rows of pins in the illustrative diagram, suppose the board has many, many rows. And at the very bottom of the board, just below the two bottommost pins, are three buckets, labeled $A,$ $B,$ and $C$ from left to right.

Whenever a ball encounters one of the leftmost pins, it travels down the right side of it to the next row. And whenever a ball encounters one of the rightmost pins, it travels down the left side of it to the next row. But this isn’t your garden variety bean machine. Whenever a ball encounters any of the other pins, it has a $75$ percent chance of traveling down the right side of that pin, and a $25$ percent chance of traveling down the left side of that pin.

A single ball is about to be dropped into the left slot at the top of the board. What is the probability that the ball ultimately lands in bucket $A,$ the leftmost slot at the bottom?

Let's break down the many, many, many rows of this bean machine into repetitions of a two pin row followed by a three pin row. Let's zoom in on one of these blocks. Assume that the probability that bean will hit the left pin with probability $p$ (and hence the probability it hits the right pin is $1-p$). Let's further say that the probability that after it passes through the three pin row that it is leaving down the left slot is $q = q(p).$ Let's work out the relationship between $p$ and $q.$

As shown in the figure, there are three possible ways that it leaves down the left slot: (a) it hits the left pin in the upper row, goes to the left hitting the leftmost pin in the lower row, then leaves through down the left slot; (b) it hits the left pin in the upper row, goes to the right hitting the middle pin in the lower row, then goes to the left leaving through the left slot; or (c) it hits the right pin in the upper row, goes to the left hitting the middle pin in the lower row, then goes to the left, leaving through the left slot. The total probability of option (a) is $p \cdot \frac{1}{4} \cdot 1 = \frac{p}{4}$. The total probability of option (b) is $p \cdot \frac{3}{4} \cdot \frac{1}{4} = \frac{3p}{16}$. The total probability of option (c) is $(1-p) \cdot \frac{1}{4} \cdot \frac{1}{4} = \frac{1-p}{16}.$ Therefore, we see that $$q = q(p) = \frac{p}{4} + \frac{3p}{16} + \frac{1 - p}{16} = \frac{6p + 1}{16}.$$

Let's say that the probability of hitting the left pin in the $n$th repitition of these blocks of consecutive two and three pin rows is $p_n.$ Then, since the probability of leaving the $n$th block through the left slot is the same as the probability of hitting the left pin in the $(n+1)$th block, we have $$p_{n+1} = \frac{6p_n + 1}{16}.$$ If we have a total of $N$ of these blocks, then the probability of ending up in $A$ is given by $p_A = \frac{p_{N+1}}{4}.$ While it isn't entirely super impactful when $N$ is large, we should note that since we are dropping a ball in the left slot that we start with $p_0 = 1,$ from which we can derive the exact probability of getting ending up in $A$ for any $N.$

For this particular problem, though, where we assume that $N \gg 1$ we can just take $p_\infty = \lim_{n \to \infty} p_n$ which we can get by plugging $p_\infty$ into both sides of the recursion formula, that is, $$p_\infty = \frac{6 p_\infty + 1}{16},$$ or equivalently $p_\infty = \frac{1}{10}.$ Therefore, when the number of such blocks grows large, the probability of ending up in $A$ is $$p_A = \frac{p_\infty}{4} = \frac{1}{40} = 2.5\%.$$

The Squiddler, Extra Credit

There are $N$ contestants about to play Mingle, where $N$ is less than $500$. This time, in each round, the number for group size can be anywhere from $1$ to $10$, with each number equally likely to be called. Also, the numbers called in the rounds are all independent of each other. It appears this version of Mingle will continue until there are no more survivors.

Before the game starts, one of the contestants, Young-il, does some quick computation. He says to his companion, Gi-hun: “Oh no, it’s too bad we only have $N$ people.” (Of course, Young-il doesn’t actually say “$N$,” but rather the number that $N$ represents.)

Young-il continues: “If we had started with $N+1$ people instead, I’d expect the game to last about $10$ additional rounds, on average, than I’d expect from starting with $N$ people.”

What is the value of $N$?

In the extra-credit version of Mingle, we again assume that the contestants are all genial, cooperative mathematicians, and there will me no nefarious and/or inadvertent issues with people not being able to form the appropriate groups. In this version, it is even easier to believe this, since rather than unceremonious death, let's say that all contestants in Extra Credit Mingle get paid proportionally for the number of rounds lasted, so that everyone is incentivized for someone to last to the next round.

The extra credit wrinkle of only ever needing to make groups of size $1$ to $10$ introduces some very weird behavior. For instance, if we ever had $N = 2520 = \textsf{lcm} \{ 1, 2, \dots, 10 \}$ then the game will go on for an infinite number of rounds, since no matter what number is called, the contestants will be able to make appropriately round groups. Thus, while there is a nonzero expectation for the number of rounds in the Extra Credit Mingle for $N \lt 2520,$ for any $N \geq 2520$ the expected number of rounds is infinite.

Anyway, let's set up the conditional expectation chain. Let's say that for some $N,$ we know that $E_N$ is the expected number of rounds when starting with $N$ contestants. From the law of total probability, assuming that we know $E_k$ for all $k = 1, \dots, N,$ we can set up the following recursive formula: $$E_N = 1 + \sum_{i=1}^{10} \mathbb{P} \{ i \} E_{ i \lfloor N / i \rfloor } = 1 + \frac{1}{10} \sum_{i=1}^{10} E_{i \lfloor N / i \rfloor}, \,\, \text{for $N \lt 2520$}.$$ (Note, and last one, sorry, but I just think it's kinda neat ... that we see here in the case of $N=2520$ that since $i\lfloor N / i\rfloor = N$ for each $i = 1, \dots, 10,$ that we get the nonsensical $E_{2520} = 1 + E_{2520}.$)

Now there are a few ways to think about this. We can turn the recursion formula into a giant system of linear equations and then solve the $500 \times 500$ lower $10$-diagonal matrix inverse to solve the values of $E_N,$ $N = 1, \dots, 500.$ Instead, I opted for setting up a memoized recursive function in a few lines of Python:

from math import floor
exp_num_rounds = {}
def compute_exp_num_rounds(N):
    if N == 0: return 0
    if N not in exp_num_rounds.keys():
        transitions = []
        for i in range(10):
            transitions.append( int((i+1) * floor( N / ( i+ 1.0) )) )
        others = sum([ compute_exp_num_rounds(t) for t in transitions if t < N ])
        self = sum([ 1 for t in transitions if t == N])
        exp_num = (1.0 + 0.1 * others)/(1.0 - 0.1 * self)
        exp_num_rounds[N] = exp_num
    return exp_num_rounds[N]

Using this function I quickly calculated $E_N$ for $N = 1, \dots, 500,$ and in fact for all $N$ up to $2519.$ We find what looks from a distance as a relatively straight line with a few barely discernable jumps. If we plot the differences $E_{N+1} - E_N$ versus $N$ we see that there are only $9$ total values of the $N$ in $\{1, \dots, 2519\}$ such that the number of expected rounds would be more than $9$ more if they started with $N+1.$ Conveniently, enough, since there is only one such value of below $500$, we know that Young-il is upset that they are starting the round of Extra Credit Mingle with $N=359$ contestants.

Looking at the values with large jump sizes, we can start to build a theoretical argument for why these values exhibit this behavior. Note that in each of these cases, $$N \in \{ 359, 719, 839, 1079, 1259, 1439, 1679, 1799, 2159\}$$ that we have $i \not\mid N$ for each $i = 2, 3, \dots, 10$ while there is only one value of $j \in \{ 2, 3, \dots, 10 \}$ for which $j \not\mid N+1.$ In a sufficiently handwavy way, this relative $9:1$ ratio in probability of dropping below $N$ after round one, is what is driving the roughly $9$ to $10$ additional expected rounds.

The Squiddler

N.B. - Shout-out to colleague and fellow Fiddler enthusiast, Rohit Jawle, for the punny post name this week.

In Season 2 of Squid Game, contestants play a game of “Mingle” (spoiler alert!). For each round of this game, the contestants all wait in a common area until a number is called. They must then split up into groups of that number. Any contestants not in a group of the correct number after $30$ seconds … well, let’s just say bad things happen to them. For now, we’ll refer to contestants who make it through a round in a group of the correct size as having “survived” the round.

Suppose there are initially $N$ contestants. In the first round, contestants must form groups of 1. Okay, that’s not too hard; everyone survives. In the second round, contestants must form groups of $2.$ This continues (with groups of $k$ in round $k$) until the $38$th round, when contestants must form groups of $38.$ What is the smallest number $N$ such that there is at least one person who survives all $38$ rounds?

Let's firstly assume that the contestants are all genial, cooperative mathematicians, and there will me no nefarious and/or inadvertent issues with people not being able to form the appropriate groups of the appropriate sizes. This might not totally make sense in Squid Game context where the penalty for being the odd person out is so draconian as death, but perhaps everyone agreed on an inherent numbering ahead of time, and if your number just doesn't come up in one round or another, these astute and honorable mathematicians at least march to their demise knowing that they played the game optimally. Whatever that's worth.

Anyway ... Let's say that at the end of round $k$ there are $N_k$ contestants remaining. Since any stragglers who are not neatly aligned in a group of $k+1$ at the end of $30$ seconds will be eliminated at the end of round $k+1$, then we see that we must have $$N_{k+1} = (k+1) \left\lfloor \frac{N_k}{k+1} \right\rfloor,$$ where we start with let's say $N_0 = N$ contestants. In theory, we could start at the beginning and guess numbers, work $38$ times through this recursion formula and then see if we end up with anyone remaining after $38$ rounds. Then once we found some starting $N$ that works, for instance, starting $N=2025$ leaves $1634$ lucky remaining contestants after $38$ rounds, you can whittle that down to final a minimal number. Of course, we could also work backwards from the condition that we want to have $N_{38} \gt 0.$

In particular, since we need $N_{38} \gt 0$ and $N_{38} \in 38 \mathbb{Z},$ the minimal number we can have is $N_{38} = 38.$ From the recursion formula, we see that $$38 \left\lfloor \frac{N_{37}}{38} \right\rfloor = 38,$$ which implies that we are looking for $N_{37} \in \{ 38, 39, \dots, 75 \}.$ Since we must also have $N_{37} \in 37 \mathbb{Z},$ we get the minimal value of $N_{37} = 74.$ In turn, we see that $N_{37} = 74$ implies that we must have $N_{36} \in \{ 74, 75, \dots, 110 \} \cap 36 \mathbb{Z},$ that is $N_{36} = 108.$ We can follow all of these nested implications back up to the minimal number of contestants needed to have some number of survivors in each of the 38 rounds to be $N = N_1 = N_2 \geq 454$ contestants. For completeness, if we were to start with $N = 454$ contestants, then the sequence of contestants remaining after $k$ rounds would be as follows:

Round #	Contestants Remaining
0	454
1	454
2	454
3	453
4	452
5	450
6	450
7	448
8	448
9	441
10	440
11	440
12	432
13	429
14	420
15	420
16	416
17	408
18	396
19	380
20	380
21	378
22	374
23	368
24	360
25	350
26	338
27	324
28	308
29	290
30	270
31	248
32	224
33	198
34	170
35	140
36	108
37	74
38	38

Ruffles have maximally aligned ridges

Two large planar sheets have parallel semicircular cylindrical ridges with radius $1.$ Neighboring ridges are separated by a distance $L \geq 2$. The sheets are placed so that the ridges extrude toward each other, and so that the sheets cannot shift relative to each other in the horizontal direction, as shown in the cross-section below:

Which value of $L$ maximizes the empty space between the sheets?

Firstly, let's establish some parameters in order to make sure we can turn this into a nice(r) optimization problem. Let $h$ be the vertical distance between the two planar sheets for a given value of $L \geq 2$. Let's assume that one cylindrical ridge on the lower sheet is centered at the origin, that is, $x = 0.$ By construction, the next cyliindrical ridge on the lower sheet (to the right) is centered at $x = L$ and the center of the semicircular cylindrical ridges on the upper sheet that is tangent to these two lower ridges should be centered at $x = \frac{L}{2}.$ Adding in the vertical axis, we have semicircles of radius $1$ centered at $(0,0)$, $(L, 0)$ and $(\frac{L}{2}, h).$

Let's next determine the objective function for optimization, in terms of $h$ and $L$. That is, we are trying to determine the maximal value of the cross-sectional area of empty space per unit length of one sheet. That is, we have $f(h, L) = \frac{A(h,L)}{L},$ where $A(h,L)$ is the cross-sectional area of the empty space bounded by the rectangle $0 \leq x \leq L$ and $0 \leq y \leq h.$ Now, the non-empty space in this rectangle is half of the unit semicircle centered at (0,0), the entire unit semicircle centered at (L/2, h) and half of the unit semicricle centered at (L, 0), so we need to subtract out the total non-empty area of $\pi,$ that is, $A(h,L) = hL - \pi,$ so we arrive at $$f(h, L) = \frac{A(h, L)}{L} = \frac{hL - \pi}{L} = h - \frac{\pi}{L}.$$

Now, let's determine the height $h$ as a function of $L,$ that is, $h = h(L).$ Since there is no ability to shift the sheets horizontally, it must be that the semicircle centered at $(\frac{L}{2}, h(L))$ is tangent to both of the lower semicircles. Thus, we can draw a straight line from $(0,0)$ to $(\frac{L}{2}, h(L))$ which must have length $2$, since each of the semicircles have unit radii, thus we have the Pythagorean theorem $$2^2 = \left(\frac{L}{2}\right)^2 + h(L)^2,$$ or equivalently $$h(L) = \frac{1}{2} \sqrt{16 - L^2}.$$ In actuality, we should be careful to make sure that the space between the sheets is at least the unit radius of the semicircular ridges, that is, $$h(L) = \max \left\{ 1, \frac{1}{2} \sqrt{16 - L^2} \right\}.$$ However, we can disregard the case where $L \gt 2\sqrt{3}$ where $h(L) = 1 \gt \frac{1}{2} \sqrt{16-L^2}$, since otherwise, barring some extreme static friction, we could horizontally shift the sheets relative to one another which is a no-no of the setup.

Having decided to ignore the other case, we have $h(L) = \frac{1}{2} \sqrt{16-L^2}$ for all $2 \leq L \leq 2\sqrt{3},$ so we now have $$f(L) = f(h(L), L) = \frac{1}{2} \sqrt{16 - L^2} - \frac{\pi}{L}.$$ Taking derivatives, we $$f^\prime(L) = \frac{-L}{2 \sqrt{16-L^2}} + \frac{\pi}{L^2},$$ which if we set equal to zero and solve for $L$ results in the sextic polynomial $$L^6 - 4\pi^2 L^2 + 64 \pi^2 = 0.$$ If we set $\ell = L^2,$ then the condition for optimality becomes a depressed cubic in $\ell$ with a single real zero, that can be handled by Cardano's formula, that is, $$\ell = \sqrt[3]{ 32 \pi^2 + \sqrt{ 1024 \pi^4 + \frac{64}{27} \pi^6} } + \sqrt[3]{ 32\pi^2 - \sqrt{1024 \pi^4 + \frac{64}{27} \pi^6}} \approx 7.06550552638\dots$$ Therefore, the optimal spacing of the ridges is $$L^* = \sqrt{\ell} \approx 2.65810186531\dots.$$