Markov chain ( Absorption) 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?
 A: 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!
