Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 12 1 ii Solution Created 2026-10-03 Updated 2026-10-06
Write and let be the triangle count in a binomial random graph. For every three-element set of vertices, let be the indicator random variable that its three edges are present. ThenFor two distinct triples , their indicator random variables are independent random variables unless they share an edge. Sharing just one vertex still leaves the sets of relevant edges disjoint. If they share an edge, their union has five edges, and thereforeThere are unordered pairs of distinct triangles in a graph sharing an edge: choose that edge, and then choose their two additional vertices. The variance of a sum consequently gives the exact formulaFor sufficiently large , the hypothesis ensures , so . Dropping negative terms and simplifying the binomial coefficients,Here as well. The event implies . Applying the Chebyshev inequality from part (i) gives the requested conclusion:Thus the triangle count is concentrated around its expectation throughout this range of the binomial random graph.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 322 1 iii Solution Created 2026-10-03 Updated 2026-10-06
The common-age conditional probabilities giveHere includes both possible component orders. Hence the binary star fractions have the concise ratioAs a check on the role of shared age, rather than . This is covariance induced by a shared latent variable: the red giant indicator random variables have covariance equal to the variance of , namely .
For a starburst galaxy with age , put . There is no age averaging. The component masses remain independent, so the fraction of systems with two red giants isThe last comparison is ambiguous in the printed question. Literally, the fraction of individual red giants in the first galaxy is . Since , no allowed starburst age satisfies that literal comparison. If the intended comparison is instead between systems containing two red giants in the two galaxies, compare with ; the answer isFor completeness, the individual red giant fraction in the burst is , which exceeds precisely for . This is a third, different comparison; it does not change the computed fraction of two-giant systems.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 201 2 c Solution Created 2026-10-03 Updated 2026-10-05
Pointwise, an integer-valued nonnegative random variable has the representationwhen , exactly the terms equal one. Applying the Tonelli theorem, or the monotone convergence theorem to the finite sums of indicator random variables, gives the tail-sum formula for expectationBoth sides may be infinite; no integrability assumption is necessary.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 207 1 a ii Solution Created 2026-10-03 Updated 2026-10-05
Let count all jumps of the continuous-time Markov chain. Its Markov-chain entry count into state isThusThis is a Lebesgue-Stieltjes integral against a counting process, so each jump contributes one. The initial occupation of state is not counted as an entry. An ordinary time integral of an indicator random variable asserting a jump at exactly time would be zero, since individual jump times have zero Lebesgue measure. The requested integral must therefore use this counting-measure interpretation. Assume non-explosion and finite expected jump counts on bounded intervals, as holds for a finite-state continuous-time Markov chain.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 207 1 a i Solution Created 2026-10-03 Updated 2026-10-05
Write for the continuous-time Markov chain and for expected value conditional on . The occupation time of a continuous-time Markov chain in state is the integral of its indicator random variable. By Tonelli theorem,The interchange is valid because the integrand is nonnegative; indeed the random integral is bounded by .
Past exam of the mathematics course of the University of Cambridge 2019 ia Paper 2 12F Solution Created 2026-09-24 Updated 2026-09-29
Let be the indicator random variable of . Then , so linearity of expectation givesUsing variance of a sum andwe obtain
For the circular array, let indicate that bulbs and are both on, with indices read modulo . Then . Non-neighbouring indicators are independent, whileThere are individual terms and ordered neighbouring pairs in the double covariance sum, so
The event is exactly . If , Markov inequality givesIf , then implies . By Chebyshev inequality,Therefore in the second regime.
Past exam of the mathematics course of the University of Cambridge 2019 ib Paper 4 9H a Solution 2026-09-29
Let be the number of returns to after time . Since is a recurrent state, the probability of another return after each visit is one. By the stated geometric distribution description, for every positive integer . Thus almost surely and .
On the other hand, writing each visit as an indicator random variable and applying the monotone convergence theorem to the partial sums givesThe left side is infinite, proving the recurrence criterion by return probabilities in the required direction:
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 339 2 c ii Solution Created 2026-10-03 Updated 2026-10-05
A fixed edge is monochromatic exactly when none of the hyperplanes separates its endpoints. Each hyperplane fails to cut it with probability at most , and the hyperplanes are independent. ThereforeLet count monochromatic edges. Applying linearity of expectation to these indicator random variables givesIndependence between different edges is unnecessary; only the independently sampled hyperplanes are used. The signs provide at most colors, whether or not every sign region is nonempty.
Past exam of the mathematics course of the University of Cambridge 2019 ii Paper 3 17G d Solution Created 2026-09-24 Updated 2026-10-03
For each edge , let be the indicator random variable of the event that precisely one endpoint lies in . Independent inclusion of the two endpoints with probability givesBecause , linearity of expectation givesSome realization therefore has . Retaining its crossing edges gives a subgraph that is bipartite, with vertex classes and , proving the random cut lower bound.
Now suppose is an even number and instead choose uniformly among all subsets of size . For a fixed edge ,and the reverse orientation has the same probability. ThusAnother application of linearity of expectation givesAt least one such balanced choice attains this expectation, and its crossing edges give the required subgraph that is bipartite. This is the balanced random cut lower bound.
Past exam of the mathematics course of the University of Cambridge 2021 ii Paper 1 17G b Solution Created 2026-09-24 Updated 2026-09-25
Let count triangles, where ranges over the three-element vertex sets and is the corresponding indicator random variable. ThenTwo distinct triangle indicators are independent unless their triangles share an edge. There areunordered pairs sharing an edge, and each covariance isThereforeIt follows thatwhen . Chebyshev's inequality now givesHenceas summarized by the triangle count in a binomial random graph.
Past exam of the mathematics course of the University of Cambridge 2023 ii Paper 1 17H b i Solution Created 2026-09-24 Updated 2026-10-03
Write as a sum of indicator random variable. Indicators for two distinct copies are independent when the copies share at most one vertex, since their edge sets are then disjoint. Pairs sharing two vertices have eleven edges in their union, while pairs sharing three have nine. It follows thatThus . By the second moment method, in probability, so . This is the sparse clique-count concentration estimate.
Let be indicator random variables for the two draws being red. Each draw has red probability , even though the draws are dependent. By linearity of expectation, the number satisfies
Write the count as a sum of Bernoulli random variables, one for each attendance indicator. Each indicator random variable has expected value , so linearity of expectation givesEquivalently, has a binomial distribution with parameters and .
Let be the indicator random variable of a black ball at draw . The black count after three draws is . By linearity of expectation,Independence is not required for this step. This is also the mean of the corresponding hypergeometric distribution.
Let be the indicator random variable of an apple in lunch . The number remaining is . Each expected value . The linearity of expectation therefore givesAlthough the indicator random variables are dependent under sampling without replacement, the linearity of expectation needs no independence assumption.
Let be the indicator random variable that coin shows a head. Each expectation is , so linearity of expectation gives the expected number of heads:For the game, write for the probability that eventually holds all coins when starting with . The states are absorbing, so and . Conditioning on the first toss and using the law of total probability givesThus : successive differences are constant, and . The boundary values give , , hence the gambler's ruin answer isFor completeness, the game terminates with probability one. From any nonabsorbing state, a run of consecutive heads would reach within the next tosses, and that run has probability . Conditional on survival, the same bound applies to the next block. Therefore the probability of surviving tosses is at most , which tends to zero.
Each position is equally likely to receive any coin, so the law of total probability gives . For two specified positions, the ordered pair of distinct coin biases is uniform over six possibilities. Assuming independent tosses conditional on the order,Thus the events are not independent, even pairwise. The covariance of draws without replacement explains the difference: the head indicator random variables have covariance . Independent physical tosses given the assigned coins do not imply independence after that hidden assignment is averaged out.
Let be the head indicator random variable for toss . These are independent and identically distributed random variables with a Bernoulli distribution of parameter , so , , and . Taking makes . The preceding Chebyshev's inequality bound givesThe endpoints are included because this event is exactly .
An indicator random variable equals with probability and with probability , so . Also pointwise, whence
Let be the indicator random variable that colour appears at least once. Then . For a colour of single-roll probability , independence of rolls gives . By linearity of expectation,The three indicators are not independent, but linearity of expectation does not require them to be. This is the expected number of observed categories.