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, so
This 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 . Hence
The 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 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
}
The first is a discrete uniform distribution; the second is a Bernoulli distribution on Boolean values. Their exact mathematical probability mass functions are
Each support contains exactly the positive-probability outcomes once, and the probabilities sum to one. 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 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
}
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 "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.
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)
  }
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.
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
      }
  }
Assume the given finite probability distributions are fixed and 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, proving
For 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 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;
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.
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, so
The shared boundary has zero probability, so it is not counted twice in this joint density calculation.
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.
For , the six oriented distances give respective probabilities
Their sum is , the expected number of black beads in the white component. As a check, summing the formula from (i) and using gives the general value , again equal to when .
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, so
for every finite initial size . Conditioning on the first individual's outcome and applying the law of total probability gives
The equation factors as
Its 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 probability
Hence 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 . Therefore
This 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 states
Because the events form a partition of a sample space of the sample space, pointwise. Multiply by and use linearity of expectation to obtain
An 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.
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 probabilities
Under 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 is
In 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 . Hence
The 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.