Past exam of the probability course of the University of Oxford / 2015 / 3

The strong law of large numbers says that, for real independent and identically distributed random variables $Z_1,Z_2,\dots$ with $\mathbb{E}|Z_1|<\infty$,The assertion is almost sure convergence of the entire sequence of sample means. Finite first absolute moment suffices; a finite variance is not required.

Put $q=1-p$ and ${\xi }_i=Y_i-Y_{i-1}$. The Markov property and the state-independent transition probabilities show that, conditional on the whole previous history, ${\xi }_i$ is $+1$ with probability $p$ and $-1$ with probability $q$. Multiplying these conditional probabilities for any finite step sequence proves that the ${\xi }_i$ are independent and identically distributed random variables, withBecause $Y_n=k+{\sum }_{i=1}^n{\xi }_i$, the strong law of large numbers givesIn particular, $Y_n\to +\infty$ almost surely. This stronger pathwise consequence will determine both eventual crossings and the asymptotic first-passage times.

For $k=0$, the target is reached at time zero, so $h_0=1$. For $k<0$, the preceding almost sure convergence gives $Y_n\to +\infty$ with probability one. A sample path with unit upward and downward steps must visit every intermediate integer when it crosses from a negative value to a positive value. It must therefore visit zero at a finite time. ThusThe unit-step property matters: positive long-run displacement alone would not force a walk with larger upward jumps to land exactly on zero.

The first-step analysis gives $h_0=1$ and, for $k\ge 1$,The minimal nonnegative solution for hitting probabilities theorem states that the probability of ever hitting a target is the pointwise smallest nonnegative solution of this transition recurrence with value one at the target. It follows by comparing any such solution with the probabilities of hitting within $n$ steps, then taking their increasing limit.

The characteristic equation $p{r}^2-r+q=0$ has distinct roots $1$ and $\beta =q/p\in (0,1)$. Hence every solution on the nonnegative integers with boundary value one has the formIf it is nonnegative for all $k$, taking $k\to \infty$ forces $A\ge 0$, and therefore $g_k-{\beta }^k=A(1-{\beta }^k)\ge 0$. The candidate $g_k={\beta }^k$ is itself nonnegative and satisfies the recurrence and boundary value. It is consequently the minimal solution, giving the biased random walk hitting probabilityOn the negative half-line the already established values $h_k=1$ satisfy the same recurrence away from zero. No unproved boundary condition at infinity has been imposed.

Since $Y_n\to +\infty$ almost surely, only finitely many early values can attain the global minimum; it is a finite integer. Also $W\le Y_0=0$. For every nonnegative integer $m$, the unit-step property and translation invariance of the increments giveSubtracting consecutive tails yields the probability mass functionThus $-W$ has the geometric distribution counting failures before the first success, with success parameterThis support convention is essential: the minimum of an upward-biased random walk can equal its starting position, so $-W=0$ has positive probability.

Work on the single event of probability one where $Y_n/n\to \mu =2p-1>0$. On every sample path in that event, $Y_n\to +\infty$ and the unit-step property ensures that every positive integer $j$ is reached, so $T_j<\infty$. Starting from zero requires at least $j$ steps to reach $j$, hence $T_j\ge j$ and $T_j\to \infty$.

The convergent numerical sequence $Y_n/n$ on this fixed sample path also converges along its possibly random subsequence $n=T_j$. Since $Y_{T_j}=j$,Taking the reciprocal is valid because $\mu >0$. We obtainThis is a first-passage law of large numbers for an upward skip-free random walk. No independence between the hitting times and the path is needed: almost sure convergence already supplies convergence along every diverging subsequence on the same event.