Past exam of the mathematics course of the University of Cambridge / 2018 / iii / Paper 214 / 2 / a / Solution

Write $N_m=|B(m)|$ and $\theta =\theta (p)>0$. By translation invariance and linearity of expectation,Let $r={\mathbb{P}}_p(R(m)\ge \theta N_m/2)$. Since $0\le R(m)\le N_m$, splitting the expectation at the threshold givesRearranging produces the slightly stronger estimateOnly the mean and boundedness of the random variable are used; independence of the vertex-membership events is unnecessary.