Past exam of the mathematics course of the University of Cambridge / 2002 / ia / Paper 2

The characteristic equation of the homogeneous linear differential equation is $m^2+m-2=(m-1)(m+2)=0$, giving the homogeneous solution $A{e}^t+B{e}^{-2t}$. For the first forcing, a particular solution of the form $C{e}^{-t}$ gives $-2C=1$, soThe initial conditions impose $A+B=1/2$ and $A-2B=-1/2$, whence $A=1/6$, $B=1/3$. Thus the first solution isFor the second forcing, $e^t$ is already a homogeneous solution, so the usual exponential trial must be multiplied by $t$. Substitution of the particular solution $Ct{e}^t$ gives $3C{e}^t=e^t$, hence $C=1/3$. Now $y=A{e}^t+B{e}^{-2t}+t{e}^t/3$, and the initial conditions give $A+B=0$, $A-2B=-1/3$. Therefore the resonant solution isThe additional factor $t$ reflects resonance in a differential equation.

This is a separable differential equation. On the solution with $y<1$, integration from the initial condition givesThe right side lies in $[0,1)$, so taking its sine stays on the required branch. The solution isNear the origin, $1-\sqrt{1-x^2}=x^2/2+O(x^4)$, so $y=x^2/2+O(x^4)$ and the tangent line is horizontal. At the other end, $y\to \sin 1$, whileThus the curve has a vertical limiting tangent line as $x\uparrow 1$, even though $x=1$ is excluded from the domain.

For the direction field, the slope is nonnegative everywhere in the square. The segments are horizontal on $x=0$ and on $y=1$, become steeper as $x$ increases at fixed $y<1$, and become flatter as $y$ increases at fixed $x$. Near $x=1$ they are almost vertical unless $y$ is correspondingly close to one. The excluded corner $(1,1)$ has no single limiting slope: the ratio $(1-y^2)/(1-x^2)$ depends on the path of approach.

The indicator function $I_A$ equals one when the event $A$ occurs and zero otherwise. Its expected value is $\mathbb{E}{I}_A=\mathbb{P}(A)$. By linearity of expectation, no independence assumption is needed to obtainSince $I_i{I}_j=I_{A_i\cap A_j}$, including $p_{ii}=p_i$, the variance isIn particular, correlations between the events cannot simply be discarded.

Write $\mu =\mathbb{E}N$. If $\mu >0$, then $N=0$ implies $|N-\mu |\ge \mu$. Applying Chebyshev's inequality therefore givesEquivalently, the contribution of $N=0$ to $\mathbb{E}[(N-\mu {)}^2]$ is ${\mu }^2\mathbb{P}(N=0)$. A positive mean is necessary for the displayed ratio to be defined. If $\mu =0$, nonnegativity instead gives $N=0$ almost surely, and the printed ratio would be $0/0$.

After $n+1$ independent tosses, an even count arises in exactly two disjoint ways: an even count after $n$ tosses followed by a tail, or an odd count followed by a head. Independence of the last toss from the preceding ones therefore givesSubtracting the fixed point $1/2$ turns this into the linear recurrenceAs zero is even, ${\pi }_0=1$, so the probability isFor $p=1/2$ this is $1/2$ for every $n\ge 1$; for $p=0$ it is always one; for $p=1$ it alternates between one and zero according to the parity of $n$.

An integrating factor for a differential one-form is a nonzero function $\mu (x,y)$ for which $\mu (dy+fdx)$ is an exact differential, say $dF$. Then solutions lie on level sets $F=\text{constant}$. Locally, the compatibility condition is ${\partial }_x\mu ={\partial }_y(\mu f)$.

Here multiplication by $2y{e}^x$, which is nonzero for $y>0$, producesThe initial condition makes this first integral equal to $a^2$. Taking the positive branch yields the solutionon the connected interval containing zero where the radicand is positive. This domain restriction matters because the original differential equation is singular at $y=0$.

Completing the square gives $2x+x^2=(x+1{)}^2-1\ge -1$. As $y>0$, the differential equation consequently impliesAt $x=0$, $y^{\prime }=-a/2<0$. Thus, moving a little to the left from $y(0)=a\ge 1$, the curve rises above $a$. Throughout $y>1$ every segment of the direction field points downwards as $x$ increases, by the inequality above. Tracing backwards therefore makes $y$ rise further, so it cannot return to $y=1$. This graphical barrier argument proves $y>a\ge 1$ and $y^{\prime }<0$ for every $x<0$ on the solution. The explicit first integral also shows this branch extends throughout $x<0$: writing $t=-x>0$, the minimum of $e^t/t^2$ is $e^2/4>1$, so $a^2{e}^t-t^2>0$ for $a\ge 1$. Including the initial point, $y^{\prime }<0$ for all $x\le 0$.

For $a=1$ the curve is $y=\sqrt{e^{-x}-x^2}$ on $(-\infty ,b)$, where the strictly increasing function $x^2{e}^x$ has the unique positive root $x^2{e}^x=1$ at $b\simeq 0.703467$. The curve decreases through $(0,1)$ with slope $-1/2$ and reaches $(b,0)$ only as a limiting endpoint. Its derivative isAs $x\to -\infty$, $y\sim e^{-x/2}$ and $y^{\prime }\sim -\frac{1}{2}{e}^{-x/2}\to -\infty$. As $x\uparrow b$, the numerator tends to $-b^2-2b<0$ and the denominator to zero from above, so again $y^{\prime }\to -\infty$. More precisely, $y\sim \sqrt{b(b+2)(b-x)}$ at the endpoint. Both ends have the requested unbounded negative slope.

For the logistic differential equation, separate variables to obtain $\log |y/(1-ay)|=rt+C$ away from the constant solutions. Applying the positive initial condition givesThe formula also includes the constant solution $y_0=1/a$. Below $1/a$ positive solutions increase; above $1/a$ they decrease. They approach $1/a$ as $t\to \infty$. Equivalently, linearizing $F(y)=ry(1-ay)$ gives $F^{\prime }(0)=r>0$ and $F^{\prime }(1/a)=-r<0$. Thus zero is unstable and $1/a$ is asymptotically stable.

The forward Euler method gives $y_{n+1}=(1+r\delta t)y_n-ra\delta t{y}_n^2$. Set $\lambda =1+r\delta t$ and $u_n=a(\lambda -1)y_n/\lambda$; multiplying the recurrence by this scaling factor gives the logistic mapIts fixed points are $u=0$ and $u_{\ast }=1-1/\lambda$. The fixed-point multipliers are $F^{\prime }(0)=\lambda$ and $F^{\prime }(u_{\ast })=2-\lambda$. Since $\lambda >1$, zero is always unstable. The positive fixed point is stable for $1<\lambda <3$ and unstable for $\lambda >3$. For $\lambda >3$, a small displacement obeys ${ϵ}_{n+1}\simeq (2-\lambda ){ϵ}_n$: its sign alternates and its amplitude grows, giving an oscillatory instability whose period is $2\delta t$.

This is an artifact of Euler discretization of logistic growth. Exact small perturbations decay by the positive factor $e^{-r\delta t}$ per time step; a one-dimensional autonomous differential equation cannot have a nonconstant periodic orbit, since its solutions move monotonically between equilibrium points. The artificial instability occurs when $r\delta t>2$, beyond the stable step range of this discretization.

For $\lambda =3.2$, remove the fixed point factors from $F(F(u))-u$ to obtain ${\lambda }^2{u}^2-\lambda (\lambda +1)u+\lambda +1=0$. The resulting logistic map two-cycle isThese points map to each other. Their periodic-orbit multiplier is $F^{\prime }(u_{-})F^{\prime }(u_{+})=4+2\lambda -{\lambda }^2=0.16$, so the two-cycle attracts nearby iterates. The cobweb shows a small initial departure from $u_{\ast }=0.6875$ growing with alternating sign and then settling into the finite rectangle between $u_{-}$ and $u_{+}$. The time trace shows the corresponding finite-amplitude oscillation.

Two functions are linearly dependent if constants $c_1,c_2$, not both zero, satisfy $c_1{y}_1+c_2{y}_2=0$ identically. Differentiating also gives $c_1{\dot{y}}_1+c_2{\dot{y}}_2=0$. Since the determinant of these two equations is the nonzero Wronskian $W$, both constants must vanish. Hence the two solutions are linearly independent.

Differentiating the Wronskian and substituting the homogeneous linear differential equation givesIntegrating proves Abel's identity:For variation of parameters, impose ${\dot{a}}_1{y}_1+{\dot{a}}_2{y}_2=0$ on the proposed particular solution. Then $\dot{y}=a_1{\dot{y}}_1+a_2{\dot{y}}_2$, and substitution into the inhomogeneous differential equation leaves ${\dot{a}}_1{\dot{y}}_1+{\dot{a}}_2{\dot{y}}_2=f$. Solving this two-by-two linear system givesArbitrary constants of integration merely add a homogeneous solution.

For the constant positive coefficient $q={\omega }^2$, take $\omega >0$. Direct differentiation verifies that $y_1=\cos \omega t$ and $y_2=\sin \omega t$ solve the homogeneous linear differential equation; their Wronskian is $W=\omega$. The requested integrands areTaking $t_0=0$ yieldsThus $|a_1(t)|\sim t/(2\omega )$ grows with power one, whereas $a_2$ is bounded. Their combination simplifies to $y_p=-t\cos (\omega t)/(2\omega )+\sin (\omega t)/(2{\omega }^2)$; the final sine term is itself a homogeneous solution. The secular term is the response to resonance in a differential equation.

Introduce $H=x^2-y^2+y^4/2$. Along a solution,At $\alpha =0$, $H$ is a first integral. The identity $H+1/2=x^2+(y^2-1{)}^2/2$ shows its level sets are bounded: neither $x$ nor $y$ can escape to infinity on a fixed level. Consequently trajectories remain bounded as $t\to \infty$, including those starting far from the origin. This bound also prevents finite-time escape; no explicit solution is needed.

The equilibrium points are $(0,0)$ and $(0,\pm 1)$. The Jacobian matrix at $(0,y_{\ast })$ isAt the origin its eigenvalues are $(\alpha \pm \sqrt{{\alpha }^2+4})/2$, with opposite signs, so the origin is a saddle point in all three cases. An eigenvector for $\lambda$ lies on $y=-x/\lambda$; the stable direction has positive slope and the unstable direction negative slope. At $(0,\pm 1)$ the eigenvalues are $(\alpha \pm \sqrt{{\alpha }^2-8})/2$.

When $\alpha =0$, these latter eigenvalues are $\pm i\sqrt{2}$. The nonlinear classification follows from the strict minima of $H$ at the two points: nearby level sets are closed curves without other equilibria, and the nonvanishing vector field makes them periodic orbits. Thus the two points are center equilibria. For $-1/2<H<0$, there are two separate closed ovals, one around each center equilibrium. The level $H=0$ consists of the saddle point and two homoclinic orbits forming a figure eight, explicitlyFor $H>0$, a single outer closed orbit encloses all three equilibrium points. Motion is clockwise, as the vector points downwards wherever $x>0$. The upper homoclinic orbit leaves the origin into $x<0,y>0$ and returns through $x>0,y>0$; the lower one has the reflected orientation.

When $\alpha =0.1$, the two nonzero equilibrium points have eigenvalues $0.05\pm i\sqrt{7.99}/2$ and are unstable foci. Nearby paths spiral outward clockwise. The first integral becomes a strictly increasing energy along every nonconstant trajectory: although $\dot{H}$ can momentarily vanish when $x=0$, it cannot vanish on an interval unless the solution is an equilibrium. Thus there are no periodic orbits or homoclinic orbits. The two stable separatrices of the saddle point, traced backwards, spiral towards the corresponding unstable foci. Its unstable separatrices move onto positive energy and escape outwards. All other nonequilibrium trajectories outside the stable manifold are unbounded forwards: a bounded forward limit set would have to lie in $x=0$, whose only invariant points are the three equilibria; the two unstable foci cannot attract a nonconstant trajectory, and convergence to the saddle occurs only on its stable manifold. Escape is not finite-time blow-up, since $\dot{H}\le 2\alpha (H+1/2)$ bounds the energy on every finite interval.

When $\alpha =-0.1$, the eigenvalues at the nonzero points are $-0.05\pm i\sqrt{7.99}/2$, so they are stable foci. The energy decreases, keeping all forward trajectories in compact sublevel sets. A bounded limit set must lie in the invariant part of $x=0$, so trajectories converge to equilibria: generically to one of the two stable foci, exceptionally to the saddle along its stable manifold. The saddle's unstable separatrices spiral into the two stable foci; its stable manifold separates their attraction basins. Again, energy monotonicity excludes periodic orbits and homoclinic orbits. These three cases give the quartic double-well phase portrait with linear damping below.

For $\mathbb{P}(B)>0$, the conditional probability is $\mathbb{P}(A\mid B)=\mathbb{P}(A\cap B)/\mathbb{P}(B)$. Since the events $B_i$ partition the sample space, their intersections with $A$ are disjoint and exhaust $A$. The law of total probability therefore gives $\mathbb{P}(A)={\sum }_j\mathbb{P}(A\mid B_j)\mathbb{P}(B_j)$. Substituting this and $\mathbb{P}(A\cap B_i)=\mathbb{P}(A\mid B_i)\mathbb{P}(B_i)$ into the definition proves Bayes' theorem:The denominator is positive by the given hypothesis on $A$.

Every urn contains $n-1$ balls. Let $k=n-r$ be its number of blue balls; choosing an urn uniformly makes $k$ uniform on $0,\dots ,n-1$. Conditional on that urn, the probability of a blue first draw is $k/(n-1)$, so the law of total probability givesDrawing twice without replacement requires $n\ge 3$. Given $k$, the probability that both draws are blue is $k(k-1)/((n-1)(n-2))$, and henceTaking the ratio defining conditional probability gives the second requested probabilityAlthough a blue first draw removes a blue ball from its urn, it also makes an urn rich in blue balls more likely. Averaging with this changed conditional distribution is essential.

Two independent events satisfy $\mathbb{P}(A\cap B)=\mathbb{P}(A)\mathbb{P}(B)$. If $\mathbb{P}(B)>0$, this is equivalent to $\mathbb{P}(A\mid B)=\mathbb{P}(A)$: learning that $B$ occurred does not change the probability of $A$. The product definition also covers zero-probability events without dividing by zero.

The 36 ordered outcomes are equiprobable. For $2\le s\le 12$, let $c_s=6-|s-7|$ count outcomes with sum $s$. Then $\mathbb{P}(A_s)=c_s/36$ and $\mathbb{P}(B_i)=1/6$ for $1\le i\le 6$. Their joint probability is $1/36$ if $1\le s-i\le 6$, and zero otherwise.

If the joint probability is zero, independence is impossible in these ranges because both marginal probabilities are positive. If it is $1/36$, the independent events condition requires $1/36=c_s/216$, or $c_s=6$. This happens only for $s=7$, and then all six values of $i$ allow the partner $7-i$. Therefore within the possible sums and facesIf arbitrary integer labels outside these ranges are included, an impossible sum or face defines an empty event, which is trivially independent of every event.

Conditional on $N=n$, the $n$ type indicators are independent random variables with the Bernoulli distribution of parameter $p$. Thus $F\mid N=n$ has the binomial distribution and its probability generating function is $(1-p+ps{)}^n$. The general rule used here is that for a nonnegative integer-valued random variable $X$, $G_X(s)=\mathbb{E}[s^X]$; for a sum of independent such variables, their probability generating functions multiply, since the expected value of the product $s^{X_1}\cdots s^{X_n}$ factors. The law of total expectation then averages the conditional result:This calculation uses the given independent labeling of objects, including conditional on their number.

A Poisson distribution with parameter $\mu$ has probability generating function $G_N(s)=e^{\mu (s-1)}$. The preceding part gives $G_F(s)=e^{\mu p(s-1)}$, the probability generating function of a Poisson distribution with parameter $\mu p$. To prove independence, retain both counts:Consequently the joint probability generating function factors asComparing the coefficients of $s^f{t}^k$ proves that the joint probabilities are the products of the marginal probabilities. Hence $F$ and $S$ are independent, with distributions $\mathrm{Poisson}(\mu p)$ and $\mathrm{Poisson}(\mu (1-p))$. This is Poisson thinning, including the degenerate counts when $p=0$ or $p=1$.

With equal type probabilities, $F$ and $S$ have the same marginal probability generating function, namely $G_N((1+s)/2)$. Their assumed independence, together with $N=F+S$, givesSet $H(t)=G_N(1-t)$ for $0\le t\le 1$. The identity becomes $H(t)=H(t/2{)}^2$ and, after $k$ iterations,The finite expected value gives $G_N(1-h)=1-\mu h+o(h)$ as $h\downarrow 0$. To justify this without any analyticity assumption at the endpoint, note that $(1-(1-h{)}^N)/h\to N$ and is bounded above by $N$; dominated convergence gives the derivative $G_N^{\prime }(1-)=\mu$. Substituting the expansion into the iterated identity yieldsThe left side is independent of $k$, so it equals the limit. Thus $G_N(s)=e^{\mu (s-1)}$ on $[0,1]$ and uniqueness of the power-series coefficients proves $N\sim \mathrm{Poisson}(\mu )$. Only finite expected value was needed; the given finite variance is stronger. This proves the Poisson characterization by independent binomial splitting rather than assuming the original count distribution.

For independent random variables, the probability density function of a sum is the convolution of probability densities. Since each density is one on $[0,1]$ and zero elsewhere,This is the length of $[0,1]\cap [u-1,u]$. Therefore the density isThe two triangular areas sum to one, as a probability density function must.

Conditioning on $U=X+Y$, independence of $Z$ gives $\mathbb{P}(Z>u)=1-u$ for $0\le u\le 1$ and zero for $u>1$. Using the preceding probability density function,

Three positive lengths form a nondegenerate triangle precisely when each is less than the sum of the other two. Necessity is the triangle inequality. For sufficiency, two circles centered at the ends of one side intersect off that side whenever the remaining lengths satisfy these strict inequalities, giving the third vertex.

Failure thus occurs when $X\ge Y+Z$, $Y\ge X+Z$, or $Z\ge X+Y$. Two such inequalities cannot hold together for strictly positive lengths. Zero lengths and equality cases have probability zero because the variables have continuous probability density functions. By symmetry each failure event has the probability $1/6$ just calculated. Hence the probability of forming a triangle is

Another convolution of probability densities gives, for $0\le s\le 1$,Only this part of the density is needed because the fourth length is at most one.

Four positive lengths $a,b,c,d$ can form a nondegenerate quadrilateral if and only if every length is less than the sum of the other three. Necessity follows by following the other three sides between the endpoints of the longest side and applying the triangle inequality. For sufficiency, select a diagonal length $r$ in the intersectionBoth intervals are nonempty, and their intersection is nonempty exactly when $|a-b|<c+d$ and $|c-d|<a+b$. These are precisely the four strict length inequalities. Construct triangles with sides $(a,b,r)$ and $(c,d,r)$ on opposite sides of their common diagonal. Their union has the required simple, nondegenerate quadrilateral as boundary.

The failure events, in which one length is at least the sum of the others, are disjoint except on sets of probability zero. For the specified length $W$, independence and the density above giveThere are four symmetric choices of the overly long side, so the probability isThis is the four-sided case of the polygon probability for independent uniform rods.

A branching process models reproduction through successive generations. In the Galton-Watson process used here, every individual independently produces a nonnegative integer number of offspring with a common offspring distribution; these reproduction counts are independent across individuals and generations. If $X_n$ is the generation size, thenwhere the ${\xi }_{n,j}$ have that distribution and the empty sum is zero. Thus zero is absorbing: once a generation is empty, every subsequent generation is empty.

Given $X_n=k$, the next size is a sum of $k$ independent reproduction counts. Multiplication of their probability generating functions gives $\mathbb{E}[s^{X_{n+1}}\mid X_n=k]=G(s{)}^k$. Averaging this conditional expectation provesWith one initial individual, $G_0(s)=s$ and $G_1(s)=G(s)$, so $G_n$ is the $n$-fold composition of $G$ with itself.

The binomial series givesThus $p_0=1-\alpha >0$ and, for $k\ge 1$,with the factors after $\beta$ omitted for $k=1$. The signs follow from $0<\beta <1$. As $s\uparrow 1$, the series has nonnegative terms and its sum increases to $G(1)=1$, so monotone convergence gives ${\sum }_{k\ge 0}{p}_k=1$. These are therefore genuine probabilities on the nonnegative integers, proving that $G$ is a probability generating function. Its expected value is infinite, since $G^{\prime }(s)=\alpha \beta (1-s{)}^{\beta -1}\to \infty$; finiteness of the mean is not required for this branching process.

Write $G_n(s)=1-A_n(1-s{)}^{{\beta }^n}$. The composition formula gives $A_{n+1}=A_n{\alpha }^{{\beta }^n}$, with $A_0=1$. Consequently $A_n={\alpha }^{1+\beta +\cdots +{\beta }^{n-1}}$, and summing the geometric series yields the explicit generation generating functionThis is the fractional-power offspring generating function and its iterates.

Evaluation of the probability generating function at zero selects the constant coefficient, soTo identify this limit with ultimate extinction, let $E_n=\{X_n=0\}$. The absorbing-zero property of the branching process gives $E_n\subseteq E_{n+1}$. Ultimate extinction means that some finite generation is empty, namely $E={\bigcup }_{n\ge 0}{E}_n$. Continuity of probability on increasing events therefore givesThis set argument is essential: it uses absorption, rather than inferring extinction merely from a numerical limit of generation probabilities.