Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Discrete mathematics, continuous mathematics, and probability / 7

A partition of a sample space is a finite or countable family of nonempty events such thatThus exactly one event in the family occurs in each outcome. To use ordinary event-conditioned conditional expectations, one usually assumes $\mathbb{P}(B_i)>0$; any zero-probability blocks can instead be omitted from the expectation formula.

For an integrable random variable $X$ and a partition of a sample space $(B_i)$, the law of total expectation statesIt follows by writing $X={\sum }_{i}X{1}_{B_i}$ and using $\mathbb{E}[X{1}_{B_i}]=\mathbb{P}(B_i)\mathbb{E}[X\mid B_i]$. Integrability justifies the countable sum. The same equality is valid with nonnegative, possibly infinite expectations when $X\ge 0$.

Let $\tau$ be the absorption time. Its expectation is finite: from every interior state, a string of at most $n$ successive left moves reaches $0$, and the probability of such a string is at least $p=3^{-n}$. Hence the Markov property gives ${\mathbb{P}}_k(\tau >jn)\le (1-p{)}^j$, a geometric tail bound, and ${\mathbb{E}}_k[\tau ]<\infty$.

For $1\le k\le n-1$, one step is always spent before absorption or the remaining walk. Apply first-step analysis and the law of total expectation to the three possible first moves. The conditional expectations of the remaining absorption time are $e_{k+1},e_k,e_{k-1}$, respectively; independence of future moves gives the same law as a fresh random walk from the new position. Thuswhich rearranges toThe term $1$ also appears when the walk stays at $k$, because staying still consumes a step.

The absorbing states give $e_0=e_n=0$. Multiplying the difference equation in (i) by $3$ givesThe second finite difference of $k^2$ is $2$, so a particular solution is $-3k^2/2$; the homogeneous solutions are $A+Bk$. Imposing the two boundary conditions gives $A=0,B=3n/2$. ThereforeUniqueness follows because the difference of any two solutions has zero second finite difference, hence is affine function, and vanishes at both endpoints. This is the mean absorption time of a lazy symmetric random walk with holding probability $1/3$.

For each random variable, the probability mass function givesLet $S_m={\sum }_{i=1}^m{X}_i$. By linearity of expectation and variance additivity for independent random variables,The independence is needed for the variance calculation, but not for the mean.

Each $X_i$ has the same probability distribution as $-X_i$. By independence, the entire vector and its negative have the same joint law, so $S_m$ has a symmetric distribution about zero. The two disjoint tail events consequently have equal probabilities:Apply Chebyshev's inequality with the mean and variance from (i):Using only containment in the two-sided event would give $8/(3m)$; the symmetry supplies the necessary extra factor $1/2$.