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

The probability measure $\mathbb{P}$ maps the sigma-algebra $\mathcal{F}$ of events into $[0,1]$. Its probability axioms are nonnegativity, normalization $\mathbb{P}(\Omega )=1$, and countable additivity: for every pairwise disjoint sequence of events $A_1,A_2,\dots$,The sample space is $\Omega$, and $\mathcal{F}$ specifies which subsets are events. Requiring countable additivity, rather than only its finite version, is part of the probability space definition.

The probability axioms first give $\mathbb{P}(\varnothing )=0$: apply countable additivity to $\Omega ,\varnothing ,\varnothing ,\dots$ and use normalization and nonnegativity. If $A\subseteq B$, then $B=A\dot{\cup }(B\setminus A)$ is a disjoint union of events. Finite additivity, as a special case of countable additivity, givesThus a probability measure is monotone with respect to set inclusion. The difference event is measurable because the events belong to a sigma-algebra.

By the even probability density of the standard normal distribution,The integral is finite. Equivalently, $|Z|$ has the half-normal distribution with unit scale.

A particular solution of the linear recurrence is $-n-1$, while its homogeneous solution is $C{2}^n$. The initial value gives $C-1=1$, soSubstitution verifies $u_{n+1}-2u_n=n$, and the recurrence plus $u_0$ determines all later terms uniquely.

The characteristic polynomial is $r^2-3r+2=(r-1)(r-2)$. Therefore $u_n=A+B{2}^n$. The initial values give $A+B=1$ and $A+2B=0$, yielding $A=2$, $B=-1$. HenceThe two constants are fixed by the two initial conditions of this second-order linear recurrence.

The characteristic polynomial of the homogeneous linear recurrence is $(r-2{)}^2$, so its repeated-root solutions are $(A+Bn)2^n$. A constant particular solution is one. Thus $u_n=1+(A+Bn)2^n$. The initial conditions give $A=-1$ and $B=1$, henceThe factor $n$ is required by the repeated root of a polynomial; omitting it would lose one independent solution.