Performing a random walk on a lattice that traps the particles

Question

I am trying to solve this problem where we have a 1D-lattice of size 100 and the particle can start from any position in the lattice and moves randomly on it(with equal probability of moving to either direction). When the particle reaches either of the ends of the lattice it stops. The problem is to plot the time average(to reach the boundary) vs initial starting position of the particle when for each starting position we take 10000 trails to compute the time average.

This is my code

for i in range(1,size):
    timearr=[]
    for j in range(trails):
        time=0
        x=i
        while True:
            r = random.randint(-1,1)
            time+=1
            x+=r
            if x==0 or x==size:
                timearr.append(time)
                break
    timemean.append(np.mean(timearr))


xarr= np.arange(1,size)
plt.plot(xarr, timemean)
plt.show()

However, taking size as 100 and trials as 10000(or even 1000) it takes a humongous amount of time to run this. Is there any way to solve this faster using Python. Ideally, I would like to do this using a vectorised approach using numpy arrays. But I can't think of how to implement control-flow in that case.

Answer 1

This can be solved much more efficiently if you recast the problem as finding the mean first passage time (MFPT) of a Markov chain for a given starting state. You can easily represent the random walk on your lattice by a transition matrix and find the MFPT for each of the states. The problem can be solved using (numerical) linear algebra.

A recent survey of methods to accomplish this can be found in: https://arxiv.org/abs/1701.07781 Good books dealing with the topic are:

J. G. Kemeny and J. L. Snell, Finite Markov chains. D. Van Nostrand Co., Inc., Princeton, NJ-Toronto-London-New York, 1960.

and

D. A. Levin, Y. Peres, and E. L. Wilmer, Markov chains and mixing times. American Mathematical Society, Providence, RI, 2009.