# Hitting time of two or three parallel random walks

1. Jul 10, 2014

### opapa

Consider a one-dimensional random walk on the integer lattice, starting at 0. The next step is decided to be +1 or -1 with equal probability 0.5. The hitting time (the expected time required for the random walk to reach any integer α -- also called the first-passage time) will be $\Theta(\alpha^2)$, since random walks are martingales. Similarly, given two numbers (α<0 and β>0), the expected time for the random walk to reach either α or β is α*β.

In my case, I have two or more independent random walks r1, r2, …, that run in parallel, and I want to find the expected time required for at least one of these random walks ri to reach either αi or βi (notice that the boundaries αi and βi can be different for each random walk). My initial intuition was that, since these random walks are independent, I could find the hitting time for each random walk and get the minimum, but I found this to be wrong through a computer simulation.

Any pointers?
Thanks

2. Jul 10, 2014

### Stephen Tashi

If we throw two fair dice, is it intuitive that the expected minimum of the two dice would be the minmum of their two expected values? If it were, then the expected minimum from throwing two dice would be the same as the expected minimum from throwing one die, since we'd take the minimum of two equal numbers.

3. Jul 11, 2014

### opapa

Thanks for the response. You are right of course that I cannot deduce something from the expected values for each walk, I need to compute the expected value from scratch.

Trying to recompute the hitting time for two random walks RW1 and RW2 (in the lines of the proof of Lemma 0.2 from http://www.cs.cornell.edu/courses/cs4850/2010sp/Scribe%20Notes%5CLecture18.pdf [Broken]), I realized that it gets very complex. The main difference is that now I am not interested in reaching a point for a first time, but in reaching a group of points, e.g., when RW11 or RW22. Furthermore, one can reach any point (RW1=i, RW2=j) following paths for which the last step is not necessarily (RW1=i-1, RW2=j-1). Therefore, it is not clear to me how the starting equation in Lemma 0.2 will be adapted for 2 dimensions.

Is there any other direction that does not have these issues?

Last edited by a moderator: May 6, 2017
4. Jul 12, 2014

### Stephen Tashi

Finding the distribution of the minimum of two independent random variables falls under the heading of "order statistics". The distribution of the minimum depends only on the distrubutions of the random variables involved. http://en.wikipedia.org/wiki/Bapat–Beg_theorem

If you have a more complicated question that is particular to graph theory, I think you should post it in a new thread and put something indicating graph theory in the title.

5. Jul 14, 2014

### opapa

Thanks! The theorem seems relevant. I will have a look at it, and, if needed, I will initiate a new thread as suggested.