Past exam of the mathematics course of the University of Cambridge 2004 iii Paper 40 4 iv Solution Created 2026-10-03 Updated 2026-10-14
For the standard Cauchy distribution tail, use the indicatorThen is the desired probability, and the ordinary importance sampling estimator is . The proposal must cover the nonzero integrand, namely the upper tail. A proposal restricted to cannot directly estimate this indicator integral; part (v) instead uses a complementary bounded-interval identity.
Past exam of the mathematics course of the University of Cambridge 2004 iii Paper 40 5 vi Solution Created 2026-10-03 Updated 2026-10-14
Under the reference convention , the hypothesis becomes absence of the free group contrast . Introduce an inclusion indicator : set when , and use its stated proper normal prior when . Assign positive prior probabilities to those models, and retain in both.
A birth draws from a proposal probability density function and appends it as ; the reverse death deletes it. The Jacobian is one. At fixed , the likelihood ratio isThus the birth acceptance ratio before capping iswhere is the normalized prior. Again, taking cancels that factor. Use the reciprocal death rule and ordinary within-model parameter updates.
After warm-up, the Markov chain Monte Carlo occupation fraction estimates the desired probability:This requires the chain to explore both models and satisfy its usual ergodic convergence conditions. Under the original continuous normal prior alone, the equality event has posterior probability zero; the explicit model indicator supplies the necessary prior atom. If intercept selection from part (v) is also performed, use two indicators and count all sampled states with , regardless of the intercept indicator.
Past exam of the mathematics course of the University of Cambridge 2004 iii Paper 40 5 v Solution Created 2026-10-03 Updated 2026-10-14
Introduce a model indicator . In , set , hence , and retain the two group effects. In , include with the prior induced by the gamma baseline. Choose positive prior model probabilities summing to one; the supplied within-model parameter priors alone do not specify these probabilities.
Let , use the same proper prior in both models, and denote their likelihoods by and . The unnormalized joint model targets areFor a birth move, draw an auxiliary from a positive probability density function and map to . The reverse death move simply deletes . This is a dimension-matching bijection with absolute Jacobian one. If the birth and death selection probabilities are and , respectively, the birth and death moves for Bayesian variable selection rule givesThe reverse acceptance is the reciprocal ratio, capped at one, evaluated at the current . Choosing cancels the added-parameter prior; a data-informed proposal may mix better but must retain its proposal factor. Within each model, also update its continuous parameters to ensure exploration.
For an explicit likelihood ratio, with and from part (ii),This supplies a complete reversible-jump Markov chain Monte Carlo move. Its acceptance probabilities enforce detailed balance between the two dimensions. The lower-dimensional state is a separate point-mass model, not a zero-probability equality test inside the continuous full-model prior.
Past exam of the mathematics course of the University of Cambridge 2004 iii Paper 40 6 ii Solution Created 2026-10-03 Updated 2026-10-14
Let be the unobserved part of the fourth count associated with the component of probability . Its complementary subcount has probability . Conditional on the observed fourth count and a parameter value,The complete-data log-likelihood now has the simple formThe constant term can depend on the completed counts, but not on . The split therefore converts the troublesome term into a binomial-like maximization problem. Since is unobserved, it should be averaged conditionally in an EM algorithm, not guessed or treated as observed.
Past exam of the mathematics course of the University of Cambridge 2004 iii Paper 41 1 iii Solution Created 2026-10-03 Updated 2026-10-14
Define . Grouping equal claim sizes gives the pathwise identityConditional on , the independent claims receive category labels with probabilities . There are assignments producing prescribed category counts, and every assignment has probability . Thus the conditional probability distribution is a multinomial distribution:when the nonnegative counts sum to , and is zero otherwise.
For , condition first on and use the probability generating function of a Poisson distribution:This factorization is the joint probability generating function of independent Poisson distribution variables. HenceA category with has zero count almost surely. The categorical thinning of a Poisson claim count produces independence after averaging over the random total, even though the counts are constrained to sum to conditional on that total.
Past exam of the mathematics course of the University of Cambridge 2004 iii Paper 41 1 ii Solution Created 2026-10-03 Updated 2026-10-14
Use the preceding construction with type- claims of deterministic size . For , the answer isThe characteristic function verifies this directly:Hence has the stated compound Poisson distribution. Distinctness of the makes the atomic probabilities unambiguous.
A zero coefficient is allowed. It corresponds to zero-sized claims in this representation and contributes nothing to . If a representation using only positive claims is preferred, remove that category: its count parameter becomes , with probabilities on the positive values. The zero claim sizes in a compound Poisson representation explain why the count parameter need not be unique. If , or if all positive-size categories have zero rate, the aggregate is identically zero.
Past exam of the mathematics course of the University of Cambridge 2004 iii Paper 41 2 Solution Created 2026-10-03 Updated 2026-10-14
Let . Conditioning on givesWhere the moment-generating function is finite around zero, differentiating the cumulant-generating function givesIn particular and . These compound Poisson cumulants use raw claim moments. The first two formulas also follow by conditioning: and , soThis is the law of total variance. They therefore remain valid with finite first two moments even when no positive exponential moment exists.
Under per-claim excess of loss reinsurance, put and let be the positive part of the excess. The insurer and reinsurer totals are sums of these payments over the same Poisson distribution count. Write . Using the tail integral formula for moments on the tail probabilities of and givesFor example, after , and shifting by gives the reinsurer formula. The moment formulas are finite whenever the corresponding claim moments are finite.
For the specified Pareto distribution, with shape three and minimum ,If , every claim exceeds the reinsurance retention. ThereforeIf , the tail integrals instead giveConsequently the requested sum of variances isOn the first branch, ; it decreases until and then increases. On the second branch . For the minimum is unique; if , all variances are zero and every reinsurance retention minimizes them. ThusThe curve starts at , reaches this minimum, passes through with matching slope on both branches, and then increases concavely toward the horizontal asymptote . The variance-minimizing retention for shape-three Pareto claims is shown below.
Sum of insurer and reinsurer aggregate variances for shape-three Pareto claims, minimized at retention three quarters of the minimum claim size
. Details. The two aggregate payouts are dependent. Conditioning on the common count gives covariance , so for every reinsurance retention, as required by . The covariance of two components of a compound Poisson sum accounts for this distinction between a sum of variances and the variance of a sum.
There is a moment domain qualification for this heavy-tailed example. For every , , and moments of order also diverge. Thus its positive moment-generating function is not finite and higher finite cumulants cannot be obtained by differentiating around zero. Its mean and variance calculations above are valid by conditioning or by the first two right derivatives at zero of the Laplace transform of a nonnegative random variable.
Past exam of the mathematics course of the University of Cambridge 2004 iii Paper 42 6 Solution Created 2026-10-03 Updated 2026-10-14
In a regular model let be the log-likelihood, its score, its total Fisher information, and the unrestricted maximum-likelihood estimator. For a point null in a p-dimensional parameter space, the standard statistics areThese define the Wald test, score test and likelihood-ratio test. With an interior true parameter, increasing information, suitable differentiability and asymptotic normality, all have asymptotic chi-squared distribution with p degrees of freedom under the null. Observed information can replace expected information when it is asymptotically equivalent.
For q smooth independent restrictions , replace the Wald statistic by , where G is the derivative of g at the estimate; compare with chi-squared q. The likelihood-ratio statistic uses the difference between unrestricted and null-restricted maxima. The score statistic is computed at the restricted maximum and uses efficient information for the tested coordinates: with nuisance coordinates lambda this is . Inverting the acceptance inequalities for point nulls produces approximate coverage- confidence regions; for example the Wald region consists of theta satisfying . Analogous score and likelihood-ratio inequalities give their confidence regions.
For the Poisson family, put to include the initial observation, and defineMultiplying the initial and conditional Poisson probabilities gives, on the supported observation sequences,The parameter-free term is , interpreting as zero. A positive count after a zero preceding count is outside the support.
For , strict concavity gives unconstrained maximum , and the upper endpoint restriction givesThere is an endpoint qualification in the printed question. With probability , and all later counts are zero. Then , and the likelihood is , which has no maximum on the stated space . The formula produces zero only as an extended estimate on the closure . This is a likelihood supremum at an excluded boundary, and zero cannot be called an actual maximum in the original space.
The observed negative second derivative is . Conditional expectation gives and . Therefore for ,This is the bounded information in a subcritical Poisson branching process. Observing more generations of one family does not provide unbounded information. Indeed , and zero is absorbing, so extinction occurs at a finite generation almost surely. The total observed progeny is finite; eventually , , and the extended estimate equals , a discrete nondegenerate random variable rather than a consistent increasingly precise estimate.
Here is a direct proof of the failure of a chi-squared Wald limit which does not rely solely on the information bound. Under any interior null , the event , has probability and forces every later count to be zero. On it the genuine constrained estimate is for every , so the usual expected-information Wald statistic isThus it has a persistent atom tending to . The fact that atoms obstruct a continuous distributional limit rules out a chi-squared limit, including when equals one half and that atom is at zero. Any definition adopted for the separate all-zero sample event leaves this positive-count counterexample intact. Hence the Wald statistic does not have the usual asymptotic chi-squared null law for this increasing observation horizon.
Past exam of the mathematics course of the University of Cambridge 2004 iii Paper 54 2 Solution Created 2026-10-03 Updated 2026-10-14
There is a necessary distinction between a failure bound averaged over the unknown state, a worst-case bound, and a separate bound for each candidate state. The last interpretation is false: a forger can discard the inputs and always prepare . If the actual state is , every authenticity test passes with probability one. The meaningful uniform statement concerns worst-case failure, or average failure under any fixed prior giving both states positive probability. The PDF does not specify that prior; the argument below gives an explicit bound for either interpretation.
Put . Any unconditional strategy producing output qubits, including ancillas, adaptive measurement in quantum measurements and correlated outputs, is a quantum channel . Its inputs and ideal outputs are the density operatorsThe projective measurements on the different banknotes commute, and their all-pass effect is exactly . Therefore the probability of at least one rejection, conditional on input , isThis remains true for entangled outputs; no independence of their individual test outcomes is assumed.
Use trace distance . The pure-state trace distance and fidelity identity givesFor completeness, two pure-state projectors differ by a matrix with nonzero eigenvalues , which proves this identity. Also the pure-target upper bound on trace distance gives . To see the mixed-state step, write and use convexity of the trace norm followed by the Cauchy-Schwarz inequality:Finally, trace-distance contraction under quantum channels gives . This follows from : the adjoint channel is positive and unital, so its image of any effect is still an effect.
The triangle inequality now yieldsThus the cloning failure bound from trace-distance contraction isand in particular . For positive priors , another Cauchy-Schwarz inequality givesso the average rejection probability satisfiesFor equal priors, one may take ; the same choice is a strict lower bound on worst-case rejection. This proves a quantitative version of the no-cloning theorem for the bank's all-pass test. It concerns an unconditional attempt: heralded success cannot be postselected while omitting failed attempts from the accounting.
Past exam of the mathematics course of the University of Cambridge 2004 iii Paper 54 3 Solution Created 2026-10-03 Updated 2026-10-14
Let and choose uniformly from the finite family . All bounds below must hold for every pair of distinct inputs .
A universal hash family, also called universal2, satisfies . A strongly universal hash family satisfiesThus the two outputs are independent and uniform; summing over gives the collision condition. An almost strongly universal hash family permits a larger conditional guessing bound. In the -almost-strongly-universal convention used here,equivalently . Necessarily , with giving strong universality. Stating this normalization matters because the name alone does not specify the allowed forgery probability.
Here is an explicit polynomial almost strongly universal hashing construction and a one-use message authentication protocol. Use a publicly specified finite field , where . Encode a fixed-length -bit message as field elements , padding the final block in a fixed way. Both parties know the length, so this encoding is injective. They share independent uniform secret field elements , requiring shared secret bits. DefineFor every message, the output is uniform because of . For distinct messages and prescribed tags , the condition determines exactly one value of for each . The remaining condition isIts left-hand side has a nonzero coefficient of positive degree, so subtracting the specified constant gives a nonzero polynomial of degree at most . By the root bound for a polynomial, there are at most possible field elements . Consequentlyand this is an -almost-strongly-universal family with , provided . The powers start at one deliberately: a message coefficient at power zero could give a known constant tag shift, allowing a deterministic substitution.
Alice sends the message and its tag over the public channel. Bob accepts only if his independently computed tag agrees. An attacker who has seen no tag guesses one with probability . After seeing a valid pair , an attacker substituting a different message and any chosen tag succeeds with conditional probability at most . This remains true when the choice of depends on the observed pair: the bound is uniform over all those choices. More explicitly, the observed tag leaves uniform because each possible has exactly one compatible secret mask .
For a desired forgery bound , choose . Since and , the substitution bound is at most . The secret requirement isFor a long message this is much shorter than its bits. This is Wegman–Carter authentication: a keyed hash plus a fresh secret one-time pad on the tag. It authenticates the message rather than concealing its contents. Use the key once for the guarantee just established; multiple authenticated messages require fresh masks and a reuse security analysis. Authenticate lengths and sequence identifiers too if variable lengths or replay protection are required.
Past exam of the mathematics course of the University of Cambridge 2004 iii Paper 54 4 Solution Created 2026-10-03 Updated 2026-10-14
Compute the honest one-qubit density operators in the computational basis. Writing and , the two quantum state ensembles giveThe equality includes the off-diagonal coherence; comparing only the basis outcome probabilities would not suffice.
The protocol is perfectly hiding against Bob when Alice is honest. Independence of the honest preparations makes his full received density operator . For any POVM , including collective measurements and measurements using ancillas, the Born rule gives the same outcome probabilities . Thus no measurement supplies information about the committed bit.
It is not binding against Alice. Here is an explicit ensemble-steering attack on quantum bit commitment. For each position, Alice prepares the normalized two-qubit pure stateretains and sends . Its partial trace on is the honest common density operator. She sends the halves of independent copies while retaining all the halves, and chooses her bit only at unveiling.
To open one, she makes a projective measurement of each retained qubit in the computational basis. Outcome zero has probability and prepares Bob's state ; outcome one has probability and prepares . She announces that list. It has exactly the honest bit-one distribution, and every declared-state test passes.
To open zero, she instead measures each retained qubit using a three-outcome POVM with effects , whereAll effects are positive. Their diagonal sums are and , and the off-diagonal sum is zero, so . This establishes that the proposed POVM is physically valid.
To verify the conditional states directly, the coefficient matrix of , with Bob's index as the row and Alice's as the column, isA real rank-one effect on Alice's half gives the unnormalized Bob state vector . For the three effects above,Their squared norms are therefore , exactly the honest bit-zero probabilities, and Bob's conditional pure states are the corresponding declared states. Independent measurements on the retained halves produce the honest distribution of the entire list, so even checks on the declared frequencies do not defeat the attack. Every declared-state projector test again succeeds.
Alice can consequently unveil either bit with acceptance probability one, without having chosen it when sending the qubits. This is the Hughston–Jozsa–Wootters theorem mechanism implemented by an explicit measurement, rather than merely an appeal to the general impossibility of perfectly hiding and binding quantum bit commitment.
Past exam of the mathematics course of the University of Cambridge 2005 ia Paper 2 10F Solution Created 2026-09-24 Updated 2026-10-14
Use the intended model of independent random variables with exponential distributions of rates . For , independence gives the survival functionThusThe variance is , obtained from the standard first two exponential moments, and .
For these competing exponential clocks, ties have probability zero. Integrating over Alice's firing time givesLet denote the event that the next shot hits, and use the stated success probability as . Bill's corresponding conditional success probability is one. The law of total probability givesThe Bayes' theorem therefore yields
The printed assumptions specify the two marginal exponential distributions but do not explicitly specify their independence. The answers above require that extra assumption; marginals alone do not determine the race. For a concrete counterexample, take one and set , . These have the required marginals, but ; if , Alice always fires first and . Thus the independence qualification changes actual answers, rather than merely their derivation.
Past exam of the mathematics course of the University of Cambridge 2005 ia Paper 2 11F Solution Created 2026-09-24 Updated 2026-10-14
All the following distributions are conditional on the point lying in the unit disk. Initially the joint probability density of is on the square. The disk has area , so the conditioning event has probability . Dividing by this probability gives the constant conditional density on the disk, proving its uniform distribution there.
The polar coordinates have Jacobian determinant . ConsequentlyIntegrating the joint probability density gives and . Since the joint density equals the product of these marginal densities on a product support, and are independent. In particular has the uniform distribution on .
The second change of variables preserves the angle and changes the radius toThe event has probability zero, so arbitrary definitions at that point have no effect on the distribution. For , monotonicity of the logarithm givesSince is a function of , it remains independent of the uniform angle. Hence the new joint probability density isFinally, has polar Jacobian determinant . Dividing the preceding density by gives the Cartesian joint probability densityThis factors into two standard normal distribution densities on . Thus and are independent, each with mean zero and variance one. This derivation is the radial form of the Box-Muller transform.
Past exam of the mathematics course of the University of Cambridge 2005 ia Paper 2 12F Solution Created 2026-09-24 Updated 2026-10-14
For each , let be the relative rank of among , with the smallest value assigned rank one. Then . The independent relative ranks of a uniform random permutation can be proved directly: for any choices , insert the index at position in the list of previous indices ordered by their values. After all insertions, assign the values along that list. This is a unique permutation with those relative ranks, and conversely every permutation yields one such insertion sequence.
There are possible insertion sequences, all equally likely because the uniform random permutation is uniform. ThusThe ranks are independent and each is uniform on its possible values. It follows that the independent record indicators haveThe first indicator is the constant one, which is also independent of the others. For , additivity of expectation and variance additivity for independent random variables giveHere is the harmonic number.
Let be the year index of the second record. For , independence givesThe empty product for is one. There is no second record in the first years with probabilityThis exposes a finite-horizon qualification in the final request: a permutation of length alone does not specify when a record outside those years will occur. Under the usual continuation by an infinite sequence of independent, identically distributed observations with a continuous distribution, the same relative-rank argument holds for every finite prefix. Then for every , and . These probabilities sum to one, so the second record occurs almost surely, butThe expected number of additional years after year one, , is also infinite. This is the first-sample case of the waiting time for a new record after a fixed sample.
If instead one asks for the mean year conditional on the second record occurring within the stated years, then, for ,The mean additional wait under that conditioning is this value minus one. These are distinct questions: assigning whenever no second record occurs in the finite horizon also gives an infinite unconditional mean, whereas a censored observation has finite expectation by the tail-sum formula for expectation.
Past exam of the mathematics course of the University of Cambridge 2005 ia Paper 2 3F Solution Created 2026-09-24 Updated 2026-10-14
Normalize the probability density function using :The corresponding Weibull distribution has survival functionSince the distribution is continuous, the choices and have the same probabilities. The conditional probability is consequentlyFor and , the supplied inequality, applied to , gives . Taking exponentials yieldsThis expresses the increasing hazard function : surviving to a later age shortens the remaining lifetime in this conditional distribution. At equality holds, as expected from the memoryless property of the exponential distribution.
Past exam of the mathematics course of the University of Cambridge 2005 ia Paper 2 9F Solution Created 2026-09-24 Updated 2026-10-14
The expectation of a complex random quantity is defined through its real and imaginary parts. Both and are bounded, so all expectations below exist. Expand the addition formulae and apply the expectation of a product of independent random variables identity:Combining real and imaginary parts provesFor the simple symmetric random walk, write , with independent increments satisfying . The usual casino model uses these independent, or conditionally fair, increments. Their characteristic function is , so repeated factorization givesThis is real for real . Equivalently, the distribution of is symmetric, making .
For any integer , Fourier orthogonality givesThe random walk has finite support, so we may interchange its finite expectation with this integral. ThereforeFor even , evenness and reflection symmetry about reduce this toFor odd , has odd parity and cannot be zero, so . As a separate combinatorial check, for the return probability is , since exactly positive increments are required.
Past exam of the mathematics course of the University of Cambridge 2005 ib Paper 2 20D Solution Created 2026-09-24 Updated 2026-10-14
The transition row sums to one, since . From any state the Markov chain can reach zero, and from zero consecutive upward moves reach every state; hence it is irreducible. Its self-transition at zero has probability , so it is aperiodic. It is the reflected chain with geometric downward jumps.
Put for the hitting problem. The first-step equations for areSubtracting times the equation at gives the linear recurrence relation, valid for ,The separate boundary equation at is . It must not be replaced by the linear recurrence relation with : the absorbing hitting convention at zero is different from applying a first-step return equation there.
For , the linear recurrence relation has roots and , so for . The boundary equation gives . If , then and boundedness of probabilities forces , hence . If , the repeated-root solution is ; boundedness again gives and the boundary equation gives .
For , and the nonnegative harmonic candidate , together with , satisfies every first-step equation. Hitting-by-time- probabilities start from zero off the target and iterate those equations, so by induction they are bounded above by this candidate. Taking their increasing limit gives . But the general bounded solution has limit as , forcing under that bound. ThusIn particular the transient exponent is , fixed by the original boundary equation.
The probability of a subsequent return to zero when starting there is . It is one for , so the Markov chain is recurrent there. For it equals , so the irreducible Markov chain is transient.
For a stationary probability vector , balance at zero and one gives . Subtracting adjacent balance equations givesso this initial ratio propagates and . It can be normalized only when . In that caseDirect substitution verifies all balance equations, including . An irreducible Markov chain admitting this stationary probability law is positive recurrent, with mean return time . At the linear recurrence relation and boundary relation force every equal; no such nonzero sequence is summable. The recurrent chain is therefore null recurrent. In summary,
Past exam of the mathematics course of the University of Cambridge 2005 ib Paper 2 9D Solution Created 2026-09-24 Updated 2026-10-14
In a finite two-person zero-sum game the row player chooses , the column player chooses , and the row player receives while the column player receives . The row player maximizes that payoff and the column player minimizes it. Mixed strategies are probability vectors and , giving expected row payoff .
Against a fixed row mixture, the worst column is a pure column, so the row problem introduces its guaranteed payoff :Similarly the column player minimizes an upper guarantee :The values are unrestricted real variables; no positivity shift of the matrix is required.
To see the linear programming duality explicitly, introduce nonnegative multipliers for the first problem's payoff inequalities and multiplier for its normalization. Its upper-bound Lagrangian isThe supremum over free and nonnegative is finite precisely when and , and is then . Minimizing it gives the displayed column problem, proving that the programs are a dual pair.
A sufficient optimality certificate is a pair of probability vectors and a common value satisfyingEquivalently, both programs are feasible with equal values. Positive-probability rows then have and positive-probability columns have , the complementary slackness conditions. These conditions certify a saddle point and hence optimal mixed strategies for both players.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 12 2 Solution Created 2026-10-03 Updated 2026-10-14
Take and , as required for the displayed sparse scaling and the later normalization. A strictly balanced graph satisfies for every proper nonempty subgraph . This forces to be connected and to have no isolated vertices: otherwise a component of at least the average density, or deletion of the isolated vertices, violates strict balance. Copies here are subgraphs, not induced subgraphs.
For fixed , the factorial moment counts ordered -tuples of distinct copies all present in the binomial random graph. The contribution of vertex-disjoint copies is exactlyThe factor removes the multiple embeddings of each copy coming from its graph automorphisms. For an overlapping tuple, let be its union. There are placements of each fixed union type, and the probability its edges are present is . When adding a copy meeting the earlier union in vertices and edges, the exponent changes byIt is strictly negative if this intersection is a proper nonempty subgraph, and zero only for an empty intersection or a whole copy. In particular the first vertex-overlapping copy has a proper nonempty intersection: the preceding copies are vertex-disjoint, and a connected copy contained in their union would have to equal one of them, contrary to distinctness. Its contribution is therefore strictly negative; later additions cannot undo that loss. Only finitely many union types occur for fixed , so their total contribution is . We have proved all the factorial moment limits, and the allowed factorial-moment criterion for Poisson convergence givesThis is the Poisson limit for strictly balanced subgraph counts.
The pendant-edge graph has density , whereas its proper core has density . Thus is not strictly balanced. The complete graph is strictly balanced, with 24 graph automorphisms, so at its copy count tends to .
Every copy has a unique four-vertex clique core and one selected edge joining it to a fifth vertex. For any four-set , let count the ambient edges between and its complement. Then , with mean . It is independent of the internal edges determining whether is a clique. Choose . A Chernoff bound and a union bound giveTherefore, simultaneously for every actual core, its number of pendant extensions is . Extra ambient edges cause no overcount: each selected seven-edge subgraph has exactly one core and one pendant edge. Summing over the cores yieldsbecause is uniformly tight. This is the pendant extensions of sparse clique copies mechanism. For , neither endpoint of is an integer, and its only nonnegative integer is . Convergence in distribution consequently givesThe positive- assumption matters: the quotient printed in the question is undefined when .
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 12 3 a Solution Created 2026-10-03 Updated 2026-10-14
If the random k-out graph with is disconnected, one of its connected components of a graph has size . The lower bound follows because every vertex chooses two distinct neighbours inside its component. For a specified -set , absence of crossing edges requires every choice at a vertex in to stay in , and every choice outside to stay outside. Independence of choices at different vertices gives exactlyFor , the two ratios are at most and . Indeed each of the factors , , is at most , and the complementary statement is identical. Put . The binomial coefficient bound follows by bounding the probability of successes in by one. Thus the union bound givesFor , the last summands are at most , whose sum from three tends to zero. For , they are at most , again summing to zero. ThereforeThe proof bounds all possible small components rather than assuming the dependent undirected edges behave like a binomial random graph.
