An apple is located at vertex $A$ of pentagon $ABCDE$, and a worm is located two vertices away, at $C$. Every day the worm crawls with equal probability to one of the two adjacent vertices. Thus after one day the worm is at vertex $B$ or $D$, each with probability $1/2$ . After two days, the worm might be back at $C$ again, because it has no memory of previous positions. When it reaches vertex $A$, it stops to dine.

(a) What is the mean of the number of days until dinner?

(b) Let p be the probability that the number of days is $100$ or more. What does Markov’s Inequality say about $p$?

For (a), let $X$ be the random variable defined by the number of days until dinner. So $$ P(X = 0) = 0 \\ P(X=1) = 0 \\ P(X=2) = \frac{1}{\binom{5}{2}} \\ \vdots$$

What would be the general distribution?

For (b), if we know (a), then we know that $$P(X \geq 100) \leq \frac{E(X)}{100}$$

  • 2
    Could you explain your first set of equations? They don't seem to account for the possibility of the worm reversing direction, nor do they seem correct. After all, $1/\binom{5}{2}=1/10$ is far less than the chance of the path $A\to B\to C$ which has probability $(1/2)(1/2)=1/4.$ Note that the point of this question is that it may be more difficult to obtain the full distribution than to compute its expectation; and Markov's Inequality nevertheless lets you deduce useful information from the expectation alone. – whuber Aug 28 at 22:18

In the excellent answer by Glen_b, he shows that you can calculate the expected value analytically using a simple system of linear equations. Following this analytic method you can determine that the expected number of moves to the apple is six. Another excellent answer by whuber shows how to derive the probability mass function for the process after any given number of moves, and this method can also be used to obtain an analytic solution for the expected value. If you would like to see some further insight on this problem, you should read some papers on circular random walks (see e.g., Stephens 1963)

To give an alternative view of the problem, I am going to show you how you can get the same result using the brute force method of just calculating out the Markov chain using statistical computing. This method is inferior to analytical examination in many respects, but it has the advantage that it lets you to deal with the problem without requiring any major mathematical insight.


Brute force computational method: Taking the states in order $A,B,C,D,E$, your Markov chain transitions according to the following transition matrix:

$$\mathbf{P} = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\[6pt] \tfrac{1}{2} & 0 & \tfrac{1}{2} & 0 & 0 \\[6pt] 0 & \tfrac{1}{2} & 0 & \tfrac{1}{2} & 0 \\[6pt] 0 & 0 & \tfrac{1}{2} & 0 & \tfrac{1}{2} \\[6pt] \tfrac{1}{2} & 0 & 0 & \tfrac{1}{2} & 0 \\[6pt] \end{bmatrix}$$

The first state is the absorbing state $A$ where the worm is at the apple. Let $T_C$ be the number of moves until the worm gets to the apple from state $C$. Then for all $n \in \mathbb{N}$ the probability that the worm is at the apple after this number of moves is $\mathbb{P}(T_C \leqslant n) = \{ \mathbf{P}^n \}_{C,A}$ and so the expected number of moves to get to the apple from this state is:

$$\mathbb{E}(T_C) = \sum_{n=0}^\infty \mathbb{P}(T_C > n) = \sum_{n=0}^\infty (1-\{ \mathbf{P}^n \}_{C,A}).$$

The terms in the sum decrease exponentially for large $n$ so we can compute the expected value to any desired level of accuracy by truncating the sum at a finite number of terms. (The exponential decay of the terms ensures that we can limit the size of the removed terms to be below a desired level.) In practice it is easy to take a large number of terms until the size of the remaining terms is extremely small.


Programming this in R: You can program this as a function in R using the code below. This code has been vectorised to generate an array of powers of the transition matrix for a finite sequence of moves. We also generate a plot of the probability that the apple has not been reached, showing that this decreases exponentially.

#Create function to give n-step transition matrix for n = 1,...,N
#N is the last value of n
PROB <- function(N) { P <- matrix(c(1, 0, 0, 0, 0, 
                                    1/2, 0, 1/2, 0, 0, 
                                    0, 1/2, 0, 1/2, 0,
                                    0, 0, 1/2, 0, 1/2,
                                    1/2, 0, 0, 1/2, 0),
                                  nrow = 5, ncol = 5, 
                                  byrow = TRUE);
                      PPP <- array(0, dim = c(5,5,N));
                      PPP[,,1] <- P;
                      for (n in 2:N) { PPP[,,n] <- PPP[,,n-1] %*% P; } 
                      PPP }

#Calculate probabilities of reaching apple for n = 1,...,100
N  <- 100;
DF <- data.frame(Probability = PROB(N)[3,1,], Moves = 1:N);

#Plot probability of not having reached apple
library(ggplot2);
FIGURE <- ggplot(DF, aes(x = Moves, y = 1-Probability)) +
          geom_point() +
          scale_y_log10(breaks = scales::trans_breaks("log10", function(x) 10^x),
                        labels = scales::trans_format("log10", 
                                 scales::math_format(10^.x))) +
          ggtitle('Probability that worm has not reached apple') +
          xlab('Number of Moves') + ylab('Probability');
FIGURE;

#Calculate expected number of moves to get to apple
#Calculation truncates the infinite sum at N = 100
#We add one to represent the term for n = 0
EXP <- 1 + sum(1-DF$Probability);
EXP;

[1] 6

As you can see from this calculation, the expected number of moves to get to the apple is six. This calculation was extremely rapid using the above vectorised code for the Markov chain.

enter image description here

Just want to illustrate a simple way to look at part (a) without going through all the Markov chain routine. There are two classes of states to worry about: being one step away and being two steps away (C and D are identical in terms of expected steps until reaching A, and B and E are identical). Let "$S_B$" represent the number of steps it takes from vertex $B$ and so on.

$E(S_C) = 1+\frac12[E(S_B)+E(S_D)] = 1+ \frac12[E(S_B)+E(S_C)]$

Similarly write an equation for the expectation for $E(S_B)$.

Substitute the second into the first (and for convenience write $c$ for $E(S_C)$) and you get a solution for $c$ in a couple of lines.

  • 3
    +1. I also like that by replacing the expectations by the probability generating functions you get a similar equation, just as easily solved, showing that the pgf for the starting state equals $t^2/(4-2t-t^2),$ and that leads to a simple formula for any of the probabilities. Better: let $X_y$ be the number of steps starting at $y\in\{A,B\}.$ Define $f_n=2^n\Pr(X_A=n)$ and $g_n=2^n\Pr(X_B=n).$ The relations are $f_n=f_{n-1}+g_{n-1}$ and $g_{n-1}=f_{n-2}.$ Substituting the latter into the former yields $f_n=f_{n-1}+f_{n-2}$ for $n\ge 3.$ Thus, $f_n$ is the $n-2^\text{nd}$ Fibonacci number. – whuber Aug 29 at 13:58
  • @whuber: You should turn your comment into a full answer - it is really good. – Ben Aug 30 at 0:13
  • 1
    I agree, it's worth posting as an answer, even in this brief form. – Glen_b Aug 30 at 0:14

The problem

This Markov chain has three states, distinguished by whether the worm is $0,$ $1,$ or $2$ spaces away from $C.$ Let $X_i$ be the random variable giving how many steps the worm will take to reach $C$ from state $i\in\{0,1,2\}.$ Their probability generating functions are a convenient algebraic way to encode the probabilities of these variables. It is unnecessary to worry about analytic issues like convergence: just view them as formal power series in a symbol $t$ given by

$$f_i(t) = \Pr(X_i=0) + \Pr(X_i=1)t^1 + \Pr(X_i=2)t^2 + \cdots + \Pr(X_i=n)t^n + \cdots$$

Since $\Pr(X_0=0)=1,$ it is trivial that $f_0(t)=1.$ We need to find $f_2.$

Analysis and solution

From state $1,$ the worm has equal chances of $1/2$ of moving back to state $2$ or reaching $C$. Accounting for taking this one step adds $1$ to all powers of $t$, tantamount to multiplying the pgf by $t$, giving

$$f_1 = \frac{1}{2}t\left(f_2 + f_0\right).$$

Similarly, from state $2$ the worm has equal chances of staying in state $2$ or reaching state $1,$ whence

$$f_2 = \frac{1}{2}t\left(f_2 + f_1\right).$$

The appearance of $t/2$ suggests our work will be made easier by introducing the variable $x=t/2,$ giving

$$f_1(x) = x(f_2(x) + f_0(x));\quad f_2(x) = x(f_2(x) + f_1(x)).$$

Substituting the first into the second and recalling $f_0=1$ gives

$$f_2(x) = x(f_2(x) + x(f_2(x) + 1))\tag{*}$$

whose unique solution is

$$f_2(x) = \frac{x^2}{1 - x - x^2}.\tag{**}$$

I highlighted the equation $(*)$ to emphasize its basic simplicity and its formal similarity to the equation we would obtain by analyzing only the expected values $E[X_i]:$ in effect, for the same amount of work it takes to find this one number, we get the entire distribution.

Implications and simplification

Equivalently, when $(*)$ is written out term-by-term and the powers of $t$ are matched it asserts that for $n\ge 4,$

$$2^n\Pr(X_2=n) = 2^{n-1}\Pr(X_2=n-1) + 2^{n-2}\Pr(X_2=n-2).$$

This is the recurrence for the famous sequence of Fibonacci numbers

$$(F_n) = (1,1,2,3,5,8,13,21,34,55,89,144,\ldots)$$

(indexed from $n=0$). The solution matching $(**)$ is this sequence shifted by two places (because there is no probability that $X_2=0$ or $X_2=1$ and it is easy to check that $2^2\Pr(X_2=2)=1=2^3\Pr(X_2=3)$).

Consequently

$$\Pr(X_2 = n) = 2^{-n-2}F_{n-2}.$$

More specifically,

$$\eqalign{ f_2(t) &= 2^{-2}F_0t^2 + 2^{-3}F_1 t^3 + 2^{-4} F_2 t^4 + \cdots \\ &= \frac{1}{4}t^2 + \frac{1}{8}t^3 + \frac{2}{16}t^4 + \frac{3}{32}t^5 + \frac{5}{64}t^6 + \frac{8}{128}t^7 +\frac{13}{256}t^8 + \cdots. }$$


The expectation of $X_2$ is readily found by evaluating the derivative $f^\prime$ and substituting $t=1,$ because (differentiating the powers of $t$ term by term) this gives the formula

$$f^\prime(1) = \Pr(X_2=0)(0) + \Pr(X_2=1)(1)1^0 + \cdots + \Pr(X_2=n)(n)1^{n-1} + \cdots$$

which, as the sum of the probabilities times the values of $X_2,$ is precisely the definition of $E[X_2].$ Taking the derivative using $(**)$ produces a simple formula for the expectation.


Some brief comments

By expanding $(**)$ as partial fractions, $f_2$ can be written as the sum of two geometric series. This immediately shows the probabilities $\Pr(X_2=n)$ will decrease exponentially. It also yields a closed form for the tail probabilities $\Pr(X_2 \gt n).$ Using that, we can quickly compute that $\Pr(X_2 \ge 100)$ is a little less than $10^{-9}.$

Finally, these formulas involve the Golden Ratio $\phi = (1 + \sqrt{5})/2.$ This number is the length of a chord of a regular pentagon (of unit side), yielding a striking connection between a purely combinatorial Markov chain on the pentagon (which "knows" nothing about Euclidean geometry) and the geometry of a regular pentagon in the Euclidean plane.

For the mean number of days until dinner, condition on the step taken on the first day. Let $X$ be the number of days until the worm gets the apple. Let $F$ be the first step.

Then we have

$$E[X]=E[X|F=B] \ [P(F=B)]+E[X|F=D] \ P[F=D]$$

If the first step is to $B,$ then either the worm gets the apple on day 2 with probability one-half, or it is back to vertex $C$ with probability one-half and it starts over. We can write this as

$$E[X|F=B]=2 \left( \frac{1}{2} \right) + \left(2+E[X] \right) \left( \frac{1}{2} \right)=2+\frac{E[X]}{2}$$

If the first step is to $D,$ then by symmetry this is the same as being at vertex $C$ except the worm has taken a single step so

$$E[X|F=D]=1+E[X]$$

Putting it all together, we get

$$E[X] = \left( 2+\frac{E[X]}{2} \right)\left( \frac{1}{2} \right) + \left( 1 + E[X] \right)\left( \frac{1}{2} \right) $$

Solving for $E[X]$ yields

$$E[X] = 6$$

  • 1
    This seems to recapitulate @Glen_b's answer. – whuber Aug 30 at 21:28

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.