In a previous question of mine, I asked for the probability distribution of an agent taking a biased walk on the positive integers (with a reflecting boundary at the origin):

Probability distribution for the position of a biased random walker on the positive integers

Here, for a $+1$ step for the walker has probability $p$, for a $-1$ step (away from the origin) the walker has probability $q$, and since $(p+q) \leq 1$, we allow the walker to stay in place with probability $r = 1 - (p+q)$. In order to prevent this walk from becoming transient, we set $p \leq q$.

By solving the relation:

$P(X=n)= p P(X=n-1) +(1-p-q) P(X=n) + q P(X=n+1)$

The user Henry provided a rather nice solution for the stationary distribution that sums to unity and matches up will with simulations with ~$10^7$ or more steps:

$P(X=n) = \left(\frac{p}{q}\right)^n \left(1-\frac{p}{q}\right)$

My question is as follows: Say we initialize our walking agent at some position $0 \leq i < M$, and we're interested in the average hitting time at position $M$. Say we also calculate some sum:

$S = \sum_{n=M}^{\infty} \left(\frac{p}{q}\right)^n \left(1-\frac{p}{q}\right)$

Considering that the stationary distribution $P(X=n)$ is a smoothly decreasing analytic function, can we use $S$ to say anything about the average hitting time, $H(M)$ for the walker agent at position $M$?

  • $\begingroup$ Why do you think that the stationary distribution is merely approximated? It satisfies detailed balance everywhere, including the exchange between $X=0$ and $X=1$, since you defined the behaviour at the origin such that the transition $0\to1$ has the same probability as all other rightward transitions. $\endgroup$ – joriki Dec 15 '12 at 19:32
  • $\begingroup$ @joriki So I want to be very careful here not to be critical of Henry's answer, and stress that the problem is my understanding. More specifically, I'm having difficulty understanding why the stationary distribution, as stated, doesn't underestimate the probability of the walker being at the origin, since, while it is true that the rightward probability remains the same, the probability of staying at the origin is increased by $q$. $\endgroup$ – PlacidLake Dec 15 '12 at 19:37
  • $\begingroup$ Are you familiar with detailed balance? This is a sufficient condition for the distribution to be stationary. On the intuitive level on which you're arguing, you have to take into account that the reflection raises the probability not just at the origin, but everywhere to its right. These things can seem counterintuitive; I think the best way to get a feel for them is to try some small examples, e.g. find the stationary distribution for a chain of three states, then take one away and see what happens to the other two. $\endgroup$ – joriki Dec 15 '12 at 19:43
  • $\begingroup$ @joriki Actually, it's also true that, for Henry's solution, P(X = 0) = (1-p)*P(X = 0) + q*P(X = 1), isn't it? I calculated this incorrectly previously due to sloppiness on my part. I am satisfied and will remove the statement that this stationary distribution is an "approximation". Thanks! $\endgroup$ – PlacidLake Dec 15 '12 at 19:50
  • $\begingroup$ @joriki You're right, these things are counter intuitive, but as long as the relevant recurrence relations are satisfied, so am I. $\endgroup$ – PlacidLake Dec 15 '12 at 19:53

No, you can't say anything about the hitting time from the stationary distribution. Consider a random walk in which the state remains unchanged with probability $1-s$ and behaves according to the present random walk with probability $s$. Then the stationary distribution is the same, but all expected times are divided by $s$ You can make $s$ arbitrarily small and thus make the expected times arbitrarily large without changing the stationary distribution.

  • $\begingroup$ This is a fair answer, but I was sort of interested in the case where $s \approx 1$, though I of course failed to specify this. $\endgroup$ – PlacidLake Dec 16 '12 at 11:19
  • $\begingroup$ Actually, how the stationary distribution $\pi$ constrains the distribution of hitting times is not obvious (to me). Scaling is irrelevant, as your argument shows, but other characteristics of $\pi$ might be encoded in the hitting times (note that, by contrast, mean return times fully determine $\pi$). (Oh, and +1 from me, of course. @OP: why not upvote an answer you accepted?) $\endgroup$ – Did Dec 16 '12 at 11:32
  • $\begingroup$ @did I have now done so :) But yes, I feel that there should be some kind of relationship between the stationary distribution and hitting times in the limit $s \to 1$, and I'm curious what might be known about it. That said, I'm not suggesting there must be such a relationship. $\endgroup$ – PlacidLake Dec 16 '12 at 12:50

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.