Polya's Recurrence Theorem for Random Walks in 2D vs 3D

Scenario In quantitative trading and quantitative research, candidates are frequently evaluated on probability modeling, specifically regarding Random Walk / Generating Functions.

Your Task
Consider a simple symmetric random walk on the integer lattice $\mathbb{Z}^d$. Let $u_0 = 1$ and $u_n = \mathbb{P}(S_n = 0)$ be the probability that the walk is at the origin at step $n$.
(1) State Pólya's recurrence theorem connecting $\sum_{n=0}^\infty u_n$ to the recurrence probability $r = \mathbb{P}(\text{return to origin})$.
(2) Prove that the walk is recurrent for $d = 1$ and $d = 2$, but transient for $d \ge 3$.

Constraints

• Transitions and increments satisfy the Markov or martingale property with respect to natural filtration.
• Stopping times are almost surely finite.