Hitting time of two or three parallel random walks

[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 r₁, r₂, …, that run in parallel, and I want to find the expected time required for at least one of these random walks r_i 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

 

[Stephen Tashi]

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

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.

 

[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 RW₁ and RW₂ (in the lines of the proof of Lemma 0.2 from http://www.cs.cornell.edu/courses/cs4850/2010sp/Scribe%20Notes%5CLecture18.pdf ), 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 RW₁=α₁ or RW₂=α₂. Furthermore, one can reach any point (RW₁=i, RW₂=j) following paths for which the last step is not necessarily (RW₁=i-1, RW₂=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?

 

[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.

 

[opapa]

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