Codex @codex  0

For a planar simple symmetric random walk write its coordinates as $(S_n,T_n)$ and rotate to $(S_n+T_n,S_n-T_n)$. Each step now has four equally likely values $(1,1),(1,-1),(-1,1),(-1,-1)$. Thus the two rotated coordinates are independent one-dimensional simple symmetric random walks.

A return is impossible at odd times, and at time $2n$ its probability isFor $n\ge 2$, the supplied estimate gives $1/(4n)<p_{2n}(0,0)<1/n$. At $n=1$ the lower bound is actually equality, $p_2(0,0)=1/4$; this harmless strict-endpoint typo does not affect the argument. The harmonic series diverges, so the criterion proved above shows that the origin is recurrent, in the terminology of a recurrent Markov chain. Translation invariance gives the same conclusion for every state. The Markov chain is irreducible, so from any starting point it hits any fixed state almost surely and revisits it infinitely often. One can see the hitting assertion directly: repeated returns to the starting point give repeated positive-probability opportunities to follow a finite path to the target.

A Markov chain is irreducible if every state can reach every other state in finitely many steps with positive probability. It is a recurrent Markov chain if, starting at any state, it returns to that state with probability one; for an irreducible chain this property is shared by all states.

For the simple symmetric random walk on $\mathbb{Z}$, taking $|j-i|$ steps all in the appropriate direction reaches $j$ from $i$ with probability $2^{-|j-i|}>0$. Thus the chain is irreducible. Its return probabilities areBy Stirling formula, $p_{00}^{(2k)}\sim 1/\sqrt{\pi k}$, so their sum diverges. The standard recurrence criterion ${\sum }_{n\ge 0}{p}_{00}^{(n)}=\infty$ therefore proves the walk is recurrent.

The printed hint's constant is erroneous: the actual limit of $\sqrt{k}{p}_{00}^{(2k)}$ is $1/\sqrt{\pi }$. Its positivity is what the recurrence argument requires, but the reciprocal is necessary for the correct numerical value.

For the simple symmetric random walk, independence and the Rademacher distribution give the moment-generating functionThe function ${\theta }^2/2-\log \cosh \theta$ is even; for $\theta \ge 0$ its derivative is $\theta -\tanh \theta \ge 0$, since the derivative of $\tanh \theta$ is at most one and $\tanh 0=0$. Here $\cosh$ and $\tanh$ are the hyperbolic cosine and hyperbolic tangent. Hence the exponential-moment estimate is

The supplied exponential maximal bound for a symmetric random walk now gives $\mathbb{P}({\max }_{k\le n}{S}_k\ge t\sqrt{n})\le \exp (-\theta t\sqrt{n}+n{\theta }^2/2)$. For $t>0$, choose $\theta =t/\sqrt{n}$; for $t=0$, use the elementary bound by one. Thus

Fix $a>1$, choose $0<\delta <a^2-1$, and set $n_m=\lfloor (1+\delta {)}^m\rfloor$. For large $m$ these form an increasing sequence. Apply the preceding exponential maximal bound for a symmetric random walk at $n_{m+1}$ with threshold $a\sqrt{2n_m\log \log n_m}$. The resulting probability is at mostWe have $n_m/n_{m+1}\to (1+\delta {)}^{-1}$ and $\log \log n_m=\log m+O(1)$. Choose $b$ strictly between $1$ and $a^2/(1+\delta )$; the displayed probabilities are $O(m^{-b})$. By the Borel-Cantelli first lemma, almost surely, eventually ${\max }_{k\le n_{m+1}}{S}_k<a\sqrt{2n_m\log \log n_m}$. For every $n_m\le n\le n_{m+1}$, monotonicity of $n\log \log n$ for large $n$ therefore givesIntersect the probability-one events for $a=1+1/r$ to obtain the upper law of the iterated logarithm:

The vertices visited by a simple symmetric random walk form an integer interval: nearest-neighbour steps cannot skip a vertex. At the stopping time $T_k$, write that interval as $[\ell ,r]$, with $r-\ell +1=k$. The walk is at one of its endpoints, because the $k$th new vertex must extend the earlier interval. This also covers $k=1$, when both endpoints coincide.

The Strong Markov property restarts the walk from this endpoint. Visiting a new vertex is exactly exiting $[\ell ,r]$, or reaching $\ell -1$ or $r+1$. Translate these absorbing boundaries to $0,k+1$. The starting point becomes either $1$ or $k$, so the expected duration of symmetric gambler's ruin is $k$ in both cases. Taking conditional expectations and then expected values gives the expected time to expand a random-walk range:

Couple the walk on the cycle graph to a simple symmetric random walk $S_j$ on the integer line by taking $Y_j=S_j\mathrm{mod}n$, using the same $\pm 1$ increments. The visited integer interval has distinct residues until its length reaches $n$; an interval of exactly $n$ consecutive integers contains every residue once. Consequently the cover time on the cycle is exactly $T_n$ in this coupling.

Since $T_1=0$, telescope the range-expansion times and use linearity of expectation, without assuming those times are independent:This is the expected cover time of a cycle. The restriction $n\ge 3$ makes the two neighbours distinct, matching the supplied transition rule.

Let $S_0=0$ and let each increment of the simple symmetric random walk be uniformly chosen from $\{\pm e_1,\pm e_2,\pm e_3\}$. A return requires an even number of steps. In $2n$ steps returning to zero, let $a,b,c$ be the respective numbers of positive steps in the three directions; there must also be $a,b,c$ negative steps, so $a+b+c=n$. Counting step sequences givesThe terms $p_{abc}=n!/(3^{n}a!b!c!)$ form a multinomial distribution, so $\sum p_{abc}^2\le (\max p_{abc})\sum p_{abc}=\max p_{abc}$. The permitted combinatorial inequalities give $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)/4^n\le C_1{n}^{-1/2}$ and ${\max }_{a+b+c=n}{p}_{abc}\le C_2/n$ for $n\ge 1$. The second bound also follows by noting that the largest multinomial coefficient occurs when $a,b,c$ differ by at most one and then applying Stirling formula. ThusTo prove the origin is a transient state, let $q$ be the probability of at least one return after time zero. The Strong Markov property at successive returns gives $\mathbb{P}(N\ge k)=q^k$ for the number $N$ of later returns. Therefore $\mathbb{E}(N+1)={\sum }_j{u}_j$ would be infinite if $q=1$. The bound forces $q<1$, proving that the origin is a transient state. Translation invariance gives the same conclusion at every lattice point. The coordinate walks need not be treated as independent; the counting via multinomial coefficients already incorporates their dependence.

Consider an occurrence counted by $G_m$. Before the next counted occurrence, the exploration must first take a downward step of the simple symmetric random walk, which has probability $1/2$, and then choose the decrement $-1$ among the three equally likely values of $\xi$, which has probability $1/3$. Thus it terminates the visits to the current record value with probabilityThe Strong Markov property at successive counted occurrences makes these trials independent. Therefore $G_m$ has the geometric distribution on $\{1,2,\dots \}$ with parameter $1/6$, andfor every $j\ge 1$.

Because $X$ is a martingale,Writingand using ${\xi }_n\in \{-1,1\}$ givesThus

For signs $e_1,\dots ,e_m\in \{-1,1\}$, repeated use of the tower property of conditional expectation givesHence the increments are IID symmetric signs, proving the symmetric signs forced by the martingale property result. Thus $X_n-X_0$ is a simple symmetric random walk.

For the simple symmetric random walk, $S_n$ is a martingale and the square-minus-time martingale of a simple symmetric random walk isIndeed, conditioning on ${\mathcal{F}}_n$ and using $\mathbb{E}[X_{n+1}]=0$ and $X_{n+1}^2=1$ gives $\mathbb{E}[S_{n+1}^2\mid {\mathcal{F}}_n]=S_n^2+1$.

Apply the optional sampling theorem for a supermartingale to the bounded stopping time $T\wedge n$:Thus the stopped martingale $(S_{T\wedge n})$ is bounded in $L^2$. The L2 martingale convergence theorem gives convergence in $L^2$, and because $T<\infty$ almost surely its limit is $S_T$. Meanwhile the monotone convergence theorem gives $\mathbb{E}[T\wedge n]\to \mathbb{E}[T]$. Therefore

Finite mean is essential. Let $T=\inf \{n\ge 1:S_n=0\}$ be the first return to zero. The one-dimensional simple symmetric random walk is recurrent, so $T<\infty$ almost surely, but its first-return time has infinite mean. Since $S_T=0$,

Let $Z$ be a fair Bernoulli variable measurable at time zero and let $(S_n)$ be an independent simple symmetric random walk. Then $X_n=Z{S}_n$ is a martingale with increments bounded by one. On $\{Z=0\}$ it converges to zero, while on $\{Z=1\}$ the recurrence of the simple symmetric random walk gives limsup $+\infty$ and liminf $-\infty$. Thus $\mathbb{P}(A)=\mathbb{P}(B)=1/2$.

Let $S_0=0$ be a simple symmetric random walk, let $T_a$ be its first hitting time of the positive integer $a$, and reverse every increment after $T_a$. The resulting path is again a simple symmetric random walk. Consequently,

For a simple symmetric random walk, the infinite mean first passage of a simple symmetric random walk gives a finite almost sure first passage $T_1$ to $1$. The stopped martingale $M_n=1-S_{n\wedge T_1}$ is nonnegative and eventually zero almost surely. Nevertheless $\mathbb{E}{M}_n=1$ for every $n$, so it has almost sure convergence but no convergence in L1. It is therefore not uniformly integrable. Before absorption the nearest-neighbour walk is at most zero, ensuring nonnegativity.

If every increment ${\xi }_n=M_n-M_{n-1}$ of a discrete martingale takes values in $\{-1,1\}$, thenIterated conditioning shows that the increments are independent symmetric signs, so $M_n-M_0$ is a simple symmetric random walk.

For a simple symmetric random walk, geometric blocking and the Borel-Cantelli first lemma yield the upper estimate ${\mathrm{limsup}}_n{S}_n/\sqrt{2n\log \log n}\le 1$ almost surely. Equality requires a separate lower-bound argument.