6
$\begingroup$

I have just started learning Markov chain and I am clueless about how to solve this problem

A man rolls a boulder up a 40 meter-high hill. Each minute, with probability 1/3 he manages to roll the boulder 1 meter up, while with probability 2/3 the boulder rolls 1 meter down. If the man is currently half-way towards the summit, what is the probability that he will reach the summit before descending to the foothills?

$\endgroup$
3
$\begingroup$

It would be overkill to solve this problem using Markov Chain theory: but the underlying concepts will help you frame it an a way that admits a simple solution.

Formulating the problem

The most fundamental concept is that of a state: we may model this situation in terms of 41 distinct positions, or "states," situated at one-meter height intervals from the bottom (height -40) to the top (height 0) of the hill. The current state, halfway up the hill, is a height of -20.

The second fundamental concept is that of independence from past events: the chance of what happens next depends only on the state, not on any details of how the man got there. Consequently, the chance of reaching the summit depends only on the state. Accordingly, if we write $s$ for a state, the chance of reaching the summit can be simply written $p(s).$ We are asked to find $p(-20).$

From any state $s$ between $-40$ and $0$ there is a $1/3$ chance that $s+1$ will be the next state and a $2/3$ chance that $s-1$ will be the next state. The most basic laws of conditional probability then imply

$$p(s) = (1/3)p(s+1) + (2/3)p(s-1) = \frac{p(s+1)+2p(s-1)}{3}.\tag{*}$$

The final step of formulating the problem treats the endpoints, or "absorbing states" $s=0$ and $s=-40.$ It should be clear that

$$p(0)=1;\ p(-40)=0.\tag{**}$$

Analysis

At this point the work may look formidable: who wants to solve a sequence of 40 equations? A nice solution method combines all the equations into a single mathematical object. But before we proceed, allow me to remark that you don't need to follow this analysis: it will suffice to check that the final formula (highlighted below) satisfies all the conditions established by the problem -- and this is just a matter of simple algebra.

At this juncture it is helpful to solve the general problem. Let's suppose there is a sequence of states $s=0,1,2,\ldots, n$ and that each state $s$ between $1$ and $n-1$ transitions to $s-1$ with probability $p$ and to $s+1$ with probability $1-p.$ For all $s$ let $a_s$ be the chance of arriving at state $0$ before hitting state $n.$ (I have dropped the previous "$p(-s)$" notation because it leads to too many p's and I have switched from indexing states with negative numbers to indexing them with positive numbers.)

As we have seen, $a_0=1,$ $a_n=0,$ and otherwise $a_{s} = pa_{s-1} + (1-p)a_{s+1}$ (the "recurrence relation"). This set of equations is neatly encoded by a polynomial

$$P(t) = a_0 + a_1 t + a_2 t^2 + \cdots + a_n t^n = a_0 + \sum_{s=1}^{n} a_s t^s.$$

Plugging in the recurrence relation and then collecting common powers of $t$ (writing $a_{n+1}=0$ for convenience) gives

$$\begin{aligned} P(t) &= a_0 + \sum_{s=1}^n \left[pa_{s-1} + (1-p)a_{s+1}\right]t^s \\ &= a_0 + p\sum_{s=1}^n a_{s-1} t^s + (1-p)\sum_{s=1}^n a_{s+1}t^s\\ &= a_0 + pt\sum_{s=1}^n a_{s-1} t^{s-1} + \frac{1-p}{t}\sum_{s=1}^n a_{s+1}t^{s+1}\\ &= a_0 + pt\sum_{s=0}^{n-1} a_{s} t^{s} + \frac{1-p}{t}\sum_{s=2}^{n+1} a_{s}t^{s}\\ &= a_0 + pt(P(t) - a_nt^n) + \frac{1-p}{t}(P(t) - a_0 - a_1t) \end{aligned}$$

This is a single equation for the polynomial $P$ (at least up to $t^n;$ I will ignore any coefficients of $t^n$ or higher powers that might be needed to make the equation work out exactly.) Simplify this equation a little using the initial condition $a_0=1$ and solve for $P$ to get

$$P(t) = \frac{(1-p) + (-1 + (1-p)a_1)t}{pt^2 - t + (1-p)}.$$

Now every coefficient of $P$ can be expressed in terms of the (still unknown) number $a_1.$ The value of $a_1$ is determined by the final condition $a_n=0.$

A closed formula is possible by expanding the right hand side as a partial fraction. It comes down to observing

$$\frac{1}{pt^2 - t + (1-p)} = \frac{1}{1-2p}\left(\frac{1}{1-t} - \frac{\lambda}{1 - \lambda t}\right)$$

and expanding the fractions as sums of geometric series, both of which are in the form

$$\frac{\rho}{1 - \rho t} = \rho + \rho^2 t + \rho^3 t^2 + \cdots$$

and multiplying that by the numerator $(1-p) + (-1 + (1-p)a_1)t$ to obtain $P(t).$ This gives a closed formula for every term in $P(t)$ as a function of $a_1.$

For $p\ne 1/2$ and writing $\lambda = p/(1-p)$ this approach gives the general result

$$a_s = \frac{\lambda^s - \lambda^n}{1 - \lambda^n}$$

for $s=1, 2, \ldots, n$ (and this happens to work for $s=0,$ too). (When $p=1/2,$ $\lambda=1$ makes this formula undefined. You can easily figure it out a simple formula, though, by taking the limit of $a_s$ as $\lambda\to 1$ using a single application of L'Hopital's Rule.)

As a check, it is clear this formula gives $a_0=1$ and $a_n=0.$ It remains to verify it satisfies the recurrence relation, but that's a matter of showing

$$\frac{\lambda^s - \lambda^n}{1 - \lambda^n} = a_s = pa_{s-1} + (1-p)a_{s+1} = p\frac{\lambda^{s-1} - \lambda^n}{1 - \lambda^n} + (1-p)\frac{\lambda^{s+1} - \lambda^n}{1 - \lambda^n},$$

which is straightforward.

Application

In the given problem $n=40,$ $p=1/3,$ and we are asked to find $a_{20}.$ Consequently $\lambda = (1/3)\,/\,(1-1/3) = 1/2$ and

$$a_{20} = \frac{2^{-20} - 2^{-40}}{1 - 2^{-40}} = 2^{-20} - 2^{-40} + 2^{-60} - 2^{-80} + \cdots.$$

The expansion on the right hand side can be terminated after the first two terms when computing in double precision floating point (which has a precision of $52$ binary places), giving

$$a_{20} \approx 2^{-20} - 2^{-40} \approx 9.53673406911546\times 10^{-7};$$

a little less than one in a million.

$\endgroup$
6
  • $\begingroup$ can you please how you got the polynomial P(t)=a0+a1t+a2t2+⋯+antn=a0+∑s=1nasts. $\endgroup$ – bluelagoon Nov 17 '20 at 13:32
  • $\begingroup$ I cannot tell what you are asking. I would guess you might be inquiring why anyone would think of using a polynomial to solve this problem; the answer to that goes back a few hundred years to Laplace: it's called a generating function. $\endgroup$ – whuber Nov 17 '20 at 13:58
  • $\begingroup$ I am asking that how did you derive the polynomial in that form, the very first polynomial P(t) = a0 + a1*t + ,,,,a1*(t^n), I don't see how this set of equations can be neatly encoded by this polynomial. $\endgroup$ – bluelagoon Nov 17 '20 at 14:15
  • $\begingroup$ I didn't derive it -- that polynomial is merely a way of writing down the $a_s$ in a useful way. The encoding of the equations is achieved by the subsequent analysis culminating in the single equation for $P(t),$ where I wrote "This is a single equation for the polynomial..." $\endgroup$ – whuber Nov 17 '20 at 14:15
  • $\begingroup$ how did you get the general result for a(s) i.e a(s)=λ^(s)−λ^(n)/1−λn $\endgroup$ – bluelagoon Nov 17 '20 at 14:49
1
$\begingroup$

Imagine that the hill-climbing journey consists of 41 states, one for each meter possible, so states 0, 1, 3, ...., 40. The transition probability matrix then becomes a 41x41 matrix, representing the different probabilities of going from one state to another. It looks like the following:

   0    1    2    --    40
0  0    1    0    --     0
1 2/3   0   1/3   --     0
2  0   2/3   0    --     0
|  |    |    |    --     |
|  |    |    |    --     |
40 0    0    0    --     0

Let's call this matrix P. If we start at 20 meters, with other words at state 20, we can represent this as a vector (41 elements long) with the probabilities of starting in each state, called u, u=[0,0, ... , 0, 1, 0 ... 0, 0], where the 1 represent a 100% probability of starting at 20 meters.

The matrix multiplication, u*P, then becomes the probabilities of ending up in all other states at timestep t+1. If we continue to do this matrix multiplication over and over again, u*P^t, where t goes towards infinity, we will reach a steady state matrix P*. This steady state matrix represents the probabilities of ending up in all other states.

So in your case, you would do this matrix multiplication in a programming language of your choice many times (eg. 100+), and you would simply look up P[20,40], which would give you the probability of starting at 20 meters and making it all the way atop the hill!

$\endgroup$
3
  • 1
    $\begingroup$ in tansition probability matrix the sum of the rows should add up to 1 but in your answer it doesn't and also we haven't been using any programming language, so I feel like there should be other easier of doing this. $\endgroup$ – bluelagoon Nov 15 '20 at 23:18
  • $\begingroup$ You are correct about that each row should sum to one, so did a slight edit to the 0-to-1 state, thanks. Unfortunately I do not know any other way of solving your problem 'by hand'... $\endgroup$ – Marcus Nov 16 '20 at 4:23
  • $\begingroup$ There are several issues with this answer, but they could be fixed. First, the transition matrix is incorrect. Although that's a minor typographical error, it's a crucial one because you haven't otherwise explicitly stated how it is to be filled in. Second, by using brute force matrix multiplication this procedure is hugely inefficient. Third, it propagates floating point error. Although it gives an adequate value at 20 meters, it's noticeably wrong for heights below 5 meters or so, where it has only four to six decimal digits of precision. For larger problems this won't do. $\endgroup$ – whuber Nov 16 '20 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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