Past exam of the mathematics course of the University of Oxford / 2015 / Prelims / Mathematics III / 4

The events $B_1,B_2,\dots$ form a partition of a sample space $\Omega$ when they are pairwise disjoint sets and cover the whole sample space:Thus exactly one of these events occurs on every outcome. Under the usual set partition convention the parts are nonempty; empty parts can simply be discarded.

For an integrable random variable $X$, the law of total expectation for the partition of a sample space isParts of zero probability contribute zero and need no definition of $\mathbb{E}[X\mid B_i]$. To see the identity, write $X={\sum }_{i}X{1}_{B_i}$ and use linearity of expectation; integrability justifies the countable sum since ${\sum }_i\mathbb{E}[|X|1_{B_i}]=\mathbb{E}[|X|]<\infty$.

First the expected value of the absorption time is finite. From any interior state, consecutive leftward moves lead to absorption within at most $n$ steps, with probability at least $p=3^{-n}$. By independence of the subsequent steps, the probability of surviving $jn$ steps is at most $(1-p{)}^j$. Summing this geometric series bounds the expected value of the absorption time by $n/p$.

Now apply first-step analysis. Starting from $k$ in the interior, one step is always used. Conditional on that step, the remaining expected values are $e_{k+1}$, $e_k$, and $e_{k-1}$, each with probability $1/3$. The law of total expectation therefore givesThe term $1$ remains even when the particle stays at $k$, because a step has elapsed. Rearranging gives

At an absorbing state, the remaining absorption time is zero, so $e_0=e_n=0$. Multiplying the linear recurrence relation by three givesThe second finite difference of $k^2$ is two. A particular solution is therefore $-3k^2/2$, while every solution of the corresponding homogeneous linear recurrence relation has the form $A+Bk$. The boundary conditions give $A=0$ and $B=3n/2$, henceThis is the mean absorption time of a lazy symmetric random walk with holding probability $1/3$.

Each random variable has mean zero and second moment $2/3$, so its variance is $2/3$. For $S_m={\sum }_{i=1}^m{X}_i$, linearity of expectation and variance additivity for independent random variables give

Each $X_i$ has the same probability distribution as $-X_i$, and independence makes $S_m$ and $-S_m$ identically distributed. Thus their two strict tail probabilities are equal:Apply Chebyshev's inequality using the mean and variance from part (i):The equal-tail argument is essential: applying Chebyshev's inequality directly to the absolute tail alone gives the weaker bound $8/(3m)$.