To obtain the st head on toss , the first tosses must contain exactly heads, and the last toss must be a head. There are choices of the first head positions. By independence, each such arrangement followed by a head has probability . The arrangements are disjoint, soThis is the negative binomial stopping argument, with counting all tosses up to and including the st success. It is not merely the probability of heads somewhere among tosses: the last toss is prescribed to be a head.
For each student, the probability of both falling asleep and dreaming about mathematics is . These indicators are independent across students, so the same Poisson thinning calculation gives, for the requested count ,Explicitly , the probability generating function of that Poisson distribution.
Given , there are exactly independent opportunities to stay awake, each with probability . HenceThe standard binomial distribution formulas are and . The Poisson distribution formulas are , , and therefore . By the law of total expectation,Using the definition of covariance,Thus and are not independent, even though the separate awake and asleep counts produced by Poisson thinning are independent.
For The first is a discrete uniform distribution; the second is a Bernoulli distribution on Boolean values. Their exact mathematical probability mass functions areEach support contains exactly the positive-probability outcomes once, and the probabilities sum to one.
Uniform, require a nonempty integer interval. Compute its size in Long before converting to Double, avoiding integer overflow in u-l+1. For Flip, require , and omit zero-probability outcomes from the reported support.class Uniform(l: Int, u: Int) extends FiniteDist[Int] {
require(l <= u)
private val size = u.toLong - l.toLong + 1L
def getDom: List[Int] = {
val result = List.newBuilder[Int]
var x = l.toLong
while (x <= u.toLong) { result += x.toInt; x += 1L }
result.result()
}
def getProb(x: Int): Double =
if (l <= x && x <= u) 1.0 / size.toDouble else 0.0
}
class Flip(p: Double) extends FiniteDist[Boolean] {
require(0.0 <= p && p <= 1.0)
def getDom: List[Boolean] =
if (p == 0.0) List(false)
else if (p == 1.0) List(true)
else List(true, false)
def getProb(x: Boolean): Double = if (x) p else 1.0-p
}Double approximates these exact values by floating-point arithmetic. Materializing a huge support is limited by available memory; the Long calculation keeps its cardinality and endpoints arithmetically correct.Reject the empty string, because the given formula would divide by zero and no normalized probability distribution exists on its empty observed support. Remove repeated characters from The probability mass function is an empirical probability distribution:Every character occurrence contributes exactly once to the total count, so the probabilities sum to one. Absent characters have count zero. For
getDom, but include all their occurrences when computing probability.class DistFromString(s: String) extends FiniteDist[Char] {
require(s.nonEmpty)
private val chars = s.toList
private val dom = chars.distinct
def getDom: List[Char] = dom
def getProb(x: Char): Double =
chars.count(c => c == x).toDouble / chars.length.toDouble
}"Scala", the support is List('S','c','a','l'), with probabilities respectively. Here Char means the language's UTF-16 code unit, matching the supplied interface rather than assuming one Unicode code point per element.For the product of finite probability distributions, enumerate the Cartesian product of the two supports and multiply the two probability masses.Each pair appears once because both original supports have no duplicates. Exact probabilities are positive on that support, and normalization follows by finite distributivity:For the pushforward of a finite probability distribution, sum all masses in each fiber of a function; simply overwriting repeated image values would lose probability.Assume the given finite probability distributions are fixed and
def product[T,U](d: FiniteDist[T], d2: FiniteDist[U]): FiniteDist[(T,U)] =
new FiniteDist[(T,U)] {
private val dom = for (x <- d.getDom; y <- d2.getDom) yield (x,y)
def getDom: List[(T,U)] = dom
def getProb(p: (T,U)): Double = d.getProb(p._1) * d2.getProb(p._2)
}def image[T,U](d: FiniteDist[T], f: T => U): FiniteDist[U] =
new FiniteDist[U] {
private val weighted = d.getDom.map(x => (f(x), d.getProb(x)))
private val dom = weighted.map(_._1).distinct
def getDom: List[U] = dom
def getProb(y: U): Double =
weighted.foldLeft(0.0) { case (total, (z,p)) =>
if (z == y) total+p else total
}
}f is a pure total function on the source support. Distinct image values form exactly the positive-mass support. The fibers partition the original support, provingFor example, sending a discrete uniform distribution on to parity produces masses and , not four distinct outcomes. Exact algebra establishes the finite probability distribution laws; Double computes approximations, with the usual possibility of rounding and floating-point underflow for very small products.Store the current multiset in an unsorted prefix The loop invariant is , the complete array has its original multiset, every discarded entry on the left is at most every active entry, and every active entry is at most every discarded entry on the right. Thus the desired global order statistic is the local one of rank . The two-way array partition result either identifies it or excludes the pivot and the irrelevant side. The positive loop variant strictly decreases unless the procedure returns.
a[0..len); Add appends exactly as in part (a). The coupling invariant is equality of length and multiset with abstract xs, rather than equality of insertion order. Get applies quickselect:PROCEDURE Get(k: INTEGER): INTEGER;
VAR l, r, m: INTEGER;
BEGIN
ASSERT((0 <= k) & (k < len));
l := 0; r := len;
LOOP
m := Partition(l, r);
IF k = m THEN RETURN a[m]
ELSIF k < m THEN r := m
ELSE l := m+1
END
END
END Get;Balanced pivots give , whose geometric series is . More generally, choosing a uniformly random pivot before each call, by swapping a random active entry into
a[r-1], gives expected running time on distinct keys: with constant probability, the pivot is in the middle half and the retained side has size at most . Expected work over these shrinking stages is a convergent geometric series.The particular last-entry pivot in the displayed code has no unconditional expected guarantee without an input distribution. Its worst case repeatedly discards one entry. Duplicate keys require further care: on an all-equal segment, the strict partition always returns , so selecting the last rank costs even with randomized pivot positions. A three-way array partitioning that groups all keys equal to the pivot restores the usual randomized linear expectation with duplicates; alternatively the stated expectation assumes distinct keys. This is a qualification to the bound, not to the algorithm correctness of the displayed code.Source paper: released examination archive, member
2018/T/a10100w1.pdf. The cover identifies the regular Preliminary Examination in Computer Science, Trinity Term 2019, Thursday 27 June, 14:30–17:30. The archive directory does not determine the sitting. All nine questions are covered, including every printed Roman subpart.Questions 1–3 form Discrete Mathematics, 4–6 Continuous Maths, and 7–9 Probability. The printed relation in 3(c)(ii) fails to be a partial order; that issue is treated explicitly rather than silently changing the source.
Split the unit square into and . The maximum is on the first triangle and on the second, soThe shared boundary has zero probability, so it is not counted twice in this joint density calculation.
By independence, the joint probability density is the product of the two uniform distribution densities:Changing its values on the boundary does not affect any probability or expected value.
Let be the indicator that black bead belongs to the white bead's connected component. The number of such black beads is . By linearity of expectation, no independence between these indicators is needed.
The two outcomes are not independent. Conditional on the selected die, the rolls are independent, but sharing the unknown die creates statistical dependence. Each nonfavored face has probability .
The unconditional marginal distribution assigns the following probability to a on either roll:However, by the law of total probability,Thus the joint probability does not factor into the two marginals. Conditional independence given a shared latent choice does not imply unconditional independence.
This is a Galton-Watson process with offspring count with probability and with probability . The descendants of distinct initial individuals evolve independently, sofor every finite initial size . Conditioning on the first individual's outcome and applying the law of total probability givesThe equation factors asIts roots are and . Since , the second root exceeds one and cannot be a probability. Therefore and for every finite initial size. The population reaches the absorbing state zero almost surely; no choice between two admissible fixed-point probabilities remains in this subcritical case.
Every particular card is second with probabilityHence and have the same distribution, with means zero and variances one. They are not independent, since a card cannot be drawn twice.
Every ordered pair of distinct cards has probability . ThereforeThis negative covariance is the effect of sampling without replacement, not a contradiction of their identical marginals.
The finite-partition form of the law of total expectation statesBecause the events form a partition of a sample space of the sample space, pointwise. Multiply by and use linearity of expectation to obtainAn event of zero probability contributes zero to the middle expression and is omitted from the final expression, so no undefined conditional expectation is multiplied by zero.
Using the indicator random variable, sum over the values of the discrete random variable :Dividing by the positive probability proves . On the product vanishes, so no additional contribution is omitted.
For an integrable discrete random variable, the conditional expectation given an event of positive probability isThe sum ranges over the possible values of ; integrability ensures absolute convergence.
Let count the ringed birds among the two captures, and let be the event that the detector records at least one ring. The hypergeometric distribution gives the prior probabilitiesUnder the usual additional assumption of independent per-ring detection, with no false records, the likelihoods are , , and . Therefore . Applying Bayes' theorem yields . Storing only the last detected number means that a stored record does not identify how many rings were present. By label symmetry, the identity of that stored ring does not further alter this distribution.
The text specifies each ring's marginal detection probability, but does not explicitly specify independence of the detection errors. To keep this modelling qualification visible, let . The marginal detection rate only implies . Without the extra independence assumption, the full family of possible posterior distributions isIn particular . The displayed numerical answer corresponds to ; the general answer exposes exactly what the detector's marginal specification alone establishes.
The two captures form a uniform ordered sample of distinct birds, that is, sampling without replacement. By exchangeability, each of the ten birds has the same chance of occupying the second position, so the probability is . Equivalently, conditioning on the first capture gives .
Let be the event that candidate succeeds. The countable additivity axiom adds probabilities only for mutually disjoint events. Successes of different candidates are not mutually exclusive, so replacing the probability of their union by misuses that axiom. Without disjointness one obtains only the union bound, not certainty. The same sum is the expected value of the number of successes, which also need not imply at least one.
If the ten outcomes are mutually independent events, with each success probability , all fail with probability . HenceThe independence assumption is essential. The marginal probabilities alone allow any union probability from up to ; perfectly overlapping success events give the lower endpoint and disjoint successes give the upper endpoint.