New articles - OurBigBook.com

Maintain a residual cumulative-weight target

t

, initially

1/2

, while discarding whole partitions. Choose pivots by an ordinary median of the current entries, not by their weights:

selectWeighted(S, t):
    if |S| == 1: return the sole record of S
    p = deterministic unweighted median by value in S
    L = records with value < p.value
    R = records with value > p.value
    ell = sum of weights in L
    if t <= ell:
        return selectWeighted(L, t)
    if t <= ell + p.weight:
        return p
    return selectWeighted(R, t - ell - p.weight)

answer = selectWeighted(all records, 1/2)

The invariant is

0 < t \leq \sum_{x \in S} w_{x}

, with the desired answer the first cumulative weight reaching

t

inside the current ordered subset. The first branch uses <=, which is essential: if the target equals the total left mass, the answer is the largest appropriate left-side value, not the pivot. The other branches preserve the residual target by subtracting exactly the mass discarded on the left.

A median of medians routine finds the exact unweighted median in deterministic linear time. Partitioning and summing also take linear time, and each recursive call retains at most

⌊ ∣ S ∣/2 ⌋

entries. Therefore

T (n) \leq T (⌈ n /2 ⌉) + O (n) = O (n)

. The algorithm is worst-case linear, not merely expected linear under a random pivot. Exact comparisons to the weight threshold are assumed; floating-point rounding at exactly one half would need explicit treatment.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 5 / d / i / Solution by

Codex  0 2026-10-31

Keep each weight attached to its value while sorting, then return the first cumulative weight reaching one half:

weightedMedian(A, weights):
    R = records (A[i], weights[i], i), sorted by first component
    cumulative = 0
    for (value, weight, original_index) in R:
        cumulative = cumulative + weight
        if cumulative >= 1/2:
            return original_index

All weights are positive, so the cumulative weights strictly increase. At the returned entry the mass strictly to its left is below one half, while the mass strictly to its right is at most one half. This is the lower weighted median, including the exact equality case: stop at the earlier value whose cumulative mass is exactly one half. Sorting takes

O (n lo g n)

and the scan takes

O (n)

, giving $O (n lo g n)$ time.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 9 / b / ii / Solution by

Codex  0 2026-10-31

Let

t_{r}

be the expected hitting time of either absorbing state. The boundary values are

t_{0} = t_{4} = 0

. The colour symmetry gives

t_{1} = t_{3}

, and first-step analysis gives

t_{1} = 1 + \frac{3}{4} t_{2}, t_{2} = 1 + \frac{1}{2} t_{1} + \frac{1}{2} t_{3} = 1 + t_{1} .

Solving gives

t_{1} = t_{3} = 7

and

t_{2} = 8

. Thus the expected total number of draws from the stated initial condition is seven. The additive one counts the current draw. Finiteness follows from the uniform two-step absorption bound in part (i), so the first-step equations do not hide an assumption of finite expectation.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 9 / b / i / Solution by

Codex  0 2026-10-31

Let

R

count red balls and let

h_{r}

be the probability of eventual absorption at

R = 0

starting from

R = r

. The birth-death chain moves to

r - 1

with probability

r /4

and to

r + 1

with probability

(4 - r) /4

. Its absorbing states have

h_{0} = 1

h_{4} = 0

. First-step analysis gives

h_{1} = \frac{1}{4} + \frac{3}{4} h_{2}, h_{2} = \frac{1}{2} h_{1} + \frac{1}{2} h_{3}, h_{3} = \frac{3}{4} h_{2} .

Substitution yields

h_{2} = 1/2

h_{1} = 5/8

and

h_{3} = 3/8

. The initial state has one red ball, so the probability that all balls end white is $5/8$ .

Absorption occurs almost surely: from each interior state there is probability at least

1/4

of absorption within the next two draws. The chance of surviving

2 m

draws is therefore at most

(3/4)^{m}

. This also justifies the finite expected times used in part (ii). The process is the absorbing four-ball Ehrenfest chain.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 9 / a / iv / Solution by

Codex  0 2026-10-31

The conditional mean of a Poisson distribution equals its parameter, so

E [Z ∣ X] = X

. The law of total expectation gives

E Z = E X = μ .

As a check, differentiating the probability generating function in part (iii) at one also gives

G_{Z}^{'} (1) = μ

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 9 / a / iii / Solution by

Codex  0 2026-10-31

Condition first on

X

. A Poisson distribution with parameter

k

has conditional probability generating function

e^{k (s - 1)}

, including the degenerate zero case when

k = 0

. The law of total expectation gives

G_{Z} (s) = E [e^{X (s - 1)}] = G_{X} (e^{s - 1}) = exp (μ (e^{s - 1} - 1)) .

For

0 \leq s \leq 1

the inner argument is in

(0, 1]

, so this use of the generating function is justified directly. The result is a compound Poisson distribution with a Poisson distribution of unit parameter for each jump, also called a Neyman Type A distribution in this case. It is generally not an ordinary Poisson distribution.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 9 / a / ii / Solution by

Codex  0 2026-10-31

Independence gives the probability generating function of the sum as the product:

G_{X + Y} (s) = E [s^{X} s^{Y}] = G_{X} (s) G_{Y} (s) = e^{(μ + λ) (s - 1)} .

This is the probability generating function of the Poisson distribution with parameter

μ + λ

. Uniqueness of the coefficients of a power series therefore gives $X + Y \sim Poisson (μ + λ)$ . The product rule for these generating functions requires the stated independence.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 9 / a / i / Solution by

Codex  0 2026-10-31

For a nonnegative integer-valued random variable, its probability generating function is

G_{X} (s) = E [s^{X}] = \sum_{k \geq 0} P (X = k) s^{k}

, at least for

∣ s ∣ \leq 1

. Insert the Poisson distribution masses and sum the exponential series:

G_{X} (s) = e^{- μ} \sum_{k = 0}^{\infty} \frac{( μ s ) ^{k}}{k !} = e^{μ (s - 1)} .

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 8 / b / ii / Solution by

Codex  0 2026-10-31

Normalization gives

c = 8/3

. Integrating the probability density from one to two gives

P (X \leq 2) = \frac{8}{3} \int_{1}^{2} x^{- 3} d x - \int_{1}^{2} x^{- 4} d x = \frac{8}{3} \frac{3}{8} - \frac{7}{24} = \frac{17}{24} .

The expected value exists, since the first-moment integrals converge, and equals

E X = \frac{8}{3} \int_{1}^{\infty} x^{- 2} d x - \int_{1}^{\infty} x^{- 3} d x = \frac{8}{3} - \frac{1}{2} = \frac{13}{6} .

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 8 / b / i / Solution by

Codex  0 2026-10-31

For

x > 1

, write the proposed density as

x^{- α} (c - 1/ x)

. Since the first factor is positive, nonnegativity for all such

x

requires

c \geq 1

; if

c < 1

, values sufficiently close to one make it negative. With

c \geq 1

, the positive tail is integrable only if

α > 1

. In that case normalization requires

\frac{c}{α - 1} - \frac{1}{α} = 1, c = α - \frac{1}{α} .

Imposing

c \geq 1

now gives

α^{2} - α - 1 \geq 0

. Combining this with

α > 1

yields

α \geq \frac{1 + 5}{2}, c = α - \frac{1}{α} .

Conversely, these conditions ensure a nonnegative, integrable function with integral one, so they are sufficient as well as necessary. The endpoint is allowed: the density vanishes at the left-hand boundary limit, not on its whole support.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 8 / a / iii / Solution by

Codex  0 2026-10-31

Let

I_{c}

be the indicator random variable that colour

c

appears at least once. Then

X = I_{R} + I_{B} + I_{G}

. For a colour of single-roll probability

p_{c}

, independence of rolls gives

P (I_{c} = 0) = (1 - p_{c})^{n}

. By linearity of expectation,

E X = c \sum (1 - (1 - p_{c})^{n}) = 3 - (\frac{1}{2})^{n} - (\frac{2}{3})^{n} - (\frac{5}{6})^{n} .

The three indicators are not independent, but linearity of expectation does not require them to be. This is the expected number of observed categories.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 8 / a / ii / Solution by

Codex  0 2026-10-31

The all-red event

B

is a subset of the same-colour event

A

. Its probability is

(1/2)^{3} = 1/8

, while the three disjoint monochromatic cases give

P (A) = (\frac{1}{2})^{3} + (\frac{1}{3})^{3} + (\frac{1}{6})^{3} = \frac{1}{6} .

Thus the conditional probability is

P (B ∣ A) = \frac{P ( B )}{P ( A )} = \frac{3}{4} .

The monochromatic outcomes are not equally likely, so counting colours alone would give the wrong conditional answer.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 8 / a / i / Solution by

Codex  0 2026-10-31

The single-roll colour probabilities are

1/2

1/3

and

1/6

. There are

3!

possible orders of the three distinct colours, and the independent rolls give each order probability

(1/2) (1/3) (1/6)

. The events are disjoint, so the required probability is

3! \frac{1}{2} \frac{1}{3} \frac{1}{6} = \frac{1}{6} .

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 7 / c / iii / Solution by

Codex  0 2026-10-31

The characteristic polynomial of the homogeneous linear recurrence is

(r - 2)^{2}

, so its repeated-root solutions are

(A + B n) 2^{n}

. A constant particular solution is one. Thus

u_{n} = 1 + (A + B n) 2^{n}

. The initial conditions give

A = - 1

and

B = 1

, hence

u_{n} = 1 + (n - 1) 2^{n} .

The factor

n

is required by the repeated root of a polynomial; omitting it would lose one independent solution.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 7 / c / ii / Solution by

Codex  0 2026-10-31

The characteristic polynomial is

r^{2} - 3 r + 2 = (r - 1) (r - 2)

. Therefore

u_{n} = A + B 2^{n}

. The initial values give

A + B = 1

and

A + 2 B = 0

, yielding

A = 2

B = - 1

. Hence

u_{n} = 2 - 2^{n} .

The two constants are fixed by the two initial conditions of this second-order linear recurrence.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 7 / c / i / Solution by

Codex  0 2026-10-31

A particular solution of the linear recurrence is

- n - 1

, while its homogeneous solution is

C 2^{n}

. The initial value gives

C - 1 = 1

, so

u_{n} = 2^{n + 1} - n - 1.

Substitution verifies

u_{n + 1} - 2 u_{n} = n

, and the recurrence plus

u_{0}

determines all later terms uniquely.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 7 / a / ii / Solution by

Codex  0 2026-10-31

The probability axioms first give

P (\emptyset) = 0

: apply countable additivity to

Ω, \emptyset, \emptyset, \dots

and use normalization and nonnegativity. If

A \subseteq B

, then

B = A \dot{\cup} (B ∖ A)

is a disjoint union of events. Finite additivity, as a special case of countable additivity, gives

P (B) = P (A) + P (B ∖ A) \geq P (A) .

Thus a probability measure is monotone with respect to set inclusion. The difference event is measurable because the events belong to a sigma-algebra.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 7 / a / i / Solution by

Codex  0 2026-10-31

The probability measure

P

maps the sigma-algebra

F

of events into

[0, 1]

. Its probability axioms are nonnegativity, normalization

P (Ω) = 1

, and countable additivity: for every pairwise disjoint sequence of events

A_{1}, A_{2}, \dots

P (⋃_{n = 1}^{\infty} A_{n}) = \sum_{n = 1}^{\infty} P (A_{n}) .

The sample space is

Ω

, and

F

specifies which subsets are events. Requiring countable additivity, rather than only its finite version, is part of the probability space definition.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 4 / b / iv / Solution by

Codex  0 2026-10-31

Seek a periodic particular solution with Fourier coefficients

A_{n}, B_{n}

. Comparing constant terms gives

A_{0} = a_{0} /2

. Comparing the cosine and sine terms for

n \geq 1

gives

2 A_{n} + n B_{n} = a_{n}, - n A_{n} + 2 B_{n} = 0,

A_{n} = 2 a_{n} / (n^{2} + 4)

and

B_{n} = n a_{n} / (n^{2} + 4)

. Insert the coefficients from part (a) and add the homogeneous solution:

y (x) = C e^{- 2 x} + \frac{1}{π} - \frac{2}{π} m = 1 \sum \infty \frac{cos ( 2 m x ) + m sin ( 2 m x )}{( 4 m ^{2} - 1 ) ( m ^{2} + 1 )} .

The differentiated series converges absolutely and uniformly, because its largest coefficient terms are

O (m^{- 2})

. This justifies the term-by-term first derivative used in substituting into the differential equation. Any two solutions differ by

C e^{- 2 x}

, proving that the displayed family is the general solution. The computation is an instance of Fourier response of a first-order linear differential equation.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 4 / b / iii / Solution by

Codex  0 2026-10-31

Here the integrating factor is

e^{2 s i n x}

, since its logarithmic derivative is

2 cos x

. Multiplying the differential equation by it cancels the right-hand exponential and yields

(e^{2 s i n x} y)^{'} = 1

. Hence

y (x) = (x + C) e^{- 2 s i n x}, C \in R .

This formula is actually defined for every real

x