# Random walk and comparing sums of Exponential random variables

Let $$\sigma$$ be the time a nearest neighbor random walk started at 1 that has probability $$p>1/2$$ of moving left reaches $$0$$. Let $$\sigma'$$ be an independent copy of $$\sigma$$. Let $$(X_k)_1^\infty$$ be iid unit Exponential random variables, and let $$(Y_k)_1^\infty$$ be iid Exponentials with mean $$v$$ (i.e. $$P(Y_1 \geq t) = e^{-t/v}$$).

We are interested in if there is a closed form in terms of $$p$$ and $$v$$ for the probability $$P \left( \sum_1^\sigma X_k < \sum_1^{\sigma '} Y_k \right).$$

Conditioning on the value of either sum gives a messy expression that isn't obvious how to simplify.

A reformulation of the problem is to think of this as a race to reach 0 by two continuous time random walks with rates $$1$$ and $$1/v$$. Using the memoryless property, the probability the rate-1 walk advances at a jump time is $$q=v/(1+v)$$. Otherwise the rate-$$1/v$$ walk advances. Let $$Z(r,q)$$ be the number of successes before $$r$$ failures occur in iid trials with success probability $$q$$ (i.e. negative binomial). If we think of the rate-$$1$$ walk advancing as a success, we can rewrite the above probability as $$P( Z(\sigma,q) > \sigma').$$ Condition on the values of $$\sigma$$ and $$\sigma'$$ and use the distribution for a negative binomial to write this as $$\sum_{i,j \geq 0} C_i C_j p^2(p(1-p))^{i+j} \sum_{k\geq 2i+1} \binom{2j +k}{k} q^k (1-q)^{2j+1} .$$ Here $$C_i$$ is the $$i$$th Catalan number. It does not look easy to evaluate exactly. We are happier with this though because it is easier to numerically approximate (though we would prefer a closed form).

• Is there any reason you didn’t write the right term in the inequality as $\nu \sum Z_i$, where $Z_i$ are unit mean exponentials? – Anthony Quas Nov 9 '18 at 19:10
• That may be better, but I am viewing this like a race to return to 0 by two continuous time biased random walks with rates 1 and 1/v. So this formulation is natural from that perspective. – Matthew Junge Nov 9 '18 at 23:14
• It seems that this could also be reformulated as a Markov chain on the first quadrant of the integer lattice, where the two walks correspond to the horizontal and vertical directions, and you are asking about the probability to exit through either the $x$-axis or the $y$-axis. Possibly some martingale methods are available...? – Nate Eldredge Nov 10 '18 at 0:18