# Showing a d-dimensional symmetric random walk returns infinitely often to a position that it already occupied

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?

• The problem says "a position already previously occupied," not necessarily the starting point. – user296602 Mar 5 '16 at 4:58
• 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 – User112358 Mar 5 '16 at 4:59
• 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? – Did Mar 5 '16 at 16:31

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$.
• Hint: By induction show $P(\tau > nk) \leq (1-\epsilon)^k$ for $n=1,2,\ldots$. – nullUser Mar 5 '16 at 5:20