0
$\begingroup$

I have the following problem on random walks:

Consider a $d$-dimensional symmetric random walk which starts at the origin at time $n=0$. Show that the walk has probability $1$ of returning infinitely often to a position already previously occupied.

This problem doesn't make much sense to me because we know that symmetric random walks are transient for $d\geq 3$. Since the random walk starts at the origin, we would show that the random walk returns to the origin infinitely often. Doesn't this contradict the fact that the random walk is transient, or am I missing something?

$\endgroup$
  • $\begingroup$ The problem says "a position already previously occupied," not necessarily the starting point. $\endgroup$ – user296602 Mar 5 '16 at 4:58
  • $\begingroup$ I see so we are asking for the probability that it returns to at least one of the previously occupied positions, not all of them $\endgroup$ – User112358 Mar 5 '16 at 4:59
  • $\begingroup$ The question is ambiguous. Are you asking to show that the random index set $$\{n\geqslant0\mid\exists k>n,\,X_k=X_n\}$$ is infinite, or that, with full probability, there exists some $n$ such that the random index set $$\{k\mid X_k=X_n\}$$ is infinite, or yet some other statement? $\endgroup$ – Did Mar 5 '16 at 16:31
0
$\begingroup$

Since the walk is symmetric, at each time $n$ there is a fixed probability $p = 1/(2d)$ of returning to the space you just came from. Thus we are in exactly a position to apply the following to $\tau =$ first time I visit a state I have already visited. ($k=1$ and $\epsilon = p$).

Theorem. If $\tau$ is a stopping time and there exists $k$ such that for all $n$ we have $P(\tau \leq n + k | \mathcal{F}_n) \geq \epsilon > 0$ then $E[\tau] < \infty$ and in particular $P(\tau < \infty) = 1$.

$\endgroup$
  • $\begingroup$ Do you have a source for this theorem? $\endgroup$ – User112358 Mar 5 '16 at 5:16
  • $\begingroup$ David Williams Probability with Martingales exercise E10.5. $\endgroup$ – nullUser Mar 5 '16 at 5:18
  • $\begingroup$ Hint: By induction show $P(\tau > nk) \leq (1-\epsilon)^k$ for $n=1,2,\ldots$. $\endgroup$ – nullUser Mar 5 '16 at 5:20
  • $\begingroup$ I can prove that, but I'm not sure how to see that proves the expectation is finite $\endgroup$ – User112358 Mar 5 '16 at 7:11

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.