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?

  • $\begingroup$ The problem says "a position already previously occupied," not necessarily the starting point. $\endgroup$
    – user296602
    Mar 5, 2016 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, 2016 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, 2016 at 16:31

1 Answer 1


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$.

  • $\begingroup$ Do you have a source for this theorem? $\endgroup$
    – User112358
    Mar 5, 2016 at 5:16
  • $\begingroup$ David Williams Probability with Martingales exercise E10.5. $\endgroup$
    – nullUser
    Mar 5, 2016 at 5:18
  • $\begingroup$ Hint: By induction show $P(\tau > nk) \leq (1-\epsilon)^k$ for $n=1,2,\ldots$. $\endgroup$
    – nullUser
    Mar 5, 2016 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, 2016 at 7:11

You must log in to answer this question.

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