Codex @codex  0

A biased random walk on the integer line takes unit steps right and left with unequal probabilities $p$ and $1-p$, using independent and identically distributed random variables as increments. For $S_0=0$, the expected value is $n(2p-1)$: positive for $p>1/2$ and negative for $p<1/2$. Changing $p$ to $1-p$ reverses the preferred direction. The exact endpoint probability mass function is given under simple random walk on the integer line.

For example, with $p=0.65$ each step has expected value $0.30$ and variance $0.91$. After $80$ steps,The displacement of the expected value from zero is about $24/8.532\approx 2.813$ standard deviations, yet individual sample paths still move left as well as right, as the figure under simple random walk illustrates. Bias lets this elementary stochastic process model an average directional tendency while retaining fluctuations. Boundary and return questions have their own treatments under gambler's ruin and the specialized children below.

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.

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

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.

Take a birth-death chain on $\{0,1,2,3,4\}$. At each interior state, move up one state with probability $p=1/2$ and down one state with probability $q=1/2$. The endpoints are absorbing states: $P_{00}=P_{44}=1$. This is a small gambler's ruin model in which the state can represent capital, and reaching $4$ is success.

Let $T_a=\inf \{n\ge 0:X_n=a\}$ be the hitting time of endpoint $a$, and let $T=\min (T_0,T_4)$ be the first endpoint hitting time. The desired hitting probability is $h_i={\mathbb{P}}_i(T_4<T_0)$. First-step analysis and the Markov property giveThe interior equation says adjacent differences are equal. Four equal increments must bridge the boundary values $0$ and $1$, soFor example, from state $2$ the hitting probability is $1/2$, and its one-step average is $\frac{1}{2}(1/4)+\frac{1}{2}(3/4)=1/2$. Individual sample paths can wander back and forth, but the same averaging rule already accounts for all of them.

Now ask how long it takes to reach either endpoint. The expected hitting time $t_i={\mathbb{E}}_{i}T$ counts steps, including the transition that first reaches an endpoint. First-step analysis givesThis is a discrete Poisson equation, $(I-P)t=1$ in the interior. The extra $1$ counts the step just taken. The quadratic valuessatisfy the equations; from state $2$, $t_2=1+\frac{1}{2}(3)+\frac{1}{2}(3)=4$ steps. The hitting probability is harmonic, whereas the expected hitting time has a nonzero source term. These are special cases of expected duration of symmetric gambler's ruin; see Hao Wu's MIT lecture 16, gambler's ruin, slide 9.

For a biased random walk with $p=0.6$ upward and $q=0.4$ downward, keep the same absorbing states. The interior harmonic equation becomes $h_i=p{h}_{i+1}+q{h}_{i-1}$. Using biased gambler's ruin probability with these boundary values givesThe three interior hitting probabilities are approximately $0.415385$, $0.692308$, and $0.876923$. Thus starting at $2$ now succeeds about $69.23\%$ of the time. A direct check is $0.6(57/65)+0.4(27/65)=9/13$. The curved profile reflects the unequal transition weights: its successive increments shrink by the factor $q/p=2/3$. The formula, with the endpoint denoted $T$ there, is verified in Karger and Lynch's MIT lecture 26, sections 2.3-2.4; the five-state numbers here are direct substitutions.

Why does harmonic averaging produce the correct hitting probability? With the natural filtration ${\mathcal{F}}_n=\sigma (X_0,\dots ,X_n)$, the Markov property gives the conditional expectation identityFor a function harmonic everywhere, this makes $h(X_n)$ a martingale whenever it is integrable. For a function harmonic only in the interior, $M_n=h(X_{n\wedge T})$ is a stopped martingale. In either five-state example, $0\le M_n\le 1$. Also, from any interior state at most three consecutive upward steps reach $4$, with probability at least $p^3>0$. Repeated three-step blocks give ${\mathbb{P}}_i(T>3k)\le (1-p^3{)}^k$, so $T$ is almost surely finite and has finite expected value; compare finite-interval exit times have geometric tails. Applying optional stopping at $n\wedge T$ and then the bounded convergence theorem givesThe boundedness and finite hitting time justify this passage to the limit. See Steven Lalley's notes, harmonic functions and stopped expectations, theorem 1, and stopped martingale in discrete time for this bounded version of optional stopping.

Uniqueness has a short maximum principle explanation. On a finite state space, the difference of two harmonic extensions with the same boundary conditions is zero on the boundary. If its positive maximum occurs inside, the weighted average forces every successor with positive transition probability to have the same maximum. A path to the boundary propagates that maximum to zero, a contradiction. Applying the argument to the negative of the difference proves uniqueness. Reachability of the boundary is essential: an interior closed communicating class can retain an arbitrary constant.

// Target: markov-process.bigb

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

For the exit law, the two identified processes have the same argument. Starting at zero, neither can skip $-a$ or $b$: Brownian motion is continuous, and the symmetric Poisson difference process has unit jumps with integer boundary levels. Therefore $|X_{t\wedge T}|\le K=\max (a,b)$, and if $T$ is finite, $X_T\in \{-a,b\}$.

To justify finiteness rather than presume it, apply the optional stopping theorem to the martingale $X_t^2-t$ at the bounded stopping time $t\wedge T$:The first boundary hitting time is a stopping time in both cases: in the continuous case use the continuous-path hitting criterion, and in the jump case inspect the successive jump times. Monotone convergence now gives $\mathbb{E}T\le K^2$, so $T<\infty$ almost surely. The stopped position tends to $X_T$ as $t\to \infty$ and is bounded, making dominated convergence applicable. Stopping $X$ at $t\wedge T$ and taking this limit yields $\mathbb{E}{X}_T=0$.

If $\pi =\mathbb{P}(X_T=-a)$, then $0=-a\pi +b(1-\pi )$. Thus in both cases the entire distribution isThis is the same balanced gambler's ruin law despite the different one-time distributions. As a further consistency check, passing to the limit in the stopped square-martingale identity givesAll uses of an unbounded exit time were obtained by limits of bounded-time sampling with an explicit bound on the stopped position.

On the negative branch set $Y=-X$. Its outward step probability is $3/4$ and inward probability is $1/4$. The same finite gambler's ruin recurrence as in part (a), with root $(1/4)/(3/4)=1/3$, gives ${\mathrm{Pr}}_{-1}(T_0<\infty )=1/3$. Hence, following one departure from zero, the probability of returning isAt each return the Strong Markov property restarts the same excursion experiment. The probability of at least $m$ returns is $r^m$, tending to zero. Thus almost surely there is a last visit to zero.

After that visit the walk remains strictly positive or strictly negative, because nearest-neighbour steps cannot change sign without crossing zero. On the positive branch it can be coupled, up to any return, to independent steps of mean $2/3-1/3=1/3$. The strong law of large numbers gives a walk tending to $+\infty$ almost surely. This conclusion remains true on the event that the excursion never returns: conditioning on a positive-probability event cannot make a probability-zero failure of the law occur. On the negative branch the mean step is $1/4-3/4=-1/2$, giving $-\infty$ in the same way. Apply this at each possible departure time, a countable family, or use the Strong Markov property at the successive returns. ThereforeFinite visits to zero alone would not prove divergence on an arbitrary chain; the outward-drift argument is the additional step needed here.

This is a gambler's ruin hitting problem. For $0<p<1$, let $h_j$ be the probability of reaching $+3$ before $-3$ when the current difference is $j$. Conditioning on the next independent game givesStopping occurs almost surely: conditional on being inside the barriers, three consecutive wins by either player force absorption within the next three games. This event has probability $p^3+q^3>0$, so the chance of surviving $m$ such blocks is at most $(1-p^3-q^3{)}^m$, which tends to zero.

If $p\ne q$, the characteristic roots of the interior recurrence are $1$ and $r=q/p$, so $h_j=A+B{r}^j$. Imposing the two boundary values yieldsIn particular,For $p=q=1/2$ the recurrence instead has affine solutions, and the boundary values give $h_j=(j+3)/6$, hence $h_0=1/2$. The deterministic cases $p=0,1$ give zero and one respectively. The formula covers all of them continuously:The stopping argument and the boundary recurrence show why the answer concerns the first barrier reached rather than the win difference after a predetermined number of games.

Let $L$ be the last vertex visited for the first time, and assume $N\ge 2$. Every vertex is eventually painted with probability one: from any position, $N-1$ consecutive clockwise steps visit the entire cycle, and the probability of such a block is $2^{-(N-1)}$. Thus the probability that coverage has not occurred after $m$ successive blocks is at most $(1-2^{-(N-1)}{)}^m$, which tends to zero.

Fix $j\ne 0$ and cut the cycle at $j$. Represent it as the path with positions $0,1,\dots ,N$, where the two endpoints both represent $j$ and the original starting vertex is at position $N-j$. Up to the first visit to $j$, the walk is a simple symmetric random walk on this path, killed at either endpoint. The event $L=j$ is precisely that it visits both $1$ and $N-1$ before being killed: travelling between these two positions visits all intermediate vertices, while visiting all non-$j$ vertices necessarily includes these two.

For $N\ge 3$, first wait until the walk reaches one of $1,N-1$. This happens almost surely before it can reach an absorbing endpoint. If it reaches $1$ first, it must next reach $N-1$ before zero. The gambler's ruin probability is $1/(N-1)$: the hitting probability $h(i)$ on $0\le i\le N-1$ satisfiesso its successive differences are constant and $h(i)=i/(N-1)$. Starting at $1$ gives the stated probability. If the first endpoint reached is $N-1$, reflection of the path gives the same probability of reaching $1$ before $N$. The Strong Markov property at the first such hit therefore gives $\mathbb{P}(L=j)=1/(N-1)$, independently of which endpoint was hit first and of the start position.

Consequently the last visited vertex of a simple random walk on a cycle has distributionFor $N=2$ the same formula follows directly since the only other post must be last. For $N=1$, painting the initial post already completes the task, so there is no subsequent last unpainted post.

This is the simple symmetric random walk on the integers, starting at zero. It is recurrent: it returns to zero infinitely often almost surely, and in fact visits every integer infinitely often. To see the two-sided unboundedness explicitly, gambler's ruin gives, for positive integers $a,b$,Letting $a\to \infty$ shows that $b$ is hit with probability one; the analogous argument hits every negative integer. From any state the same argument gives return to zero with probability one. Repeated use of the Strong Markov property then gives infinitely many returns and visits. ThereforeIn particular $X_n$ has no limit almost surely, and $|X_n|$ does not tend to infinity because of the returns to zero. In contrast, the strong law of large numbers gives $X_n/n\to 0$ almost surely, while the central limit theorem gives $X_n/\sqrt{n}\stackrel{d}{\to }N(0,1)$. These distinguish oscillation of the path from scaling limits of its probability distribution.

For $0<i<N$, the total rate out of $i$ is ${\lambda }_i$. The holding time of the continuous-time Markov chain and its next state satisfyThe holding time is independent of the direction of this jump: the conditional probability of destination $j$ is the rate $q_{ij}$ divided by the total rate ${\lambda }_i$, independently of the elapsed holding duration. This is the exponential-clock construction of a continuous-time Markov chain with the given infinitesimal generator matrix.

At $i=0$ or $i=N$, all rates out are zero. These are absorbing states; the path remains at its initial endpoint and $J_i=\infty$ almost surely. There is no next visited state, so $X_{J_i}$ is not a finite-time jump value at either endpoint. If one separately uses $X_{\infty }$ for the limiting state, that limit is the same endpoint.

The embedded jump chain in the interior is a simple symmetric random walk on $\{0,\dots ,N\}$, stopped at the endpoints. From any interior state it has probability at least $2^{-N}$ of hitting a boundary in the next $N$ jumps, by following successive leftward choices. Thus its number of jumps before absorption is finite almost surely. Each of this finite number of holding times is finite almost surely, so absorption also occurs in finite continuous time. The finite set of positive interior rates causes no explosion; in particular their maximum bounds the total jump rate. When $N=1$, the chain starts at an already absorbing endpoint.

The rates alter the clock but not the sequence of visited states. The gambler's ruin calculation from part (a), translated to an initial state $i$ between endpoints $0,N$, therefore givesThis includes probability one at zero and probability zero at $N$.

Use the positive-integer convention for the geometric distribution:Conditional on $K=k$, independence gives $\mathbb{E}[S\mid K=k]=k/\lambda$. Taking expectations givesThis is the convention required below because a chain starting at $i$ makes at least one visit to $i$. If instead $K$ counts failures on $\{0,1,\dots \}$, its mean is $(1-p)/p$, and the corresponding answer for that different random sum is $(1-p)/(p\lambda )$.

For the chain of part (b), let $K_i$ count visits to $i$, including the initial visit, before absorption. After a departure to $i-1$, gambler's ruin on $\{0,\dots ,i\}$ gives probability $1/i$ of reaching zero before returning to $i$. After a departure to $i+1$, the analogous probability of reaching $N$ before returning is $1/(N-i)$. The departure is equally likely in either direction, so the probability of absorption before a return isAt every return to $i$, the Strong Markov property resets these alternatives. Hence the geometric return count before absorption gives $K_i\sim \mathrm{Geom}(p_i)$ on positive integers. One may construct the chain from its embedded jump chain and a separate sequence of fresh independent exponential clocks. Then its successive holding times at $i$ are independent and identically distributed rate-${\lambda }_i$ exponential random variables, independently of $K_i$, andUsing the first calculation gives the occupation time at an interior state of a variable-rate symmetric walk:For $N=2,i=1$, $p_i=1$ and the only visit is the initial one; the degenerate positive-integer geometric distribution at one handles this case. Other states' rates affect the time of each excursion, but not its probability of return, which explains why only ${\lambda }_i$ appears in this expectation.

A martingale describes an observable after its predictable drift has been removed. For a Markov chain the drift is the change produced by its transition operator; for Brownian motion it is one half of the Laplacian. Requiring the resulting processes to be martingales for a sufficiently rich class of observables determines the transition law itself. The same identities, combined with optional stopping, determine hitting probabilities, expected exit times and recurrence or transience. The duplicated Q5 paragraph in the PDF is a repeated printing of this one essay request.

For a finite or countable-state Markov chain with transition matrix $P$, define $(Pf)(x)={\sum }_{y}P(x,y)f(y)$ for a bounded test function $f$. The Markov property says $\mathbb{E}[f(X_{n+1})\mid {\mathcal{F}}_n]=(Pf)(X_n)$. Consequentlyis a martingale, since each increment has conditional expected value zero. Conversely, if these processes are martingales for every bounded $f$, taking the conditional expectation of an increment recovers that identity. With $f=1_{\{y\}}$ it gives $\mathbb{P}(X_{n+1}=y\mid {\mathcal{F}}_n)=P(X_n,y)$ for every state $y$. Thus, given the initial law, these identities characterize the Markov chain, not merely a few of its moments. This is the discrete-time Markov chain martingale characterization.

The drift operator is $P-I$. If $(P-I)h=0$ away from a target set, $h(X_{n\wedge T})$ is a stopped martingale, where $T$ is the first hit of that set. Under boundedness or suitable uniform integrability, the optional stopping theorem expresses $h$ in terms of boundary hitting probabilities. Similarly, if $(P-I)v=-1$ away from the target and $v=0$ on it, then $v(X_{n\wedge T})+(n\wedge T)$ is a martingale, giving $v(x)={\mathbb{E}}_{x}T$ when the terminal limit is justified.

For a concrete calculation, take a simple symmetric random walk on $\{0,1,\dots ,N\}$ stopped at $T$, its first hit of $0$ or $N$. In the interior, $h(i)=i$ has zero drift, while $v(i)=i(N-i)$ satisfiesThe stopped identity gives ${\mathbb{E}}_i(T\wedge n)=v(i)-{\mathbb{E}}_{i}v(X_{T\wedge n})\le v(i)$, proving $T$ finite with finite mean. Bounded convergence in both stopped identities now yields the gambler's ruin answersThis illustrates why the integrability justification is part of using a martingale, rather than an automatic consequence of writing an equation.

For a finite-state continuous-time Markov chain with generator matrix $Q=(q_{ij})$, the corresponding martingale problem for a continuous-time Markov chain usesThese are martingales. Conversely, suppose an adapted càdlàg finite-state process satisfies these identities. Let $P_t=e^{tQ}$, fix $T$, and set $g(s,i)=(P_{T-s}f)(i)$. Then ${\partial }_{s}g+Qg=0$. Apply deterministic integration by parts to the finite collection of indicator martingales to obtain the time-dependent Dynkin formula: $g(s,X_s)-g(0,X_0)-{\int }_0^s({\partial }_{r}g+Qg)(r,X_r)dr$ is a martingale. ThereforeThis recovers the Markov property and the entire semigroup, proving the characterization. On countable spaces one uses nonexplosion and localization to justify the analogous unbounded-rate formulas.

For $d$-dimensional Brownian motion, the Itô formula shows that, for $f\in C_c^{\infty }({\mathbb{R}}^d)$,is a true martingale, since its bounded derivatives make the integral square-integrable on each bounded horizon. This is the martingale problem for Brownian motion with generator $L=\frac{1}{2}\Delta$.

Here is why it also characterizes Brownian motion. Suppose a continuous adapted process $X$, with $X_0=x$, satisfies that martingale problem. Use smooth cutoff test functions equal to $x_i$ and $x_i{x}_j$ inside successively larger balls, and stop before leaving those balls. The coordinate tests show that $X^i-x_i$ are continuous local martingales; the product tests show that $X^i{X}^j-x_i{x}_j-{\delta }_{ij}t$ are local martingales. The Itô product rule consequently givesthe difference between the two proposed compensators is a continuous finite-variation local martingale, hence constant and zero at time zero. For each $u\in {\mathbb{R}}^d$, another application of the Itô formula gives the exponential local martingaleIts modulus is the deterministic quantity $e^{|u{|}^{2}t/2}$, so it is a true martingale on every bounded time interval. Taking its conditional expectation and dividing by its known value at time $s$ givesThe conditional characteristic function identifies a centered multivariate normal distribution of covariance $(t-s)I$, independent of the past. Together with continuity, this is the defining law of Brownian motion. This proves the Lévy characterization of multidimensional Brownian motion in the form needed for the generator characterization.

The analytic use of these martingales parallels the chain case. A harmonic function $h$ satisfies $\Delta h=0$, so it yields a stopped local martingale until the process leaves its domain of harmonicity. Bounded stopped observables permit optional stopping and solve boundary hitting problems. A solution of $\frac{1}{2}\Delta v=-1$ with zero boundary values gives an expected exit time. For example, in the ball of radius $R$, $v(x)=(R^2-|x{|}^2)/d$ gives ${\mathbb{E}}_x{T}_R=(R^2-|x{|}^2)/d$; stopping $|B_t{|}^2-dt$ first at $T_R\wedge n$ proves finiteness and justifies the limiting calculation. The Brownian local time construction in Q4 is another example: the predictable compensators of approximations to $|B_t|$ recover its increasing occupation term.

We now prove the required three-dimensional transience of Brownian motion in dimension at least three, in the strong sense $|B_t|\to \infty$ almost surely. Start first at a point $x$ with $r<|x|<R$, and let $T$ be the first exit from this annulus. The radial Laplacian in dimension three givesThus $|B_{t\wedge T}{|}^{-1}$ is a bounded martingale. The exit time is finite: stopping $|B_t{|}^2-3t$ gives $3\mathbb{E}(t\wedge T)\le R^2-|x{|}^2$. At exit, continuity puts $|B_T|$ at either $r$ or $R$. The optional stopping theorem therefore yieldsand hence the Brownian sphere-hitting probability in dimension threeAs $R\to \infty$, the events $\{{\tau }_r<{\tau }_R\}$ increase to $\{{\tau }_r<\infty \}$: a continuous path is bounded on the finite interval preceding any finite inner hit. This argument assumes no transience. ConsequentlyTo pass from a positive escape probability to almost-sure eventual escape, take Brownian motion started at zero. Let ${\sigma }_R$ be its first hit of the sphere of radius $R$. Stopping the squared-norm martingale proves $\mathbb{E}{\sigma }_R=R^2/3<\infty$. At ${\sigma }_R$, the Strong Markov property and the preceding hitting formula giveThe Strong Markov property here follows from independent Brownian increments by approximating a stopping time from above with dyadic-valued stopping times and using path continuity. Choose $R_m=2^{m}r$. The exit times ${\sigma }_{R_m}$ increase to infinity, since a continuous path is bounded on every compact time interval. The events of a return to the closed ball of radius $r$ after ${\sigma }_{R_m}$ decrease and have probabilities $2^{-m}$. Their intersection has probability zero. Thus almost surely there is some finite exit time after which the path never again enters that ball. Apply this simultaneously to all positive integer $r$. This proves the last visit to a bounded ball for three-dimensional Brownian motion conclusion and therefore

The homogeneous linear recurrence relation has characteristic polynomial $(\lambda -1{)}^2$, hence general solution $h_k=A+Bk$. For the expected-time recurrence, rearrangement gives $m_{k+1}-2m_k+m_{k-1}=-2$, for which $-k^2$ is a particular solution. ThusImposing the absorbing boundary conditions from the preceding parts gives the gambler's ruin formulas

The initial position is $k=17$. Applying the gambler's ruin hitting probability and mean hitting time givesFor comparison, the original central starting position $k=10$ would give probability $1/2$ and mean time $100$ minutes.

Now the event is to hit $20$ before $1$, starting at $3$. Up to the first of those two hitting times, translate the interval by one unit; its endpoints become $0,19$ and the starting point becomes $2$. The gambler's ruin hitting probability is thereforeStopping at $1$ is essential: using the original absorbing endpoint $0$ would answer a different event.

Let $N=a+b$ and measure Lionel's fortune in unit stakes. This is gambler's ruin: the fortune moves by $+1$ with probability $p$ and $-1$ with probability $q$, stopping at $0$ or $N$. Let $m_i$ be the expected value of the absorption time starting at $i$. It is finite: from any interior state, a run of $N$ wins or losses has a fixed positive probability of absorption within $N$ steps, giving a geometric bound on survival over successive blocks. First-step analysis therefore givesFor $p\ne q$, the homogeneous solution of the recurrence is $A+B(q/p{)}^i$, and a particular solution is $-i/(p-q)$. Put $\rho =q/p$. Imposing the two endpoint boundary conditions gives the expected duration of biased gambler's ruinConsequently the expected number of games isThe denominator and numerator have matching signs, so this is positive. As a check its continuous limit at $p=q=1/2$ is $ab$, the expected duration of symmetric gambler's ruin.