3
$\begingroup$

$\textbf{Background:}$ Consider a particle in $\mathbb{N}^2$ starting at a point $(x,y)$ that can only move one step at a time along the lattice. The particle moves each up or down in continuous time with rate $y$, and each left or right with rate $x$. It will therefore be moving faster, the further away from the origin that it is. Furthermore, once it hits an axis, it cannot leave that axis, so the axes act as a kind of absorbing boundary. I am wondering about the expected time (or, in an ideal world, the distribution) for the particle to hit either axis for the first time.

$\textbf{Question:}$ Write $v(x,y)$ for the expected time for the particle to hit either axis given it began at $(x,y)$. What is $v(x,y)$? We can write the recurrence equation $$ v(x,y) = \frac{1}{2(x+y)} + \frac{x}{2(x+y)} (v(x-1,y) + v(x+1,y)) + \frac{y}{2(x+y)} (v(x,y-1) + v(x,y+1))$$ for $x,y>0$, and with boundary conditions $v(x,0) = v(0,y) = 0 \; \; \; \forall \; x,y>0$.

In particular, if we let $x=y$, the equation can be written as $$ \frac{1}{2x} + (v(x+1,x) - v(x,x)) = (v(x,x) - v(x-1,x))$$ which feels, to me, like it might be a good place to start.

$\textbf{What I've got so far}:$

  • A poor upper bound on $v(x,y)$ that shows it's finite.
  • The particle must hit one of the axes eventually, and can't hit both at the same time. The probability that the particle hits the x-axis before the y-axis, starting at the point $(x,y)$, is $x/(x+y)$ .
  • If one defines the same process in 1d, the expected time to hit the origin given a start point of $x$ is clearly infinite. But the expected hitting time of either $0$ or $A$, starting at $0<x<A$, is $x(H_A - H_x)$, where $H_m$ is the $m$-th harmonic number.
$\endgroup$
  • $\begingroup$ The horizontal and vertical coordinates are independent processes aren't they? If so, they should be studied separately... $\endgroup$ – Anthony Quas Mar 13 at 15:42
  • $\begingroup$ Yes, they are, but the question is about them running simultaneously. One could rephrase as: Given two independent 1d processes (with the specified frequency-dependent rates) and denoting $t_1(x)$ and $t_2(y)$ as the time for each process to hit $0$ starting at $x>0$ and $y>0$ respectively, what is $v(x,y) = E(min(t_1(x),t_2(y)))$? $\endgroup$ – Samuel Reid Mar 13 at 16:43
  • 2
    $\begingroup$ Ok, but given this, it’s pretty clear that you can get all the information you need from the 1d process. And you should be able to figure out the expected hitting time for that by approximating the 1d difference equation by a differential equation. $\endgroup$ – Anthony Quas Mar 14 at 2:46
  • $\begingroup$ Well, first of all the expected hitting time for the 1d process is infinite. But a similar quantity is noted at the end of my question. I'm unclear exactly how this will help me get the answer for the 2d process though. Would you mind elaborating? $\endgroup$ – Samuel Reid Mar 14 at 15:07
4
+50
$\begingroup$

Some experimenting reveals that the hitting time $t_1(x)$ of the 1D process started at $x\in\mathbb{N}$ (in the notation of OP's comment) has a simple cdf, $$\mathbb{P}(t_1(x) < t ) = \left(\frac{t}{t+1}\right)^x.$$ I don't know an easy combinatorial proof, but one may check explicitly that it solves $$\mathbb{P}(t_1(x) < t ) = \int_0^t \mathrm{d}s\, 2x\,e^{-2x s} \tfrac12\left[\mathbb{P}(t_1(x+1) < t-s )+\mathbb{P}(t_1(x-1) < t-s )\right].$$

Edit: The fact that $\mathbb{P}(t_1(x) < t ) = \mathbb{P}(t_1(1) < t )^x$ can easily be understood in the light of James Martin's answer. For the whole population to die out before time $t$, the descendants of each of the $x$ initial individuals have to die out before time $t$.

It follows immediately that $$\mathbb{P}(\min(t_1(x),t_2(y))>t) = \left[1-\left(\frac{t}{t+1}\right)^{x}\right]\left[1-\left(\frac{t}{t+1}\right)^{y}\right].$$ Hence \begin{align*}v(x,y) &= \mathbb{E}(\min(t_1(x),t_2(y))) \\ &= \int_0^\infty \mathrm{d}t\left[1-\left(\frac{t}{t+1}\right)^{x}\right]\left[1-\left(\frac{t}{t+1}\right)^{y}\right]\\ &=1 - x\,H_x-y\, H_y+(x+y)H_{x+y-1} < \infty, \end{align*} where $H_n$ is the $n$th harmonic number.

$\endgroup$
  • $\begingroup$ I think the answer is correct, but that there is a mistake in OP's recurrence relation. Shouldn't the $\frac{1}{2(x+y)}$ on the right-hand side be $\frac{1}{x+y}$? $\endgroup$ – Timothy Budd Apr 5 at 19:59
  • $\begingroup$ You are right. I interpreted the process as jumping vertically with rate $y$ (up or down with equal probability), but it jumps up and down both with rate $y$. Let me include the appropriate factors of two. $\endgroup$ – Timothy Budd Apr 5 at 20:30
  • $\begingroup$ This is really lovely, and I'm hoping (either of) you could help me understand: Where did the integral equation for $P(t_1(x)<t)$ come from? And, more generally, how does one go about "experimenting"? How does one gain intuition for these things? (It strikes me that I never would have come up with this.) Nawaf spoke of having "no general strategies" in his answer to the question linked as well. I am somewhat in awe of seemingly guess-and-check mathematics that arises out of intuition. $\endgroup$ – Samuel Reid Apr 9 at 12:09
  • 2
    $\begingroup$ The integral equation for $\mathbb{P}(t_1(x)<t)$ just expresses the fact that the first jump occurs after time $s$ distributed as an exponential r.v. with parameter $2x$, after which it jumps to $x+1$ or $x-1$ with equal probability. As to your more general question concerning "experimenting": As soon as one encounters a one-dimensional difference equation, it is natural to turn it into a differential equation by introducing generating functions. Then one can try to solve or guess the solution. $\endgroup$ – Timothy Budd Apr 9 at 15:33
  • $\begingroup$ In this particular case the 1d process is a birth-death process for which standard solution methods are available. $\endgroup$ – Timothy Budd Apr 9 at 15:35

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.