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?
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.
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{**}$$
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.
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.
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!
