2
$\begingroup$

I am looking for a general formula for hitting times in a standard birth-and-death chain. I'm absolutely convinced that I've seen a paper with such a formula in it in the past, but I cannot for the life of me find it now. The formula looks something like this:

$$ E_{i-1}(\tau_i) = \prod_{j < i} \frac{q_{j,j+1} ... }{...}. $$

I've looked through any papers on birth–death process which seem at all relevant. These include the following.

  • Ding, Lubetzky, Peres; Total Variation Cutoff in Birth-and-Death Chains
  • Fill; The Passage Time Distribution for a Birth-and-Death Chain
  • Smith; The Cutoff Phenomenon for Random Birth and Death Chains
  • Zhang; Moments of First Hitting Times for Birth–Death Processes on Trees

I've even tried to use the formula for my own research in the past. Try as I might, I can't find it now.

If anyone knows the reference, that would be much appreciated!

Improve this question
$\endgroup$
2
  • $\begingroup$ Have you looked at doi.org/10.1007/s10959-015-0659-z? $\endgroup$
    – Steve Huntsman
    Commented May 20, 2021 at 13:07
  • $\begingroup$ @SteveHuntsman I had not see that, no. Unfortunately, it doesn't provide an expression the type of which I desired. But it looks interesting all the same and I have saved it to my collection of references, thanks! $\endgroup$
    – Sam OT
    Commented May 20, 2021 at 14:46

2 Answers 2

Reset to default
3
$\begingroup$

There is a discussion of birth an death chains in [1]; see page 27 for the hitting time formulas. See also [2], [3], [4].

[1] Markov Chains and Mixing Times: Second Edition by Levin and Peres, with contributions by Wilmer, https://bookstore.ams.org/mbk-107 https://darkwing.uoregon.edu/~dlevin/MARKOV/mcmt2e.pdf

[2] Chen, Mu-Fa. "Speed of stability for birth-death processes." Frontiers of Mathematics in China 5, no. 3 (2010): 379-515.

[3] Fill, James Allen. "On hitting times and fastest strong stationary times for skip-free and more general chains." Journal of Theoretical Probability 22, no. 3 (2009): 587.

[4] Palacios, J. and Tetali, P., 1996. A note on expected hitting times for birth and death chains. Statistics & Probability Letters, 30(2), pp.119-125.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Some nice references, thanks Yuval :) Somewhat amazingly, as well-known and standard as a reference it is, I think your LPW book might actually be the particular reference I was thinking of! I'd been looking through research papers not (text)books. Thanks very much! $\endgroup$
    – Sam OT
    Commented May 29, 2021 at 8:00
3
$\begingroup$

Let use compute $E_0(\tau_1)$, the general expression follows by shift. For simplicity I assume that $|X_{i+1}-X_i|=0$, ie that the probability to stay put vanishes (one can also treat the general case by essentially the method described below). Let $\omega_i=P(X_1=i+1|X_0=i)$.

Write, starting at $X_0=0$, $$\tau_1=1_{X_1=1}+1_{X_1=-1}(1+ \tau_0'+\tau_1')$$ where $\tau_0',\tau_1'$ are of the same law as $\tau_0$ starting at $-1$ and $\tau_1$ starting at $0$.

Let $\omega_i$ be the probability to jump right at $i$. Taking expectations and rearranging you get $$ E_0(\tau_1)=1/\omega_0+\rho_0 E_{-1}(\tau_0),$$ where $\rho_i=(1-\omega_i)/\omega_i$.

Now you can iterate: $$E_0(\tau_1)=1/\omega_0+\rho_0/\omega_{-1}+\rho_0\rho_{-1} E_{-2}(\tau_{-1})$$

So $$ E_0(\tau_1)=\sum_{i=0}^\infty \frac{1}{\omega_{-i}} \prod_{j=0}^{i-1} \rho_{-j}$$ (If the right side diverges, then the expectation is indeed infinite).

These formulae appear in the study of (one dimensional) random walk in random environment. Look up my lecture notes (Springer LNM) for an introduction. This is equation (2.1.14) there.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks, Ofer. Kind of you to write this out. +1 || Evidently I wasn't sufficiently clear in my question: I was really after the reference. It has more than just that particular formula in, which is pretty easy to derive as you point out. Although, given that I can't find it, I am starting to wonder if the paper only existed in my imagination!---maybe it was more my memory of a combination of results from multiple papers... Still, I am grateful for your clearly laid out derivation of the particular formula :) $\endgroup$
    – Sam OT
    Commented May 21, 2021 at 15:15
  • 1
    $\begingroup$ It is equation 2.1.14 in the lecture notes I mentioned, which are quotable. Is it not what you asked for? $\endgroup$
    – ofer zeitouni
    Commented May 22, 2021 at 10:37
  • $\begingroup$ It certainly is the equation I was referencing. But I was asking for the paper that I'd seen it in. Your lecture notes, as helpful a reference as they are, are not this paper. This paper has other relevant stuff in it too, thus wanting the reference. Deriving the formula is quite straight forward, as you desmonstrate above. The reference to RW in RE is very helpful, though. It may have been in such a paper that I saw the reference. I'll keep that in mind and post here if I find the paper in the future! :) $\endgroup$
    – Sam OT
    Commented May 22, 2021 at 14:24
  • $\begingroup$ Good luck. I thought you needed a reference, not THE reference :-). $\endgroup$
    – ofer zeitouni
    Commented May 22, 2021 at 14:27
  • $\begingroup$ Thank you all the same! :) -- sorry the question wasn't clearer $\endgroup$
    – Sam OT
    Commented May 23, 2021 at 20:25

You must log in to answer this question.

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