A Maximum and Arcsine Laws Workshop

Three Questions About One Walk

Let \((\Omega,\mathcal{F},\mathbb{P})\) support independent random variables \((\xi_k)_{k\ge1}\) with \(\mathbb{P}(\xi_k=1)=\mathbb{P}(\xi_k=-1)=\tfrac12\). The simple symmetric random walk is \(S_0=0\) and \(S_n=\sum_{k=1}^n\xi_k\), a discrete-time process with state space \(\mathbb{Z}\). Its running maximum, positive occupation time, and last zero answer different questions about the same path. In this workshop, the maximum is treated exactly at finite \(n\); occupation time and last zero are also studied after division by \(n\), using their arcsine limits.

Definition: For an integer \(n\ge1\), define \(M_n=\max_{0\le k\le n}S_k\), \(A_n=\sum_{k=1}^n\mathbf{1}_{\{S_k>0\}}\), and \(g_n=\max\{k:0\le k\le n,\ S_k=0\}\). Thus \(A_n\) counts strictly positive positions at times \(1,\ldots,n\), while \(g_n\) is the last time at or before \(n\) when the walk is at zero. The maximum includes \(S_0=0\), so \(M_n\ge0\); the last-zero set is nonempty because it contains time zero.

The exact maximum formula below is a finite counting identity. The occupation-time and last-zero conclusions instead concern the distributions of \(A_n/n\) and \(g_n/n\) as \(n\) grows. These are not exact finite-\(n\) formulas. In particular, parity constraints and point masses can matter at finite times.

An Exact Formula for the Running Maximum

For an integer \(r\), write \(q_n(r)=\mathbb{P}(S_n\ge r)\). Since \(S_n\) is the sum of \(n\) increments, it equals \(2j-n\) when exactly \(j\) increments are \(+1\). Hence, with \(\lceil x\rceil\) denoting the least integer at least \(x\),

q_n(r)=2^{-n}\sum_{j=\max(0,\lceil(n+r)/2\rceil)}^n {n\choose j},

where a sum with lower index greater than \(n\) is zero. The formula includes the endpoint \(S_n=r\) when it is attainable: the event in \(q_n(r)\) is \(S_n\ge r\).

Theorem (Reflection formula): For every integer \(n\ge1\) and integer \(a\ge1\),

\mathbb{P}(M_n\ge a)=\mathbb{P}(S_n\ge a)+\mathbb{P}(S_n>a).

Equivalently, for every integer \(m\ge0\),

\mathbb{P}(M_n\le m)=1-q_n(m+1)-q_n(m+2).

Proof. Consider the set of length-\(n\) paths that hit \(a\), and divide it into paths with \(S_n\ge a\) and paths with \(S_n<a\). Every path ending at or above \(a\) must hit \(a\), since it starts at zero and changes by steps of size one. For a path that hits \(a\) and ends below \(a\), find its first time at \(a\) and reverse the sign of every increment after that time. The resulting path ends at \(2a-S_n>a\). This operation is its own inverse: every path ending above \(a\) hits \(a\), and reflecting its increments after the first hit gives a path ending below \(a\). All length-\(n\) paths have probability \(2^{-n}\), so the probability of hitting \(a\) and ending below \(a\) is \(\mathbb{P}(S_n>a)\). The paths ending at or above \(a\) contribute \(\mathbb{P}(S_n\ge a)\). Adding the disjoint contributions proves the first identity. Taking complements and setting \(a=m+1\) proves the second. \(\square\)

Worked Example: The Maximum Through Four Steps

Find the complete distribution of \(M_4\). The possible endpoints \(S_4=-4,-2,0,2,4\) have respective probabilities \(\tfrac1{16},\tfrac4{16},\tfrac6{16},\tfrac4{16},\tfrac1{16}\), from the binomial counts \({4\choose0},{4\choose1},{4\choose2},{4\choose3},{4\choose4}\). Thus \(q_4(1)=\tfrac5{16}\), \(q_4(2)=\tfrac5{16}\), \(q_4(3)=\tfrac1{16}\), \(q_4(4)=\tfrac1{16}\), and \(q_4(r)=0\) for \(r\ge5\).

Use the reflection formula at each integer threshold. For \(m=0,1,2,3,4\), the respective cumulative probabilities are

\begin{aligned} \mathbb{P}(M_4\le0)&=1-\tfrac5{16}-\tfrac5{16}=\tfrac6{16},\\ \mathbb{P}(M_4\le1)&=1-\tfrac5{16}-\tfrac1{16}=\tfrac{10}{16},\\ \mathbb{P}(M_4\le2)&=1-\tfrac1{16}-\tfrac1{16}=\tfrac{14}{16},\\ \mathbb{P}(M_4\le3)&=1-\tfrac1{16}-0=\tfrac{15}{16},\\ \mathbb{P}(M_4\le4)&=1-0-0=1. \end{aligned}

Subtract successive cumulative probabilities, using \(\mathbb{P}(M_4\le-1)=0\), to obtain \(\mathbb{P}(M_4=0,1,2,3,4)=(\tfrac6{16},\tfrac4{16},\tfrac4{16},\tfrac1{16},\tfrac1{16})\). Check: these masses sum to \(\tfrac{6+4+4+1+1}{16}=1\), and the mass at \(M_4=4\) is the probability of four consecutive upward steps, \(\tfrac1{16}\).

Occupation Time and the Arcsine Limit

The arcsine distribution on \([0,1]\) has density \(f(x)=1/(\pi\sqrt{x(1-x)})\) for \(0<x<1\), and cumulative distribution function

F(x)=\frac{2}{\pi}\arcsin\sqrt{x},\qquad 0\le x\le1.

The density integrates to one: under the substitution \(x=\sin^2\theta\), where \(0<\theta<\tfrac{\pi}{2}\), one has \(dx=2\sin\theta\cos\theta\,d\theta\) and \(\sqrt{x(1-x)}=\sin\theta\cos\theta\). The integral of the density is therefore \(\tfrac2\pi\int_0^{\pi/2}d\theta=1\). Integrating only to \(x\) gives the displayed \(F(x)\), including \(F(0)=0\) and \(F(1)=1\).

Standard result (arcsine limit for positive occupation): For the simple symmetric random walk defined above, \(A_n/n\) converges in distribution to the arcsine distribution as \(n\to\infty\). In particular, for \(0\le x\le1\), \(\mathbb{P}(A_n/n\le x)\to F(x)\). This limit theorem is established in the earlier material on the occupation-time arcsine law; here it is used to calculate workshop probabilities.

Worked Example: A Middle-Range Occupation Probability

Find the limiting probability that the walk is positive for between one quarter and three quarters of the observation times, including both endpoints. The event is \(\{\tfrac14\le A_n/n\le\tfrac34\}\). Because the limiting distribution has a continuous cumulative distribution function, probabilities of intervals with fixed endpoints converge to the corresponding limiting interval probability. Therefore

\lim_{n\to\infty}\mathbb{P}\left(\tfrac14\le \frac{A_n}{n}\le\tfrac34\right) =F(\tfrac34)-F(\tfrac14) =\frac{2}{\pi}\left(\arcsin\tfrac{\sqrt3}{2}-\arcsin\tfrac12\right) =\frac{2}{\pi}\left(\tfrac{\pi}{3}-\tfrac{\pi}{6}\right) =\tfrac13.

Check: \(F(\tfrac14)=\tfrac{2}{\pi}\cdot\tfrac{\pi}{6}=\tfrac13\), while \(F(\tfrac34)=\tfrac{2}{\pi}\cdot\tfrac{\pi}{3}=\tfrac23\); their difference is \(\tfrac13\). Inclusion or exclusion of either endpoint gives the same limiting value because the arcsine distribution has no point masses.

The Last Zero Before the Observation Time

The last zero \(g_n\) is a time index, not a height. A value of \(g_n/n\) near zero means the walk has had no zero for most of the observed interval; a value near one means it returned to zero relatively late. The event \(\{g_n/n\le x\}\), for \(0\le x\le1\), says that no zero occurred after time \(\lfloor nx\rfloor\), where \(\lfloor y\rfloor\) is the greatest integer at most \(y\). The constraint includes a zero at time \(\lfloor nx\rfloor\), if there is one, and excludes all later zeros through time \(n\).

Standard result (arcsine limit for the last zero): For the simple symmetric random walk, \(g_n/n\) converges in distribution to the arcsine distribution. Consequently, at every \(x\in[0,1]\), \(\mathbb{P}(g_n/n\le x)\to F(x)\). This is the last-zero arcsine limit from the earlier material on last zeros.

Worked Example: How Early Is the Last Zero?

Find the limiting probability that the last zero occurs no later than one quarter of the observation horizon. The event is \(\{g_n/n\le\tfrac14\}\); equivalently, the last zero time is at most \(\lfloor n/4\rfloor\). Applying the last-zero limit gives

\lim_{n\to\infty}\mathbb{P}\left(\frac{g_n}{n}\le\tfrac14\right) =F(\tfrac14) =\frac{2}{\pi}\arcsin\sqrt{\tfrac14} =\frac{2}{\pi}\arcsin\tfrac12 =\tfrac13.

Check: \(F(0)=0\) and \(F(1)=1\), as required for a distribution on \([0,1]\); at the requested threshold the value is \(\tfrac13\). This is a limiting probability, not an assertion that the finite-\(n\) probability equals \(\tfrac13\).

Endpoint Conventions and a Common Error

The reflection count depends on whether the endpoint event is strict. The identity uses both \(\mathbb{P}(S_n\ge a)\) and \(\mathbb{P}(S_n>a)\). Replacing the second term by \(\mathbb{P}(S_n\ge a)\) incorrectly counts paths ending exactly at the barrier a second time.

Common mistake. For \(n=2\) and \(a=1\), the paths are \(++,+-,-+,--\), each with probability \(\tfrac14\). The paths with \(M_2\ge1\) are \(++\) and \(+-\), so the probability is \(\tfrac24=\tfrac12\). A mistaken formula using \(2\mathbb{P}(S_2\ge1)\) gives \(2\cdot\tfrac14=\tfrac12\) here only by coincidence; it is not the reflection identity. At \(n=2,a=2\), the correct value is \(\mathbb{P}(S_2\ge2)+\mathbb{P}(S_2>2)=\tfrac14+0=\tfrac14\), whereas doubling the weak-tail probability gives \(\tfrac12\). The endpoint \(S_2=2\) belongs to the first term only.

For the same reason, a finite-horizon maximum calculation should specify whether the event is \(M_n\ge a\) or \(M_n>a\), and an occupation calculation should specify whether visits to zero count as positive. Here they do not: \(A_n\) uses the strict condition \(S_k>0\). Arcsine limits provide a useful asymptotic benchmark, but they do not erase finite-time lattice effects or replace exact counting when \(n\) is fixed.

Check Your Understanding

For each question, state the event with its endpoint convention before calculating.

For \(n=3\), use the reflection formula to compute \(\mathbb{P}(M_3\le1)\). Check that the result is between zero and one.
What is the limiting probability that \(A_n/n\) is at most \(\tfrac34\)? Evaluate the inverse-sine expression exactly.
Write the event \(\{g_n/n>\tfrac12\}\) in words. What is its limiting probability?
Why does the reflection formula for \(\mathbb{P}(M_n\ge a)\) contain a strict endpoint event in its second term?