1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ So, a particle at each step can go into any direction. And you want to test each starting position. For large $N$ the number of steps required will be huge, no matter what... you probably can cut some constants from your implementation by using numpy and vectorization. However, I would expect marginal improvement for this algorithm. $\endgroup$ – Anton Menshov Mar 28 '18 at 14:04
  • $\begingroup$ BTW, one thing you can do: you can test only half of your positions. As the response is expected to be symmetric (equal probability of left vs. right) $\endgroup$ – Anton Menshov Mar 28 '18 at 14:05
  • $\begingroup$ I don't think either of those suggestions would improve my run time significantly, I'm looking for something along of lines of an order of magnitude(or more) improvement $\endgroup$ – Prada Mar 28 '18 at 17:43
  • 2
    $\begingroup$ Then you should look into changing your algorithm completely, not the implementation. $\endgroup$ – Anton Menshov Mar 28 '18 at 17:44
4
$\begingroup$

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.

$\endgroup$

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.