Expected path length in a ladder-like graph if edges can be randomly removed.

Question

Question from an old exam:

The King of Squares sets out to patrol the City of Squares. The City of Squares is an infinite ladder, i.e., a graph $(V, E)$ where $V = \mathbb{N} \times \{0,1\}$ and the vertex $(x, y)$ is connected to $(x-1, y)$ for $x>0,(x+1, y)$ and $(x, 1-y)$. Unfortunately, due to the revolt, some parts of the streets are blocked. Each edge independently becomes blocked with probability $\frac{1}{2}$. The king leaves his palace at the point $(0,0)$. Let $X$ be the largest value of the coordinate $x$ that the King can reach without passing through the blocked streets.
The king can look ahead, so he will choose the best route before he sets off.
In the situation in the image below $X=5$.

(a) Find EX.
(b) Find the probability that both points $(X, 0)$ and $(X, 1)$ are reachable.

My attempt at (a):
Let $$ X_i = \begin{cases} i, & \text{if it's possible to reach $(i, 0)$ or $(i,1)$} \\ 0, & \text{otherwise}. \end{cases} $$ Now we need to find the probability $p(i)$ that it is possible to reach the point $(i, 0)$ or $(i,1)$.

I have calculated that $p(i) = \frac{5}{8} p(i-1)$, where $p(1) = \frac{5}{8}$.
This is derived from the idea that the probability of going from coordinate$ (x, 0)$, to $(x+1, 0)$ or $(x+1, 1)$ is $\frac{5}{8}$.

Then $E[X]=\sum_{i=1}^{\infty}E[X_i]=\sum_{i=1}^{\infty}i\cdot(\frac{5}{8})^i = \frac{40}{9} \approx 4.44$.

Is this correct? How to do (b), because I don't know where to start?

Answer 1

Let $X$ denote the furthest horizontal coordinate that the king can visit.

The pmf of $X$ is given by

$$\color{blue}{\mathbb P(X=n)=\frac{1}{2^{3n+4}}\left [\left(3 + \sqrt{5} \right)^{n+1} + \left(3 - \sqrt{5} \right)^{n+1}\right]}$$

for $n=0,1,2,\dots \, $.

This gives the expectation

$$\color{blue}{\mathbb E(X)=\frac{9}{5}}.$$

How to obtain the probabilities

Here, we present two methods. The second is easier, but the first provides deeper analysis as it allows us to solve other problems imposing other conditions on a reachable point (e.g., analyzing part b in the OP for any fixed number of steps).

First method:

The probability is computed by counting subgraphs of a ladder graph with $n$ layers in which there is a path from (0,1) to only $(n,0)$, there is a path from (0,1) to only $(n,1)$, and there are paths from (0,1) to both $(n,0)$, $(n,1)$; denoted by $f_0(n)$, $f_1(n)$, and $f_{01}(n)$, respectively.

The following recurrences are used to determine $f_0(n)$, $f_1(n)$, and $f_{01}(n)$:

$$f_0(n)=2f_0(n-1)+f_{01}(n-1)$$ $$f_1(n)=2f_1(n-1)+f_{01}(n-1)$$ $$f_{01}(n)=4f_{01}(n-1)+2f_0(n-1)+2f_1(n-1)$$

with $f_0(0)=0, f_1(0)=1, f_{01}(0)=1$.

This gives

$$\color{blue}{\mathbb P(X=n)=\frac{f_0(n)+f_1(n)}{2^{3n+1}}\times \frac{1}{2}+\frac{f_{01}(n)}{2^{3n+1}}\times \frac{1}{4}}=\frac{1}{2^{3n+1}}\left [ \frac{1}{2}\left ( \frac{ (3 + \sqrt{5})^n (5 + \sqrt{5})- (3 - \sqrt{5})^n (-5 + \sqrt{5}) }{10} \right ) + \\ \frac{1}{4}\left( \left(3 + \sqrt{5} \right)^n \left (\frac{1}{2} + \frac{3}{2\sqrt{5}} \right)+ \left (3 - \sqrt{5} \right )^n \left (\frac{1}{2} - \frac{3}{2\sqrt{5}} \right) \right ) \right]=\frac{1}{2^{3n+4}}\left [\left(3 + \sqrt{5} \right)^{n+1} + \left(3 - \sqrt{5} \right)^{n+1}\right]$$

Second method:

Alternatively, the probability can be obtained based on the number of subgraphs of a ladder graph with $n+1$ layers in which there is a path from (0,1) to one of $(n,0)$ or $(n,1)$, but there is no path to any of $(n+1,0)$ and $(n+1,1)$, which satisfies the following recurrence:

$$g(n)=6g(n-1)-4g(n-2)$$

with $g(0)=6, g(1)=28$. In this case, we have

$$\color{blue}{P(X=n)=\frac{g(n)}{2^{3(n+1)+1}}}$$

where

$$g(n)=\left(3 + \sqrt{5} \right)^{n+1} + \left(3 - \sqrt{5} \right)^{n+1}.$$

How to derive the recurrences

Here I explain how I derived the first recurrence in the first method. The other recurrences in the first or second methods can be obtained similarly.

To see how the first recurrence $f_0(n)=2f_0(n-1)+f_{01}(n-1)$ is derived, see the figure below:

$\hskip 2.2 in$

This shows how different subgraphs of a ladder graph with $n$ layers in which there is a path from $(0,1)$ to only $(n,0)$ (referred to as $0$ type in the sequel) can be generated from all subgraphs of a ladder graph with $n-1$ layers in which there is a path from $(0,1)$ to $(n-1,0)$ or $(n-1,1)$.

1. You can see that we can generate $\color{blue}{\text{no subgraph}}$ of $0$ type from a subgraph of a ladder graph with $n-1$ layers in which there is a path from $(0,1)$ to only $(n-1,1)$ (note that we can only change the lower, upper, and right edges in the $n$th cell).

2. Based on each subgraph of a ladder graph with $n-1$ layers in which there is a path from $(0,1)$ to only $(n-1,0)$, we can construct $\color{blue}{\text{two subgraphs}}$ of $0$ type by adding either the lower edge or both lower and upper edges.

3. Based on each subgraph of a ladder graph with $n-1$ layers in which there are paths from $(0,1)$ to both $(n-1,0)$ and $(n-1,1)$, we can construct only $\color{blue}{\text{one subgraph}}$ of $0$ type by adding the lower edge. Note that adding both lower and upper edges results in a subgraph in which there are paths from $(0,1)$ to both $(n,0)$ and $(n,1)$, while here we want there is a path to only $(n,0)$.

The above observations together yield the following recurrence:

$$f_0(n)=2f_0(n-1)+f_{01}(n-1).$$

As I assumed the start point is $(0,1)$, as shown in the OP's figure, $f_0(0)=0$; note that this assumption does affect the final answer because of the symmetry.

How to solve the recurrences

The single recurrence appearing in the second method can be solved easily.

Let me explain how to solve the system of recurrences appearing in the first method:

$$f_0(n)=2f_0(n-1)+f_{01}(n-1)$$ $$f_1(n)=2f_1(n-1)+f_{01}(n-1)$$ $$f_{01}(n)=4f_{01}(n-1)+2f_0(n-1)+2f_1(n-1)$$

with $f_0(0)=0, f_1(0)=1, f_{01}(0)=1$.

Let us define $s(n)=f_0(n)+f_1(n)$, and sum the first two recurrences to get

$$s(n)=2s(n-1)+2f_{01}(n-1).$$

and rewrite the third for $n$ and $n+1$ as follows:

$$f_{01}(n)=4f_{01}(n-1)+2s(n-1)$$ $$f_{01}(n+1)=4f_{01}(n)+2s(n).$$

Now multiply both sides of the above equations by $-1$ and $\frac{1}{2}$, respectively, sum the resulting equations, and use $s(n)-2s(n-1)=2f_{01}(n-1)$ to get the following second-order recurrence for $f_{01}$:

$$f_{01}(n+1)=6f_{01}(n)-4f_{01}(n)$$

with $f_{01}(0)=1$ and $f_{01}(1)=6$. This yields:

$$f_{01}(n)=\left(3 + \sqrt{5} \right)^n \left (\frac{1}{2} + \frac{3}{2\sqrt{5}} \right)+ \left (3 - \sqrt{5} \right )^n \left (\frac{1}{2} - \frac{3}{2\sqrt{5}} \right).$$

This enables us to get $s(n)$ from $s(n)=2s(n-1)+2f_{01}(n-1)$ with $s(0)=0+1=1$, as follows:

$$s(n)=\frac{ (3 + \sqrt{5})^n (5 + \sqrt{5})- (3 - \sqrt{5})^n (-5 + \sqrt{5}) }{10}.$$

Note that from $f_0(n)=2f_0(n-1)+f_{01}(n-1)$ and $f_1(n)=2f_1(n-1)+f_{01}(n-1)$, both functions $f_0(n)$ and $f_0(n)$ can be found similarly, but deriving $s(n)$ is enough for the first method.

Note that the probability requested in the part b of the OP is given by

$$\sum_{n=0}^{\infty}\frac{f_{01}(n)}{2^{3n+1}}\times \frac{1}{4}=\color{blue}{\frac{2}{5}}.$$

The probabilities of other events can be obtained based on $f_0(n)$, $f_1(n)$, $s(n)$, and $f_{01}(n).$

Major update: $ \color{red}{\text{Quick and elementary solution method:}}$

Inspired from my first method, we can design a quick and elementary solution method that directly computes the expectation and the probability in part b, without the need of having the pmf or counting all the cases.

Let us define the following three related problems and solve them simultaneously:

$\text{Problem}_0$: The king starts from $(0,0)$

$\text{Problem}_1$: The king starts from $(0,1)$ (the same as in the OP)

$\text{Problem}_{01}$: The king can start from any of $(0,0)$ and $(0,1)$

Let $E_0$, $E_0$, and $E_{01}$ denote the expectation of furthest horizontal coordinate in the above problems, respectively. Then, by conditioning on the 8 combined situations of the lower, upper, and left edges of the first cell of the ladder graph, the following relations can be obtained:

$$E_0=\frac{3}{8}(1+E_0)+\frac{1}{8}(1+E_{1})+\frac{1}{8}(1+E_{01})$$ $$E_1=\frac{1}{8}(1+E_0)+\frac{3}{8}(1+E_{1})+\frac{1}{8}(1+E_{01})$$ $$E_{01}=\frac{2}{8}(1+E_0)+\frac{2}{8}(1+E_{1})+\frac{2}{8}(1+E_{01}).$$

To better understand the method, consider 8 cases for the left, lower, and upper edges of the first cell. For example, consider the case that the left and upper edges are removed and the lower only exists (happen with probability of 1/8). By conditioning $E_0$ on this case (one of the three cases considered in the first term in the first row of the three dimensional system), the expected increment is 1 + $E_0$. For another example, consider the case that the lower edge is removed, and both upper and left exist (happen with probability of 1/8). By conditioning $E_0$ on this case (the only case considered in the second term in the first row of the three dimensional system), the expected increment is 1 + $E_1$. As the third example, consider the case that both left and lower edges are removed and only the upper exists (happen with probability of 1/8). By conditioning $E_0$ on this case, the increment is $0$.

Now by solving the above system, we simultaneously obtain all the three expectations: $$\color{blue}{E_0=E_1=\frac{9}{5}, E_{01}=\frac{11}{5}}.$$

The same can be done to get the probability in part b. Similarly, define $P_0$, $P_0$, and $P_{01}$ as the probability that the king needs to stop at some coordinate $i$ while he has paths to both $(i,0)$ and $(i,1)$. Then, by solving the following system:

$$P_0=\frac{1}{8}\times 1+\frac{3}{8}P_0+\frac{1}{8}P_{1}+\frac{1}{8}P_{01}$$ $$P_1=\frac{1}{8}\times 1+\frac{1}{8}P_0+\frac{3}{8}P_{1}+\frac{1}{8}P_{01}$$ $$P_{01}=\frac{2}{8}\times 1 +\frac{2}{8}P_0+\frac{2}{8}P_{1}+\frac{2}{8}P_{01},$$

we obtain the probability in part b for each of the three problems as follows:

$$\color{blue}{P_0=P_1=\frac{2}{5}, P_{01}=\frac{3}{5}}.$$

For the problem in the OP, $E_0$ and $E_1$ or $P_0$ and $P_1$ are the same because of the symmetry. However, I kept both $E_0$ and $E_1$ so that the readers simply see how the method can be adjusted for the asymmetric case where the removal probabilities of the lower and upper edges are not equal.

Answer 2

For each nonegative integer $x$ and each $Y\subset\{0,1\}$ let the event $R_{x,Y}$ be: for each $y\in \{0,1\}$ we have $y\in Y$ iff there exists an abscissa-nondecreasing path from $(0,0)$ to $(x,y)$. Then $p(R_{0,\varnothing})=0$, $p(R_{0,\{0\}})=\frac 12$, $p(R_{0,\{1\}})=0$, and $p(R_{0,\{0,1\}})=\frac 12$. Moreover, it is easy to see that for each natural $x\ge 0$ we have: $$p(R_{x+1,\varnothing})=p(R_{x,\varnothing})+\frac 12 p(R_{x,\{0\}})+\frac 12 p(R_{x,\{1\}})+ \frac 14 p(R_{x,\{0,1\}}),$$ $$p(R_{x+1,\{0\}})=0p(R_{x,\varnothing})+\frac 14 p(R_{x,\{0\}})+0 p(R_{x,\{1\}})+ \frac 18 p(R_{x,\{0,1\}}),$$ $$p(R_{x+1,\{1\}})=0p(R_{x,\varnothing})+0p(R_{x,\{0\}})+\frac 14 p(R_{x,\{1\}})+ \frac 18 p(R_{x,\{0,1\}}),$$ $$p(R_{x+1,\{0,1\}})=0p(R_{x,\varnothing})+\frac 14 p(R_{x,\{0\}})+\frac 14 p(R_{x,\{1\}})+ \frac 12 p(R_{x,\{0,1\}}).$$

Put $p_x=(p(R_{0,\varnothing}),p(R_{x,\{0\}}),p(R_{x,\{1\}}),p(R_{x,\{0,1\}}))^t.$ Then $p_0=\left(0,\frac 12,0,\frac 12\right)^t$, and for each nonnegative integer $x$ we have $p_{x+1}=Ap_x$, where $$A= \begin{pmatrix} 1 & \frac 12 & \frac 12 & \frac 14 \\ 0 & \frac 14 & 0 & \frac 18 \\ 0 & 0 & \frac 14 & \frac 18 \\ 0 & \frac 14 & \frac 14 & \frac 12 \end{pmatrix}.$$

That is, $p_x=A^xp_0$. Let $$T= \begin{pmatrix} 1 & 0 & -3-\sqrt{5} & 3-\sqrt{5} \\ 0 & 1 & 1 & -1 \\ 0 & -1 & 1 & -1 \\ 0 & 0 & 1+\sqrt{5} & -1+\sqrt{5} \end{pmatrix}$$ be the matrix whose columns are the eigenvectors of the matrix $A$. Then $D=T^{-1}AT= \operatorname{diag}\left(1,\frac 14,\frac{3+\sqrt{5}}{8},\frac{3-\sqrt{5}}{8} \right)$ is the diagonal matrix of the eigenvalues of the matrix $A$. Thus $p_x=TD^xT^{-1}p_0$.

(b) The required event happens iff $R_{X,\{0,1\}}$ and both horizontal edges from the $X$-th column of the graph to the $X+1$ column are blocked. That is, the required probability is $\frac 14 p(R_{X,\{0,1\}})$, which is $\frac 14$ multiplied by the last component of the vector $TD^XT^{-1}p_0$, that is $$\frac 1{10\cdot 8^{X+1}}\left(\left(5+3\sqrt{5}\right)\cdot \left(3+\sqrt{5}\right)^X+ \left(5-3\sqrt{5}\right)\cdot\left(3-\sqrt{5}\right)^X\right).$$

(a) For each nonegative integer $x$ we have $X\ge x$ iff not $R_{x,\varnothing}$. It follows $$EX=\sum_{x=1}^\infty xP(X=x)=\sum_{x=1}^\infty x(P(X\ge x)-P(X\ge x+1))=$$ $$\sum_{x=1}^\infty x(p(R_{x+1,\varnothing}))-p(R_{x,\varnothing}))=\lim_{z\to\infty} z p(R_{z+1,\varnothing})-\sum_{x=1}^z p(R_{x,\varnothing}).$$

The expression under the limit is the first component of the vector $(zA^{z+1}-\sum_{x=1}^z A^x)p_0$, that is of the vector $T(zD^{z+1}-\sum_{x=1}^z D^x)T^{-1}p_0$. Let $\xi$ be any real number such that $|\xi|<1$. Let the positive integer $z$ tends to the infinity. We have $z\xi^{z+1}-\sum_{x=1}^z \xi^x= z\xi^{z+1}-\xi\frac{1-\xi^z}{1-\xi}$, and the latter expression tends to $\frac{-\xi}{1-\xi}$. Therefore the matrix $zD^{z+1}-\sum_{x=1}^z D^x$ converges to a diagonal matrix $$D'=\operatorname{diag}\left(1,-\frac 13,\frac{-5-2\sqrt{5}}{5},\frac{-10-\sqrt{5}}{10}\right).$$ Then the first component of the vector $TD'T^{-1}p_0$ equals $$\frac {46+5\sqrt{5}}{20}.$$

Answer 3

Notations:

• $U_n$ the event that the upper horizontal edge is not blocked at $n$.
• $L_n$ the event that the lower vertical edge is not blocked at $n$.
• $V_n$ the event that the vertical edge is not blocked at $n$.
• $N = \inf\left\{ n \in \mathbb N_{\ge 1}\, : \, L_n \cap U_n \cap V_n^c\; \text{is false}\right\}$, $N$ follows a geometric distribution $\mathcal G\left(p = \frac78\right)$

Question a:

Idea:

The idea is to establish a system of equations such that $\mathbb E\left[X\mid V_0\right]$ and $\mathbb E\left[X \mid V_0^c\right]$ are solutions of the system.

Recursion:

• In the case of $V_0^c$, \begin{array}{|c|c|c|} \hline \textbf{Event} & \textbf{Probability} & \textbf{Expectation}\\ \hline L_1^c & \frac12 & 0\\ \hline L_1 \cap V_1^c & \frac14 & 1 + \mathbb E\left[X \mid V_0^c\right]\\ \hline L_1 \cap V_1 & \frac14 & 1 + \mathbb E\left[X \mid V_0\right]\\ \hline \end{array}

• In the case of $V_0$, \begin{array}{|c|c|c|} \hline \textbf{Event} & \textbf{Probability} & \mathbb E\left[X\mid N\right]\\ \hline L_N\cap U_N\cap V_N^c & 0 & \\ \hline L_N^c\cap U_N^c & \frac27 & N - 1\\ \hline L_N \cap U_N^c \cap V_N^c & \frac17 & N + \mathbb E\left[X \mid V_0^c\right]\\ \hline L_N^c \cap U_N \cap V_N^c & \frac17 & N + \mathbb E\left[X \mid V_0^c\right]\\ \hline \left(L_N \cup U_N\right) \cap V_N & \frac37 & N + \mathbb E\left[X \mid V_0\right]\\ \hline \end{array}

Formulas:

\begin{align} \mathbb E\left[X \mid V_0^c\right] &= \frac14 \left(1 + \mathbb E\left[X\mid V_0\right]\right) + \frac14 \left(1 + \mathbb E\left[X \mid V_0^{c}\right]\right)\\ &= \frac12 + \frac14 \mathbb E\left[X \mid V_0\right] + \frac14 \mathbb E\left[X \mid V_0^c\right] \end{align}

and

\begin{align} \mathbb E\left[X\mid V_0\right] &= \mathbb E\left[\mathbb E\left[X \mid N\right] \mid V_0\right]\\ &= \mathbb E\left[N\right] - \frac27 + \frac27 \mathbb E\left[X\mid V_0^c\right] + \frac37\mathbb E\left[X\mid V_0\right]\\ &= \frac87 - \frac27 + \frac27 \mathbb E\left[X\mid V_0^c\right] + \frac37\mathbb E\left[X\mid V_0\right]\\ &= \frac67 + \frac27 \mathbb E\left[X\mid V_0^c\right] + \frac37\mathbb E\left[X\mid V_0\right] \end{align}

You can solve this system and evaluate: $$\mathbb E\left[X\right] = \frac12\left(\mathbb E\left[X\mid V_0\right] + \mathbb E\left[X\mid V_0^c\right]\right) = \frac95.$$

---

Question b:

A similar way can be done for the probability of the second question. Indeed if $A$ is the event that the $0$ and $1$ are reachable at $X$ you will have:

Recursion

• In the case of $V_0^c$, \begin{array}{|c|c|c|} \hline \textbf{Event} & \textbf{Probability} & \mathbb P\left[A\right]\\ \hline L_1^c & \frac12 & 0\\ \hline L_1 \cap V_1^c & \frac14 & \mathbb P\left[A \mid V_0^c\right]\\ \hline L_1 \cap V_1 & \frac14 & \mathbb P\left[A \mid V_0\right]\\ \hline \end{array}

• In the case of $V_0$, \begin{array}{|c|c|c|} \hline \textbf{Event} & \textbf{Probability} & \mathbb P\left[A\mid N\right]\\ \hline L_N\cap U_N\cap V_N^c & 0 & \\ \hline L_N^c\cap U_N^c & \frac27 & 1\\ \hline L_N \cap U_N^c \cap V_N^c & \frac17 & \mathbb P\left[A \mid V_0^c\right]\\ \hline L_N^c \cap U_N \cap V_N^c & \frac17 & \mathbb P\left[A \mid V_0^c\right]\\ \hline \left(L_N \cup U_N\right) \cap V_N & \frac37 & \mathbb P\left[A \mid V_0\right]\\ \hline \end{array}

Formulas:

\begin{align} \mathbb P\left[A \mid V^c\right] &= \frac14 \mathbb P\left[A \mid V\right] + \frac14 \mathbb P\left[A\mid V^c\right] \end{align}

and

\begin{align} \mathbb P\left[A \mid V_0\right] &= \frac27 + \frac27 \mathbb P\left[A\mid V_0^c\right] + \frac37\mathbb P\left[A\mid V_0\right] \end{align}

You can solve this system and finally evaluate the following:

$$\mathbb P\left[A\right] = \frac12 \left(\mathbb P\left[A\mid V\right] + \mathbb P\left[A\mid V^c\right]\right) = \frac25.$$

---

Question c:

If you want to find the pmf of $X$, do the same idea to $\mathbb E\left[t^X\right]$. Let $f(t) = \mathbb E\left[t^N\right]$.

Recursion

• In the case of $V_0^c$, \begin{array}{|c|c|c|} \hline \textbf{Event} & \textbf{Probability} & \mathbb E\left[t^X\right]\\ \hline L_1^c & \frac12 & 1\\ \hline L_1 \cap V_1^c & \frac14 & \mathbb E\left[t^{1+X} \mid V_0^c\right]\\ \hline L_1 \cap V_1 & \frac14 & \mathbb E\left[t^{1+X} \mid V_0\right]\\ \hline \end{array}

• In the case of $V_0$, \begin{array}{|c|c|c|} \hline \textbf{Event} & \textbf{Probability} & \mathbb E\left[t^X\mid N\right]\\ \hline L_N\cap U_N\cap V_N^c & 0 & \\ \hline L_N^c\cap U_N^c & \frac27 & t^{N-1}\\ \hline L_N \cap U_N^c \cap V_N^c & \frac17 & t^N\mathbb E\left[t^{X} \mid V_0^c\right]\\ \hline L_N^c \cap U_N \cap V_N^c & \frac17 & t^N\mathbb E\left[t^X \mid V_0^c\right]\\ \hline \left(L_N \cup U_N\right) \cap V_N & \frac37 & t^N\mathbb E\left[t^X \mid V_0\right]\\ \hline \end{array}

Formulas:

\begin{align} \mathbb E\left[t^X\mid V_0^c\right] &= \frac12 + \frac14 t\left(\mathbb E\left[t^X\mid V_0^c\right] + \mathbb E\left[t^X\mid V_0\right]\right) \end{align}

and

\begin{align} \mathbb E\left[t^X\mid V\right] &= f(t) \left(\frac2{7t} + \frac27 \mathbb E\left[t^X\mid V_0^c\right] + \frac37 \mathbb E\left[t^X\mid V_0\right]\right) \end{align}

Now solve the system and evaluate:

\begin{align} g(t) &= \mathbb E\left[t^X\right] = \frac12 \left(\mathbb E\left[t^X\mid V^c\right] + \mathbb E\left[t^X\mid V\right]\right)\\ &= \frac{6-t}{t^2 - 12t + 16}\\ &= \frac12 \left(\frac{1}{6 + 2\sqrt{5} - t} + \frac{1}{6 - 2\sqrt{5} - t}\right)\\ &= \frac12 \sum_{n=0}^{\infty}\left(\left(\frac1{6+2\sqrt{5}}\right)^{n+1} + \left(\frac1{6-2\sqrt{5}}\right)^{n+1}\right)t^n \end{align}

Where the last two steps use the partial fraction decomposition and the fact that $\frac1{a-t} = \sum_{n=0}^\infty \frac1{a^{n+1}}t^n$ for $t$ near $0$.

So $$\mathbb P\left[X = n\right]= \frac12 \left(\left(\frac1{6+2\sqrt{5}}\right)^{n+1} + \left(\frac1{6-2\sqrt{5}}\right)^{n+1}\right)$$

Answer 4

Define a Markov chain as follows:

• There are $4$ states $11,10,01,00$. We are in state $10$ at time $i$ if $(i,0)$ is reachable using only roads to the left of $i$ – i.e. left-only reachable – but $(i,1)$ is not, in state $11$ if both $(i,0)$ and $(i,1)$ are left-only reachable and similarly for the other two states.
• At $i=0$ we are in $11$ or $10$ with equal probability, corresponding to whether or not the leftmost rung of the ladder is blocked.
• Three edges are needed to compute the transition probabilities – the next rung and two side edges – and the transition matrix is $$P=\begin{bmatrix} 1/2&1/4&1/4&0\\1/8&1/4&0&0\\1/8&0&1/4&0\\1/4&1/2&1/2&1\end{bmatrix}\begin{bmatrix}p_{11}\\p_{10}\\p_{01}\\p_{00}\end{bmatrix}$$ Let the upper-left $3×3$ submatrix be $Q$; $Q^iv=Q^i(1/2,1/2,0)^T$ furnishes the probabilities of being in some transient (non-absorbing) state at time $i$. The remaining nonzero matrix $b=(1/4,1/2,1/2)^T$ gives the absorbing probabilities for each state.
• For this problem we need not consider reachable but not left-only reachable points – such a point implies $X$ is larger than where the king is currently at. So our chain really is a Markov chain, with $00$ an absorbing state.

The fundamental matrix is $$N=(I-Q)^{-1}=\begin{bmatrix}\frac{12}5&\frac45&\frac45\\\frac25&\frac{22}{15}&\frac2{15}\\\frac25&\frac2{15}&\frac{22}{15}\end{bmatrix}$$ and when left-multiplied by the all-ones vector produces the expected number of steps before absorbing if we start at a specific state, i.e. $E(X)+1$: $$\begin{bmatrix}\frac{16}5_{11}&\frac{12}5_{10}&\frac{12}5_{01}\end{bmatrix}$$ Taking the average of the first two components and subtracting $1$ gives the answer to (a) as $\frac95$.

$Q^iv\circ b$, where $\circ$ is the elementwise product, gives the probabilities of $X=i$ with given final transient state. The sum of this over all $i$ $$\sum_{i=0}^\infty Q^iv\circ b=\left(\sum_{i=0}^\infty Q^i\right)v\circ b=(I-Q)^{-1}v\circ b=Nv\circ b=\begin{bmatrix}\frac25_{11}\\\frac7{15}_{10}\\\frac2{15}_{01}\end{bmatrix}$$ is the distribution of states at $X=i$ – their sum is $1$ as they should be. Finally the answer to (b) is $\frac25$.