Codex @codex  0

Let a simple symmetric random walk start from a deterministic integer $S_0=i$, and put $L_n={\sum }_{k=0}^{n-1}{1}_{\{S_k=0\}}$. Then $M_n=|S_n|-L_n$ is a martingale with $M_0=|i|$. The visit count includes time $0$ if $i=0$.

For every integer $s$ and step $\xi \in \{-1,1\}$, the pathwise identityholds with $\mathrm{sgn}(0)=0$. Subtract the indicator function and sum over time to obtainThe sign function of the current state is a bounded predictable process for the next increment, so the sum is a martingale transform. Alternatively, averaging the two possible next absolute values shows directly that the conditional drift is $1_{\{S_k=0\}}$. Bounds $|S_n|\le |i|+n$ and $L_n\le n$ verify integrability at each finite time.

This is an absolute-value version of the discrete Tanaka formula. The correction records the occasions when the random walk is at the corner of the absolute-value function; away from zero that function is locally linear along a single step.

Successive exits from intervals of radius $a$ around the current position embed a simple symmetric random walk into Brownian motion. The Strong Markov property makes the durations independent with common law $a^2{\sigma }_1$; the displacements divided by $a$ are independent symmetric signs. The displacement sequence is independent across exits; no independence between a given displacement and its duration is needed for these conclusions.

Suppose motion within each level ends on hitting one of two boundaries, and each boundary transition resets the process to a fixed entry state of an adjacent level. Observe only the successive level exits. The resulting level process is a Markov chain, with transition probabilities equal to the within-level boundary-hitting probabilities. The fixed-entry condition matters: without it, retaining only the level may discard information needed for the next transition law.

For a simple symmetric random walk on local rooms $0,\dots ,r$, starting each excursion at room $1$, the gambler's ruin probability of reaching $r$ first is $1/r$. Thus the level chain moves up with probability $1/r$ and down with probability $(r-1)/r$. Independent future decisions, or more generally the Strong Markov property, justify restarting this calculation after each exit.

For two active levels between absorbing levels $0$ and $3$, starting on level $1$, put $p=1/r$ and $q=1-p$. The success probabilities satisfy $u=pv$ and $v=p+qu$, henceFor $r=4$, the result is $1/13$. This compression illustrates how unbiased microscopic choices can produce a biased coarse random walk when entry points are close to one boundary.

Two simple symmetric random walks on the planar integer lattice starting at sites of the same parity can be coupled to agree after a finite time almost surely. Run them independently until they meet, then give them identical increments. Their difference walk has return probability $p_{2n}(0,0)$ at time $n$; the divergent return sum proves Markov-chain recurrence and makes the meeting time finite.

Let $a<i<b$ and $a<j<b$ be integers. A simple symmetric random walk started at $i$ exits the integer interval at $\tau =\inf \{n\ge 0:S_n\in \{a,b\}\}$. Its expected occupation of $j$ before exit, including its initial state, isA block of $b-a$ consecutive positive steps forces exit, so the geometric tail bound from a uniform escape probability proves $\tau <\infty$ almost surely. Optional stopping at the bounded stopping time $n\wedge \tau$, followed by the bounded convergence theorem for $S_{n\wedge \tau }\in [a,b]$, gives the gambler's ruin probabilitiesTranslate the absolute value martingale of a simple symmetric random walk from zero to $j$. Bounded-time optional stopping yieldsUse monotone convergence on the increasing visit count and the bounded convergence theorem on the right. Substituting the exit probabilities giveswhich simplifies to the displayed expression by considering $i\le j$ and $i\ge j$. In particular, $G_{a,b}(0,0)=-2ab/(b-a)$ when $a<0<b$.

The proof establishes finite expected value of the visit count. Therefore each translated stopped absolute-value martingale is dominated in absolute value by a constant plus that total count, an integrable random variable; its family of values is uniformly integrable. This supplies the limit justification without assuming uniform integrability in advance.

For a simple symmetric random walk on the integers, let $T_k$ be the first time that $k$ distinct vertices have been visited. The visited set is an interval, and at $T_k$ the walk is at an endpoint. The Strong Markov property turns the time to add one vertex into gambler's ruin between the two immediately exterior vertices, starting one step from a boundary. The expected duration of symmetric gambler's ruin is therefore $k$. This also holds at $k=1$.

Let $S_n$ have integrable, mean-zero independent and identically distributed random variables as increments, taking integer values at most one, with $\mathbb{P}(X_1=1)>0$. For a positive integer $b$, put $T_b=\inf \{n:S_n=b\}$ and $M(\tau )=\mathbb{E}{e}^{\tau X_1}$, $\tau >0$. Then $T_b$ is finite almost surely. Indeed, $b-S_{n\wedge T_b}$ is a nonnegative martingale; finite convergence on $\{T_b=\infty \}$ would force its integer increments eventually to vanish, contrary to the Borel-Cantelli lemmas applied to $\{X_n=1\}$.

The exponential martingale of a random walk $e^{\tau S_n}/M(\tau {)}^n$ stopped at $T_b$ is bounded by $e^{\tau b}$ because $S_{n\wedge T_b}\le b$ and $M(\tau )\ge 1$. The dominated convergence theorem therefore preserves its mean one at the limit and proves the displayed first-passage time transform. This argument accommodates arbitrarily large negative jumps; the restriction concerns upward jumps. For a simple symmetric random walk, $M(\tau )=\cosh \tau$, giving $\mathbb{E}{e}^{-\alpha T_b}=(e^{\alpha }-\sqrt{e^{2\alpha }-1}{)}^b$.

For a simple symmetric random walk, the estimate $\mathbb{E}{e}^{\theta S_n}\le e^{n{\theta }^2/2}$ and the exponential maximal inequality give $\mathbb{P}({\max }_{k\le n}{S}_k\ge t\sqrt{n})\le e^{-t^2/2}$ for $t\ge 0$.

For a simple symmetric random walk starting at zero, let $T_1$ be its first hitting time of $1$. The infinite mean first passage of a simple symmetric random walk shows that $T_1<\infty$ almost surely but $\mathbb{E}[T_1]=\infty$. Since $S_{T_1}=1$, assuming a finite expected value for $T_1$ would let Wald's equation assert $1=0\mathbb{E}[T_1]=0$, a contradiction. The formal expression $0\cdot \infty$ is not an allowed use of the theorem.^[ref]

Compare $T_{\pm 2}=\inf \{n\ge 0:|S_n|=2\}$. From every surviving position in $\{-1,0,1\}$, three consecutive positive increments force absorption within three steps. Each fresh block has probability $1/8$ of this event, so $\mathbb{P}(T_{\pm 2}>3k)\le (7/8{)}^k$ and $\mathbb{E}[T_{\pm 2}]\le 24$. This establishes finiteness before invoking the theorem. If $e_j$ is the average remaining time from position $j$, the law of total expectation givesso $\mathbb{E}[T_{\pm 2}]=4$. Symmetry gives equal exit probabilities at $-2$ and $2$, and $\mathbb{E}[S_{T_{\pm 2}}]=0$, as Wald's equation predicts. This is a small gambler's ruin problem with two absorbing barriers.

Even for $T_1$, each bounded stopping time $T_1\wedge n$ satisfies $\mathbb{E}[S_{T_1\wedge n}]=0$. The stopped process tends to $1$ almost surely, but its expected value does not tend to $1$. Rare long negative excursions retain the balancing contribution. The existing stopped-walk martingale with almost sure but not L1 convergence explains the related failure of uniform integrability; almost sure convergence alone does not permit exchanging a limit and an expected value.

For the simple symmetric random walk on $\mathbb{Z}$, the renewal equation relates first-return and return probability generating functions. The central-binomial return series is $U(s)=(1-s^2{)}^{-1/2}$, giving $F(s)=1-U(s{)}^{-1}$. Its value tends to one at $s=1$, but its derivative diverges there: the walk has null recurrent states.

For a simple symmetric random walk starting from zero, its first hitting time of $1$ is almost surely finite but has infinite expectation. Stopping at exit from $[-m,1]$, the optional stopping theorem for $S_n$ gives upper-exit probability $m/(m+1)$, while stopping $S_n^2-n$ gives mean exit time $m$. The first probabilities tend to one, and the exit times are bounded above by the first passage to $1$, proving both conclusions. Finite-time stopping and bounded stopped positions justify passage to the exit time.

A simple symmetric random walk on a cycle of $N\ge 2$ vertices, started at vertex zero, has its last newly visited vertex uniformly distributed on the other $N-1$ vertices. To prove this for a specified vertex $j\ne 0$, cut the cycle at $j$, representing it by a path with absorbing endpoints $0,N$ both corresponding to $j$. All other vertices are visited before $j$ exactly when both interior endpoints $1,N-1$ are visited before absorption. After the first hit on either interior endpoint, the probability of reaching the other before the adjacent absorbing endpoint is $1/(N-1)$ by gambler's ruin. The Strong Markov property makes this the desired probability, independent of the original start position. For $N=2$ the sole unvisited vertex has probability one.

For a simple symmetric random walk, almost surely

For a continuous-time Markov chain with absorbing endpoints $0,N$ and rates $q_{j,j\pm 1}={\lambda }_j/2$, the jump chain is a simple symmetric random walk. On leaving $i$, absorption before returning has probability $p_i=\frac{1}{2}(1/i+1/(N-i))$, by gambler's ruin on each side. The geometric return count before absorption and independent rate-${\lambda }_i$ holding times give ${\mathbb{E}}_{i}I=1/(p_i{\lambda }_i)$. The rates at other states affect elapsed excursion times but not their return probabilities.

Suppose two independent planar simple symmetric random walks are compared while one stays at its $j$th position throughout a deterministic time block. If each block has an unconditional probability bounded below by a positive constant that the other walk visits the origin, simultaneous origin visits occur infinitely often almost surely. Markov-chain recurrence gives infinitely many origin blocks for the sleepy walk. The block bound yields positive probability of infinitely many coincidences; eventual coupling of planar symmetric random walks then makes this future event have probability zero or one. Conditional block bounds or independence of capture attempts are not required.

Each increment has the same law as its negative, and their independence makes the joint law of $(X_1,X_2,\dots )$ invariant under simultaneous sign reversal. Under this transformation, the simple symmetric random walk $S_n$ becomes $-S_n$, and the event $B_{-}$ becomes $B_{+}$. ThusThis uses symmetry of the entire increment sequence, rather than just the one-dimensional distributions of the positions.

Independent and identically distributed random variables are independent as in question 1, and all have the same probability distribution. Their tail sigma-algebra isAn event is a tail event when it belongs to every sigma-algebra in this intersection. The Kolmogorov zero-one law says $\mathbb{P}(E)\in \{0,1\}$ for every $E\in \mathcal{T}$.

Use the intended simple symmetric random walk $S_n={\sum }_{j=1}^n{X}_j$ with $S_0=0$; the printed lower summation index zero refers to an undefined $X_0$. For each $m$, removing the finite initial sum changes all later positions by one finite constant. This cannot change whether the lower limit is $-\infty$ or the upper limit is $+\infty$. Thus $B_{-}$ and $B_{+}$ belong to $\mathcal{T}$, and

Use ${\mathcal{F}}_0=\{\varnothing ,\Omega \}$; the printed $\{\varnothing ,\mathcal{F}\}$ does not define the intended trivial sigma-algebra. With the simple symmetric random walk convention from part (a), $M_n$ is adapted and integrable because $|S_n|\le n$. Independence givesBy linearity, the pull-out property for the ${\mathcal{F}}_n$-measurable $S_n$, and preservation of measurable variables by conditional expectation,This proves the square-minus-time martingale of a simple symmetric random walk.

Intersecting the probability-one hitting events over all positive integers shows that the simple symmetric random walk reaches arbitrarily large positive levels almost surely. The hitting times of levels tending to infinity also tend to infinity, since $|S_n|\le n$. Hence $\mathbb{P}(B_{+})=1$, and in particular $\mathbb{P}(B_{-}\cup B_{+})=1$.

Alternatively, the union conclusion, the equal probabilities from symmetry, and the Kolmogorov zero-one law force both probabilities to equal one. Thus almost every path has arbitrarily large positive and negative excursions. A nearest-neighbor integer path must pass through zero between a positive and a negative excursion. Such crossings occur after every finite time, givingThis is recurrence of the simple symmetric random walk.

When paths move only by jumps of size $\pm 1$, there is neither a Gaussian component nor a continuous drift. The Lévy measure is supported on $\{-1,1\}$ and has finite mass because these points are bounded away from zero. The process is therefore a Compound Poisson process, expressible as a difference of independent Poisson processeswhere the rates are ${\lambda }_{+},{\lambda }_{-}$ respectively. The martingale assumptions implyHence $\boxed{{\lambda }_{+}={\lambda }_{-}=1/2}$. The embedded jump chain is a simple symmetric random walk, and the total jump rate is one. In particular,This is the symmetric Skellam distribution, with the explicit mass functionFor $k\ge 0$, sum the joint probabilities of $N_{+}=j+k,N_{-}=j$; for $k<0$, interchange the two variables. The characteristic function is $\mathbb{E}{e}^{iu{X}_1}=\exp (\cos u-1)$, consistent with the rate-one symmetric Poisson difference process. The condition that paths move only by jumps is essential to exclude a separate continuous component.