2
$\begingroup$

Consider two random processes $X, Y$. $Y$ is a Poisson process with rate $\lambda$. $X$ behaves as follows: whenever $X < Y$, it acts equivalent to a Poisson process with rate $\lambda$ (independent of $Y$). Whenever $X = Y$, it waits until $Y$ increments, so that $Y - X = 1$, before continuing to increment itself. (In other words, $X$ never allows itself to surpass $Y$).

My question is: what is known about the distribution of $X$? Specifically, can anyone offer any bounds regarding the expected time until $X > n$, for arbitrary $n$?

My simulations indicate that it's roughly Y's arrival time plus some very slowly growing "lag" when $n$ is very big. This lag is sort of intuitive: consider the case where you have a whole bunch of processes each bounding the one to its left; in that case you would intuitively have quite a big discrepancy between the leftmost process and the rightmost one.

$\endgroup$
3
  • 1
    $\begingroup$ Not sure about the answer, but try to give a formulation first. Let $Z_n, W_n$ be the $n$-th arrival time of the process $X, Y$ respectively. $W_n$ is well known to have a Gamma/Erlang distribution, while $Z_n = \max\{Z_{n-1}, W_n\} + V_n$ where $V_n$ is an exponential random variable with rate $\lambda$, independent. $\endgroup$
    – BGM
    Jul 11, 2018 at 3:17
  • 1
    $\begingroup$ You can view this as a symmetric random walk $Z=Y-X$ on $\mathbb Z$ in which steps are taken with rate $2\lambda$ and all negative steps at the origin are discarded. You want to know the expected number of steps until $n+1$ negative steps have been taken. I think you should be able to derive a generating function for this. Some of the techniques I used in this answer might be useful. If I find the time, I'll try to work it out in more detail. $\endgroup$
    – joriki
    Jul 11, 2018 at 6:11
  • $\begingroup$ @joriki That's a clever observation. I'd greatly appreciate if you find the time to post an answer; I am not too familiar with generating functions. $\endgroup$
    – aellab
    Jul 11, 2018 at 12:41

1 Answer 1

Reset to default
1
$\begingroup$

Fix a positive integer $n$. If $T_{ij}$ is the expected time for $X$ to reach state $n$, given $(X(t),Y(t))=(i,j)$, then you can stop the $Y$ process once it reaches state $n$ and you get a state space of integers $(i,j)$ for $0\leq i\leq j \leq n$ and equations \begin{align} T_{ij} &=\frac{1}{2\lambda} + \frac{1}{2}T_{i+1,j} + \frac{1}{2}T_{i,j+1}, \quad 0\leq i<j<n\\ T_{jj}&= \frac{1}{\lambda} + T_{j,j+1} , \quad 0\leq j<n\\ T_{i,n} &= \frac{n-i}{\lambda} , \quad 0\leq i < n\\ T_{nn}&=0\end{align} You can solve them by hand for small integers $n$ to compute the desired value $T_{00}$.

  • $n=1$: $T_{00} = 2/\lambda$.

  • $n=2$: $T_{00} = 3.5/\lambda$.

$\endgroup$
9
  • $\begingroup$ A simple lower bound on the expected time for $X$ to reach state $n$ is the starting average delay of $1/\lambda$ (for $Y$ to make the first move) and then the expected time for a Poisson process to move $n$ steps unhindered by $Y$, so $$ \frac{n+1}{\lambda}\leq T_{00}$$ $\endgroup$
    – Michael
    Jul 11, 2018 at 6:10
  • $\begingroup$ I think you've shifted $n$ by $1$ relative to the question. It says $X\gt n$, not $X\ge n$. (Though your version seems more natural; it might be preferable to change the question instead.) $\endgroup$
    – joriki
    Jul 11, 2018 at 6:14
  • $\begingroup$ @joriki : So I have. But solving one solves the other. My answer specifies what I solve for so I don't think there is any confusion. $\endgroup$
    – Michael
    Jul 11, 2018 at 6:15
  • 1
    $\begingroup$ @joriki Yep. Specifically, if $A_x, A_y$ are the arrival times of $X$ and $Y$ at $n$, I'm interested in the asymptotic growth (well, decrease) of $A_x / A_y$ as $n \to \infty$. Hopefully to be able to roughly estimate how close $X$ and $Y$ are going to "act" for some $n$. $\endgroup$
    – aellab
    Jul 11, 2018 at 12:55
  • 1
    $\begingroup$ To be more clear, I'd like to be able to find for example, some upper bound on for which $n$s is $A_x \leq 1.01A_y$. $\endgroup$
    – aellab
    Jul 11, 2018 at 13:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .