2
$\begingroup$

Consider simple random walk started at $1$ on the path $[0,M]$. Let $\tau_x$ be the time to reach $x$ and condition on the event $\tau_M < \tau_0$ (the walk hits $M$ before reaching $0$). Conditioned on this event, let $V_k$ be the number of visits to $k$ up to time $\tau_M$. What is $\mathbb E V_k$?

All we need is a bound independent of $M$. Something like there exists $C>0$ such that

$$\sup_{M >0 }\Bigl[ \max_{0< k < M} \mathbb E V_k \Bigr]< C.$$

$\endgroup$
  • $\begingroup$ Doesn't "the walk hits $M$ before reaching $0$" imply conditioning on $\tau_M<\tau_0$ and not $\tau_M<\tau_1$? $\endgroup$ – HMPanzo Dec 27 '16 at 20:46
3
$\begingroup$

To second Anthony Quas's answer, here's a simple way to calculate $\mathbb{E}V_k$. Notice that conditional on $\tau_M<\tau_0$ your walk will visit $k$ at least once. Once we are at $k$, the number of consecutive visits is a positive geometric random variable, since the walk is a Markov process. The parameter is $1-\mathbb{P}(V_k=1 | \tau_M<\tau_0)$, and therefore its expectation value is $$\mathbb{E}[V_k]=\frac{1}{\mathbb{P}(V_k=1 | \tau_M<\tau_0)} = \frac{\mathbb{P}(\tau_M < \tau_0)}{\mathbb{P}(\tau_k<\tau_0)\frac{1}{2}\mathbb{P}(\tau_{M-k}<\tau_0)},$$ since the walk has to visit $k$ before $0$, step to $k+1$, and then visit $M$ before returning to $k$. Since $\mathbb{P}(\tau_M < \tau_0) = 1/M$ (ballot problem) we find $$\mathbb{E}[V_k]= 2 k (1-k/M)$$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you so much for the nice and clean argument. Although the uniform bound doesn't hold, this appears to be sufficient for our purposes. $\endgroup$ – Matthew Junge Dec 28 '16 at 14:40
2
$\begingroup$

Surely you can't hope for a bound that's independent of $M$. Imagine that $M$ is huge and let $K\ll M$ be large. Then consider what happens after you first hit $M-K$. You're seeing approximately a simple symmetric random walk so it should take $K^2$ steps to reach $M$. There should be around $K$ of these at $M-K$.

Or are my heuristics way off?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Probably a more grown up way to say the same thing is to first fix $K$ and then choose a really large $M$ so that the conditioned random walk on $[M-2K,M]$ is so close to a simple symmetric random walk that it is very unlikely to do anything different within $K^2$ steps. Now the ssrw starting at $M-K$ visits that site $K$ times before hitting $M-2K$ or $M$. So the constant $C$ should exceed $K$ for an arbitrary $K$. $\endgroup$ – Anthony Quas Dec 28 '16 at 7:54

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.