Past exam of the MSc in advanced computer science course of the University of Oxford / 2021

a

Solution

Assume

0 < Z = \sum_{x} r (x) < \infty

, and work on the support

S = {x : r (x) > 0}

. In rejection sampling, choose a normalized proposal probability mass function

g

and a known finite constant

M

satisfying

r (x) \leq M g (x)

everywhere. Draw independent random variables

Y \sim g

and

U \sim Unif (0, 1)

, accepting

Y

when

U \leq r (Y) / (M g (Y))

. The joint probability of proposing and accepting

x

r (x) / M

, so the overall acceptance probability is

Z / M

and the accepted value has probability mass function

r (x) / Z

. Fresh trials therefore produce independent and identically distributed random variables with the desired probability distribution. For a fixed positive number

N

of accepted values, the sample average

N^{- 1} \sum_{i = 1}^{N} f (Y_{i})

is an unbiased estimator of the expectation when that expectation is finite. Its variance is

Var_{p} (f) / N

if the second moment is finite. Finding a valid envelope can be difficult, and a small acceptance probability makes the method expensive.

For the Metropolis–Hastings algorithm, choose a proposal transition matrix

q

and, at the current state

x

, propose

y \sim q (x, \cdot)

. Accept with the Metropolis–Hastings acceptance probability

α (x, y) = min {1, \frac{r ( y ) q ( y , x )}{r ( x ) q ( x , y )}} .

A proposal outside

S

is rejected; an impossible proposal need not be assigned a ratio. Otherwise remain at

x

. This constructs a Markov chain satisfying detailed balance with

p

, without computing

Z

or a global envelope. Estimate the expectation by averaging

f (X_{i})

over iterations, including repeated states after rejections. Keeping only accepted jumps generally changes the stationary distribution of the recorded process.

The Metropolis–Hastings algorithm produces dependent samples, so the variance of its average includes autocovariances; starting outside stationarity can also cause finite-run bias. With Markov chain irreducibility, suitable recurrence and an integrable

f

, the countable-state Markov chain ergodic theorem gives consistency. Aperiodicity is additionally needed for the usual convergence of one-time probability distributions. In contrast, accepted rejection sampling values need no initial transient. Neither method is universally faster: envelope rejection competes with the proposal quality and mixing time of the Markov chain. Nonnegativity of

f

alone does not guarantee a finite expectation or variance.

b

Solution

Here

q (x, y) = p (y)

, with fresh proposal randomness independent of the past. For

x, y \in S

, the Metropolis–Hastings acceptance probability is

α (x, y) = min {1, \frac{p ( y ) p ( x )}{p ( x ) p ( y )}} = 1.

Thus

P (x, y) = p (y)

is independent of

x

, and

X_{1}, \dots, X_{N}

are independent and identically distributed random variables with probability distribution

p

, even if

X_{0}

was chosen arbitrarily in

S

. The method becomes ordinary Monte Carlo method sampling from $p$ . The average of

f (X_{1}), \dots, f (X_{N})

is an unbiased estimator, with the variance stated in part (a). Including an arbitrary initial state would spoil this finite-sample property. This is the independent stationary proposal lemma.

c

Solution

Neither Markov chain irreducibility nor fast convergence follows from detailed balance. On two states, the identity transition matrix satisfies detailed balance for the uniform probability distribution, but neither state can reach the other.

Even after imposing Markov chain irreducibility and aperiodicity, consider

P_{ε} = (1 - ε ε ε 1 - ε), 0 < ε < \frac{1}{2} .

It satisfies detailed balance for

π = (1/2, 1/2)

. Its nontrivial eigenvalue is

1 - 2 ε

, and, from state zero, its total variation distance from

π

after

n

steps is

\frac{1}{2} (1 - 2 ε)^{n}

. This approaches zero arbitrarily slowly as

ε

decreases. Detailed balance without rapid convergence separates correctness of a stationary distribution from reachability and speed.

d

Solution

Put

a = p (x) q (x, y)

and

b = p (y) q (y, x)

. For

a + b > 0

, the off-diagonal probability flux of the proposed rule is

p (x) q (x, y) β (x, y) = a \frac{b}{a + b} = \frac{ab}{a + b} = b \frac{a}{a + b} = p (y) q (y, x) β (y, x) .

a = b = 0

, define both acceptance probabilities to be zero; both fluxes are zero. The diagonal detailed balance equations hold automatically, including the probability of rejected proposals. Summing the detailed balance equations over

x

gives stationarity:

\sum_{x} p (x) P (x, y) = \sum_{x} p (y) P (y, x) = p (y) .

The alternative rule therefore preserves $p$ . The unknown normalizing constant cancels after replacing

p

r

. This Barker acceptance probability is no larger than the Metropolis–Hastings acceptance probability for the same proposed move: if

t = b / a > 0

, then

t / (1 + t) \leq min (1, t)

. Preservation of

p

still requires separate Markov chain irreducibility and convergence checks before it guarantees useful sampling.

e

Solution

Use the Poisson distribution with probability mass function

π_{n} = e^{- λ} λ^{n} / n!

N_{0}

. A symmetric nearest-neighbour proposal with a reflecting boundary is

q (n, n + 1) = \frac{1}{2} (n \geq 0), q (n, n - 1) = \frac{1}{2} (n \geq 1), q (0, 0) = \frac{1}{2} .

All other entries vanish. In particular, the boundary proposal does not force a move to one: retaining the probability

q (0, 0) = 1/2

makes

q (0, 1) = q (1, 0)

The adjacent ratios of the Poisson distribution are

π_{n + 1} / π_{n} = λ / (n + 1)

and

π_{n - 1} / π_{n} = n / λ

. The Metropolis–Hastings acceptance probability consequently gives

u_{n} = \frac{1}{2} min {1, λ / (n + 1)}, d_{n} = \frac{1}{2} min {1, n / λ} (n \geq 1), d_{0} = 0,

where the symbol

u_{n}

denotes the upward transition probability. Thus the complete transition matrix is

P (n, n + 1) = u_{n}, P (n, n - 1) = d_{n}, P (n, n) = 1 - u_{n} - d_{n},

with no downward entry at zero and all other entries zero. In matrix form,

P = 1 - u_{0} d_{1} 0 ⋮ u_{0} 1 - u_{1} - d_{1} d_{2} ⋮ 0 u_{1} 1 - u_{2} - d_{2} ⋱ 00 u_{2} ⋱ \dots \dots \dots ⋱ .

Every row is nonnegative and sums to one. An executable Python step of this Poisson Metropolis chain is:

def poisson_step(n, lam, rng):
    if lam <= 0 or n < 0 or int(n) != n:
        raise ValueError("require lam > 0 and an integer n >= 0")
    y = n + 1 if rng.random() < 0.5 else max(0, n - 1)
    ratio = lam / (n + 1) if y > n else n / lam if y < n else 1.0
    return y if rng.random() < min(1.0, ratio) else n

Supply a pseudorandom number generator such as random.Random(2021) and retain each returned state, including repeats. No normalizing constant or evaluation of a factorial is needed by the algorithm.

f

Solution

For each adjacent pair, the detailed balance equations follows directly:

π_{n} P (n, n + 1) = \frac{1}{2} π_{n} min (1, π_{n + 1} / π_{n}) = \frac{1}{2} min (π_{n}, π_{n + 1}) = π_{n + 1} P (n + 1, n) .

For nonadjacent distinct states both fluxes vanish, and diagonal fluxes agree trivially. Since

\sum_{n} π_{n} = e^{- λ} \sum_{n} λ^{n} / n! = 1

, this is a genuine stationary distribution, rather than merely an invariant measure of infinite mass.

Every upward and downward transition probability between neighbouring states is positive for

λ > 0

. Any two states can therefore be joined by a finite path of positive probability: the Markov chain is irreducible. Moreover,

P (0, 0) = 1 - \frac{1}{2} min (1, λ) \geq \frac{1}{2} > 0.

State zero has period one; Markov chain irreducibility makes every state aperiodic. Finally, the standard countable-state recurrence theorem states that an irreducible Markov chain admitting a stationary distribution of total mass one is positive recurrent, with that stationary distribution unique. The countable-state Markov chain convergence theorem then states that Markov chain irreducibility, positive recurrence and aperiodicity imply

P^{k} (i, j) \to π_{j}

for all states

i, j

. The hypotheses just verified hold on the infinite state space

N_{0}

, not merely on a numerical truncation.^[ref]

Consequently, the unique stationary distribution and the limiting distribution are both $Poisson (λ)$ , from every initial state. The countable-state Markov chain ergodic theorem also gives

N^{- 1} \sum_{k = 1}^{N} f (X_{k}) \to \sum_{n} π_{n} f (n)

almost surely whenever

\sum_{n} π_{n} ∣ f (n) ∣ < \infty

.^[ref]

2

a

Solution

Variational inference replaces exact Bayesian inference by an optimization problem over a tractable family

q_{λ} (z)

. A guide program samples from this approximating family. Optimizing an evidence lower bound is equivalent to minimizing

D_{KL} (q_{λ} ∥ p (\cdot ∣ x))

. Its appeal is that a fitted approximation can be cheap to sample and may scale well when an exact posterior distribution is inaccessible. A restricted family, such as mean-field variational inference, can miss dependence or entire modes; a local optimum can add further error. More optimization cannot remove approximation error caused by an inadequate family.

Monte Carlo method inference instead estimates posterior expectations using simulated values or weighted values. Examples include rejection sampling, importance sampling and Markov chain Monte Carlo. Under their respective support and convergence assumptions, increasing computation can yield consistent estimates without choosing a finite-dimensional posterior family. Their uncertainty includes simulation error; an inefficient proposal or slow mixing time can make that error large. Markov chain Monte Carlo additionally requires convergence and dependence diagnostics.

The central trade-off is optimization within an approximate family versus simulation under a target probability distribution. It is not an absolute distinction between deterministic and random computation: variational inference often uses Monte Carlo method estimates of its gradient, while Monte Carlo method inference may use fitted proposals. Neither method automatically guarantees accurate uncertainty estimates or superiority at a fixed computational budget.

b

Solution

Let

0 < p (x) < \infty

, take

q_{λ}

supported where

p (z, x) > 0

, and assume the following expectations exist. By the definition of Kullback-Leibler divergence and Bayes' theorem,

D_{KL} (q_{λ} ∥ p (\cdot ∣ x)) = E_{q_{λ}} [lo g q_{λ} (z) - lo g \frac{p ( z , x )}{p ( x )}] = lo g p (x) - E_{q_{λ}} [lo g p (z, x) - lo g q_{λ} (z)] .

Therefore the evidence lower bound is

L (λ) = E_{q_{λ}} [lo g p (z, x) - lo g q_{λ} (z)] = lo g p (x) - D_{KL} (q_{λ} ∥ p (\cdot ∣ x)) .

Nonnegativity of Kullback-Leibler divergence proves

L (λ) \leq lo g p (x)

. The marginal likelihood

p (x)

is constant with respect to the variational parameter

λ

, so maximizing

L

minimizes the stated Kullback-Leibler divergence.

The practical advantage is that evaluating logarithms of joint probabilities and

lo g q_{λ}

requires no evaluation of the usually intractable marginal likelihood. One can estimate

L

and its gradient with Monte Carlo method. Equality with the log marginal likelihood occurs only when

q_{λ} = p (\cdot ∣ x)

almost everywhere. Merely maximizing the evidence lower bound over a restricted family neither computes the exact posterior distribution nor proves that the maximum attains this equality.

c

Solution

The discrete base factors in the displayed construction inherit their variational parameters. Accordingly write $s_{λ} (ε)$ , not a parameter-independent

s (ε)

, for the joint base probability mass function or probability density function. The continuous noise factors can be parameter independent while the discrete factors are

λ

dependent. Calling the entire base law parameterless while retaining its nonzero score function would be inconsistent.

Let

t_{λ}

push the base law forward to

q_{λ}

, and define

W_{λ} (ε, x) = lo g p (t_{λ} (ε), x) - lo g q_{λ} (t_{λ} (ε)) .

Use a fixed base measure

ν

, with counting measure for discrete coordinates and Lebesgue measure for continuous coordinates. Assume locally parameter-independent support, differentiability and an integrable domination permitting differentiation under the integral sign. A valid reparameterization gradient gives

L (λ) = \int s_{λ} (ε) W_{λ} (ε, x) d ν (ε) .

Apply the product rule before simplifying:

\nabla_{λ} L = \int [(\nabla_{λ} s_{λ}) W_{λ} + s_{λ} \nabla_{λ} W_{λ}] d ν = E_{s_{λ}} [(\nabla_{λ} lo g s_{λ} (ε)) W_{λ} (ε, x) + \nabla_{λ} W_{λ} (ε, x)] = E_{s_{λ}} [(\nabla_{λ} lo g s_{λ} (ε)) W_{λ} (ε, x) + \nabla_{λ} lo g p (t_{λ} (ε), x) - \nabla_{λ} lo g q_{λ} (t_{λ} (ε))] .

This is the required combined score and pathwise gradient estimator. A sample from

s_{λ}

and the integrand on the last line give an unbiased stochastic gradient under the stated regularity conditions. Its first term is a score-function gradient estimator contribution; the remaining terms differentiate the sampled objective along the continuous transformation. The same separation appears in the general stochastic computation graph construction.^[ref]

All derivatives inside the expectation hold

ε

fixed. They still include both explicit parameter dependence and dependence through

t_{λ}

. For a continuous coordinate

z = t_{λ} (ε)

\nabla_{λ} lo g q_{λ} (t_{λ} (ε)) = (\partial_{λ} lo g q_{λ}) (z) + (D_{λ} t_{λ})^{T} \nabla_{z} lo g q_{λ} (z) .

The model joint density

p (z, x)

is fixed as

λ

changes, but its composition with

t_{λ}

need not be constant. Discrete coordinates are not differentiated as real-valued paths; their changing probabilities enter through the score function. Moving supports or parameter-dependent branch boundaries require additional care and are not justified merely by formally interchanging a derivative and an integral.

d

Solution

The two limiting-case names in the printed bullets are reversed. Fully reparameterized continuous choices give a reparameterization gradient; non-reparameterized discrete choices give a score-function gradient estimator. Here are both reductions, including the extra term that vanishes only after taking an expectation.

When all choices are reparameterized with parameter-independent base noise,

s_{λ} = s

and

\nabla_{λ} lo g s = 0

. The expression in part (c) becomes

\nabla_{λ} L = E_{s} [\nabla_{λ} {lo g p (t_{λ} (ε), x) - lo g q_{λ} (t_{λ} (ε))}] .

Differentiating along the sampled transformation is precisely the pathwise gradient, also called the reparameterization gradient. There is no score function of the parameter-independent base law.

When all choices are discrete and left untransformed,

t_{λ} (ε) = ε = z

and

s_{λ} = q_{λ}

. Set

S_{λ} (z) = \nabla_{λ} lo g q_{λ} (z)

and

W_{λ} (z, x) = lo g p (z, x) - lo g q_{λ} (z)

. Since

p

has no variational parameter, the integrand in part (c) is

S_{λ} (z) W_{λ} (z, x) - S_{λ} (z) = S_{λ} (z) (W_{λ} (z, x) - 1) .

Normalization gives the zero-mean score function identity

E_{q_{λ}} S_{λ} = \sum_{z} \nabla_{λ} q_{λ} (z) = \nabla_{λ} 1 = 0.

Thus

\nabla_{λ} L = E_{q_{λ}} [S_{λ} W_{λ}] = E_{q_{λ}} [S_{λ} (W_{λ} - 1)] .

The first expression is the usual score-function gradient estimator; the second has a constant score baseline of one. The two random integrands are generally different even though their expectations agree. A suitable constant score baseline can reduce variance, but one is not universally the optimal baseline.^[ref]

For a concrete check, take

q_{λ} (D, Z) = Bernoulli (q) N (m, σ^{2})

with

q = (1 + e^{- a})^{- 1}

and

σ = e^{ℓ}

, and a fixed target

p (D, Z) = Bernoulli (0.4) N (D, 1)

. Direct integration gives

L = - D_{KL} (Bern (q) ∥ Bern (0.4)) - \frac{1}{2} {σ^{2} + m^{2} - 2 m q + q - 1 - 2 ℓ} .

(5)

Using

Z = m + σ ε

ε \sim N (0, 1)

, the combined integrand has components

(D - q) (W - 1)

D - Z

and

1 - (Z - D) σ ε

. Their expectations are respectively

q (1 - q) [lo g (0.4/0.6) - lo g (q / (1 - q)) + m - 1/2]

q - m

and

1 - σ^{2}

, matching direct differentiation. Dropping the discrete score function term would incorrectly give zero for the first component. This calculation checks the combination without accepting the printed reversal.

3

a

Solution

Treat each observed arrival label as a constraint on an unobserved walking duration. Departures are treated as fixed design information. Writing

c

for the minutes available until work starts, the derived late-label thresholds have frequencies

20 : 1, 21 : 3, 25 : 3, 27 : 1, 32 : 2

; the early-label thresholds have frequencies

29 : 1, 34 : 1, 36 : 3, 37 : 1, 38 : 1, 39 : 1, 43 : 1, 44 : 1

. These are censoring thresholds, not measured journey times. A late label means

T > c

, and an early label means

T < c

; equality has probability zero under the continuous model.

The paper specifies no prior distribution. One explicit proper model is

μ \sim Unif (0, 60), σ \sim Unif (1, 20), T_{i} ∣ μ, σ \sim iid N (μ, σ^{2}),

with independent priors; all times are in minutes. These ranges are a transparent modelling choice, not information deduced from the observations. In particular, this is a prior on the standard deviation

σ

, not a uniform prior on the variance

σ^{2}

. The normal distribution permits negative durations; it is the mathematical approximation requested here, rather than a claim that such durations are physically possible. A truncated model would be a different model.

The following Python implements hard conditioning by rejection sampling. None marks a rejected trace; an accepted Boolean answers whether all five future arrivals are late. The same parameters are shared across past and future days.

import math
import random

LATE = {20: 1, 21: 3, 25: 3, 27: 1, 32: 2}
EARLY = {29: 1, 34: 1, 36: 3, 37: 1, 38: 1, 39: 1, 43: 1, 44: 1}
RECORDS = [(c, True) for c, n in LATE.items() for _ in range(n)]
RECORDS += [(c, False) for c, n in EARLY.items() for _ in range(n)]

def journey_trace(rng):
    mu = rng.uniform(0.0, 60.0)
    sigma = rng.uniform(1.0, 20.0)
    # Twenty latent past durations and five future durations.
    past = [rng.gauss(mu, sigma) for _ in RECORDS]
    future = [rng.gauss(mu, sigma) for _ in range(5)]
    if not all(t > c if late else t < c
               for t, (c, late) in zip(past, RECORDS)):
        return None
    return all(t > 30.0 for t in future)

def accepted_average(trace, n, rng):
    if n <= 0:
        raise ValueError("n must be positive")
    successes = accepted = 0
    while accepted < n:
        result = trace(rng)
        if result is not None:
            accepted += 1
            successes += int(result)
    return successes / n

For example, accepted_average(journey_trace, n, random.Random(2021)) estimates the desired conditional probability from

n

accepted traces. Accepting False is essential: treating a false answer as a rejected trace would condition on the desired conclusion. The model deliberately emphasizes clear semantics; rejection can be inefficient because all twenty past-label constraints must hold together.

b

Solution

An idealized underlying probability space is

Ω = (0, 60) \times (1, 20) \times R^{25}, P = Unif (0, 60) \otimes Unif (1, 20) \otimes N (0, 1)^{\otimes 25},

with the product Borel sigma-algebra. Its 27 independent random coordinates are

μ

σ

, twenty past standard-normal noises, and five future standard-normal noises. Define

T_{i} (ω) = μ + σ ε_{i}

. Sampling an unknown variance does not mean drawing a new variance on each day; a single draw of

σ^{2}

applies to all durations in a trace.

Let

A

be the event that the first twenty durations satisfy their corresponding observed inequalities. The observations are the twenty late/early labels, conditional on the fixed departure thresholds. They are not exact values of the latent

T_{i}

. The posterior probability measure on traces is

P_{A} (B) = P (B ∣ A) = \frac{P ( B \cap A )}{P ( A )} .

Here

P (A) > 0

: at every interior parameter pair each strict normal-tail probability lies in

(0, 1)

, so their finite product has positive prior integral.

The returned outcome is

Y (ω) = 1 {T_{21} > 30, \dots, T_{25} > 30} \in {0, 1} .

Thus the underlying sample space has dimension 27, the successful output space is ${0, 1}$ , and the observations define the conditioning event $A$ . The desired output probability distribution is the pushforward measure of

P_{A}

under

Y

. Rejection is an implementation device, not a third scientific answer: None is discarded before forming the conditional output law.

c

Solution

Write

Φ

for the standard normal distribution function. Integrating out the twenty independent past durations gives the threshold-censored normal likelihood

L (μ, σ) = \prod_{c \in C_{L}} Φ (\frac{μ - c}{σ})^{n_{L} (c)} \prod_{c \in C_{E}} Φ (\frac{c - μ}{σ})^{n_{E} (c)} .

The frequencies

n_{L}, n_{E}

are those in part (a). For a future day, the conditional late-arrival probability is

π (μ, σ) = Φ ((μ - 30) / σ)

. Conditional independence of the five future durations gives

h (μ, σ) = π (μ, σ)^{5}

Exactly three primitive random coordinates suffice. Draw

μ, σ

from the same priors and one independent

U \sim Unif (0, 1)

. Reject if

U \geq L (μ, σ)

; otherwise return whether

U < L (μ, σ) h (μ, σ)

. Conditional on acceptance and the parameters,

U

is uniform on an interval of length

L

; the true-answer subinterval has length

L h

. Reusing this same uniform value is therefore intentional, not an independence mistake.

Indeed the two output contributions at each parameter value are

P (A, Y = 1 ∣ μ, σ) = L h, P (A, Y = 0 ∣ μ, σ) = L (1 - h) .

These are exactly the contributions obtained by integrating the original twenty-five duration noises. Multiplication by the common prior density and normalization therefore give the same joint posterior distribution of

(μ, σ, Y)

. The revised program preserves the query and parameter posterior, but does not retain individual latent durations. This is uniform-interval encoding of conditioning and a binary query.

Here is an executable version, reusing the definitions from part (a). Logarithms avoid multiplying many small probabilities.

def normal_logcdf(z):
    value = 0.5 * math.erfc(-z / math.sqrt(2.0))
    return math.log(value) if value > 0.0 else -math.inf

def journey_loglik(mu, sigma):
    return (sum(n * normal_logcdf((mu - c) / sigma)
                for c, n in LATE.items())
            + sum(n * normal_logcdf((c - mu) / sigma)
                  for c, n in EARLY.items()))

def collapsed_trace(rng):
    mu = rng.uniform(0.0, 60.0)
    sigma = rng.uniform(1.0, 20.0)
    log_likelihood = journey_loglik(mu, sigma)
    # This uniform lies in (0, 1], avoiding log(0).
    log_u = math.log(1.0 - rng.random())
    if log_u >= log_likelihood:
        return None
    log_h = 5.0 * normal_logcdf((mu - 30.0) / sigma)
    return log_u < log_likelihood + log_h

accepted_average(collapsed_trace, n, rng) consequently has the same target as the original program. The ideal three-dimensional sample space is

(0, 60) \times (1, 20) \times (0, 1)

with product uniform probability measure, conditioned on the displayed acceptance event. Finite-precision normal tails can underflow to zero in this simple implementation; the mathematical equivalence concerns exact probabilities, and the numerical check in part (d) independently integrates the likelihood in the region carrying appreciable posterior mass.

d

Solution

For any chosen proper prior density

ρ (μ, σ)

R \times (0, \infty)

with positive evidence, Bayes' theorem gives

P (Y = 1 ∣ A) = \frac{\int _{0}^{\infty} \int _{- \infty}^{\infty} ρ ( μ , σ ) L ( μ , σ ) Φ ( \frac{μ - 30}{σ} ) ^{5} d μ d σ}{\int _{0}^{\infty} \int _{- \infty}^{\infty} ρ ( μ , σ ) L ( μ , σ ) d μ d σ} .

The prior density comes from the first two random draws. The likelihood

L

is the probability of satisfying all observed-label constraints after integrating the past duration noises. The factor

Φ ((μ - 30) / σ)^{5}

is the probability of the five-day outcome conditional on the shared parameters. The denominator is the probability of acceptance, which converts the numerator's joint probability into the required conditional probability.

For the independent uniform priors in part (a), the constant

ρ = 1/ (60 \cdot 19)

cancels and both integrals reduce to

0 < μ < 60

1 < σ < 20

. A prior on the variance

v = σ^{2}

would require transforming the density: this chosen prior has density

1/ (38 v)

for

1 < v < 400

conditional on

μ

. One must not silently replace it by a uniform prior on

v

There is no unique numerical probability until the prior distribution is chosen. As a check for the stated uniform priors, independent Gaussian quadrature calculations with 256 and 512 nodes per coordinate agree at the shown precision:

P (Y = 1 ∣ A) \approx 0.15038909, E [π ∣ A] \approx 0.61265126.

The prior-predictive probability of all observed labels is approximately

0.00030422536

, explaining the rejection cost. These numbers are illustrations of the explicit model, not additional observed data.

A subtle point is that the five future days are independent only conditional on

(μ, σ)

. Integrating shared parameter uncertainty gives

E [π^{5} ∣ A]

, not

(E [π ∣ A])^{5}

. The latter is about

0.08631110

for these priors and understates the five-day probability. Jensen's inequality gives

(E [π ∣ A])^{5} \leq E [π^{5} ∣ A]

, while

0 \leq π \leq 1

gives

E [π^{5} ∣ A] \leq E [π ∣ A]

. For two future late-arrival indicator functions, their posterior covariance is

Var (π ∣ A) \geq 0

. This is the posterior predictive repeated-success identity.

Figure 1.
Posterior uncertainty and the five-day predictive probability for the explicitly chosen uniform priors. The contour is cropped to the parameter region carrying the visible mass; integration uses the full prior rectangle.
**Details**.

e

Solution

I would first collapse the duration noises as in part (c), then use self-normalized importance sampling on the two shared parameters. Draw independent

(μ_{j}, σ_{j}) \sim ρ

, give each the importance weight

w_{j} = L (μ_{j}, σ_{j})

, and return

P_{N} = \frac{\sum _{j = 1}^{N} w _{j} π ( μ _{j} , σ _{j} ) ^{5}}{\sum _{j = 1}^{N} w _{j}} .

This is likelihood weighting: the observations affect the weights rather than forcing repeated simulation of twenty latent inequalities. Integrating out both the constraints' auxiliary randomness and the future Boolean query is Rao-Blackwellization; at fixed parameters it removes randomness without changing the relevant conditional expectations.

The weights and weighted queries lie in

[0, 1]

, and the evidence is positive. The strong law of large numbers therefore makes the numerator and denominator averages converge to their corresponding integrals, proving almost sure convergence of their ratio to part (d). The finite-

N

ratio is generally biased; the assertion concerns consistency rather than a finite-sample unbiased estimator. Use logarithms of importance weights to avoid numerical underflow:

def weighted_answer(n, rng):
    if n <= 0:
        raise ValueError("n must be positive")
    samples = []
    for _ in range(n):
        mu = rng.uniform(0.0, 60.0)
        sigma = rng.uniform(1.0, 20.0)
        samples.append((journey_loglik(mu, sigma),
                        math.exp(5.0 * normal_logcdf((mu - 30.0) / sigma))))
    offset = max(logw for logw, h in samples)
    if not math.isfinite(offset):
        raise ArithmeticError("all weights underflowed")
    scaled = [(math.exp(logw - offset), h) for logw, h in samples]
    den = math.fsum(w for w, h in scaled)
    answer = math.fsum(w * h for w, h in scaled) / den
    ess = den * den / math.fsum(w * w for w, h in scaled)
    return answer, ess

The returned effective sample size of importance sampling is a concentration diagnostic, not a proof of accuracy. Repeat runs and inspect the weights. If the prior is much broader than the posterior, improve the proposal with the corresponding importance sampling density correction, or use the Metropolis–Hastings algorithm targeting

ρ L

. Because this particular collapsed problem is only two-dimensional, deterministic numerical integration is also an excellent independent accuracy check; it was used for the figure and numerical illustration. Straight rejection of the original traces is correct but wastes most proposals here.

Computational game theory (A15684W1, A16016W1)

Source paper: released examination archive.

1

a

Solution

$ℓ_{2} ≻ ℓ_{1}$ . The distinction is small but strict: their normalized expected utilities are

18/25

and

7/10

, respectively.

By the Von Neumann-Morgenstern utility theorem, use a representing utility function and apply a positive affine function to set

u (ω_{1}) = 1

and

u (ω_{4}) = 0

. This is possible because the given strict preference implies

u (ω_{1}) > u (ω_{4})

. The two specified indifference relations then give

u (ω_{3}) = \frac{3}{5}, u (ω_{2}) = \frac{3}{4} + \frac{1}{4} \frac{3}{5} = \frac{9}{10} .

Taking the expected utility of each lottery yields

U (ℓ_{1}) = \frac{2}{5} + \frac{1}{5} \frac{9}{10} + \frac{1}{5} \frac{3}{5} = \frac{7}{10}, U (ℓ_{2}) = \frac{2}{5} \frac{9}{10} + \frac{3}{5} \frac{3}{5} = \frac{18}{25} .

Their difference is

1/50 > 0

, establishing the stated strict preference. These numbers measure utility, not monetary reward or an assumed ordering of the subscripts.

Here is the underlying argument directly in terms of the axioms. The independence axiom for lottery preferences permits substitution of indifferent lotteries inside a common mixture. Replacing

ω_{3}

by its given mixture of

ω_{1}, ω_{4}

, and then replacing

ω_{2}

, followed by reduction of compound lotteries, gives

ω_{2} \sim \frac{9}{10} ω_{1} + \frac{1}{10} ω_{4},

and consequently

ℓ_{1} \sim \frac{7}{10} ω_{1} + \frac{3}{10} ω_{4}, ℓ_{2} \sim \frac{18}{25} ω_{1} + \frac{7}{25} ω_{4} .

The transitive relation axiom combines the successive substitutions. Finally, mixture monotonicity says that among mixtures of a strictly better and a strictly worse outcome, the greater probability of the better outcome is strictly preferred; this follows from the independence axiom for lottery preferences and transitivity. Since

18/25 > 7/10

and

ω_{1} ≻ ω_{4}

, the comparison follows. Complete lottery preferences and continuity of lottery preferences are part of the representation theorem's hypotheses; the direct substitution calculation uses the already supplied indifferences and does not need to invoke continuity of lottery preferences again.^[ref]

b

Solution

No: these two strict comparisons violate the independence axiom for lottery preferences. Let

z

denote the certain zero-money lottery. Reduction of compound lotteries gives

ℓ_{1} = \frac{1}{4} ℓ_{3} + \frac{3}{4} z, ℓ_{2} = \frac{1}{4} ℓ_{4} + \frac{3}{4} z .

For example, the second expression assigns probability

(1/4) (4/5) = 1/5

to the nonzero reward and

4/5

to zero. The claimed

ℓ_{3} ≻ ℓ_{4}

must therefore imply

\frac{1}{4} ℓ_{3} + \frac{3}{4} z ≻ \frac{1}{4} ℓ_{4} + \frac{3}{4} z,

which is

ℓ_{1} ≻ ℓ_{2}

, contradicting the other claimed strict preference.

The same obstruction is visible in any proposed expected utility representation. Subtract

u (0)

from the utility function, and write

a = u (3000) - u (0)

and

b = u (4000) - u (0)

. The first comparison requires

(1/5) b > (1/4) a

, hence

(4/5) b > a

, whereas the second requires

a > (4/5) b

. No real

a, b

satisfy both. This argument requires neither risk neutrality nor an assumption that the utility function is increasing in money.

2

a

Solution

Put

p = Pr (T)

and

q = Pr (L)

, so the complementary probabilities are

1 - p

and

1 - q

. All four expressions are the row player's expected payoff, including those indexed by a column action. Direct expected value calculations give

π_{1} (p, L) π_{1} (p, R) π_{1} (T, q) π_{1} (B, q) = 2 p - (1 - p) = 3 p - 1, = - 3 p + (1 - p) = 1 - 4 p, = 2 q - 3 (1 - q) = 5 q - 3, = - q + (1 - q) = 1 - 2 q .

The column player's expected payoff is the negative of the row player's because this is a zero-sum game.

b

Solution

The bold black curve is the pointwise minimum of the two opposing-column expected payoff functions. It is the row player's security level payoff at the specified mixed strategy:

g (p) = min (3 p - 1, 1 - 4 p) = {3 p - 1, 1 - 4 p, 0 \leq p \leq 2/7, 2/7 \leq p \leq 1.

The lines meet where

3 p - 1 = 1 - 4 p

, hence at

p = 2/7

. The first branch increases with slope

3

and the second decreases with slope

- 4

, so their intersection is the unique global maximum of the lower envelope:

0 \leq p \leq 1 arg max g (p) = \frac{2}{7}, max g = - \frac{1}{7} .

The endpoint values are

g (0) = - 1

and

g (1) = - 3

, both smaller. Since an opposing mixed strategy forms a convex combination of the two pure-column expected payoffs, it cannot make the row player's expected payoff lower than this envelope.

Figure 1.
The row player's lower payoff envelope and its maximum at p = 2/7
. **Details**.

c

Solution

The bold black curve is now the pointwise maximum of the two pure-row expected payoff functions:

h (q) = max (5 q - 3, 1 - 2 q) = {1 - 2 q, 5 q - 3, 0 \leq q \leq 4/7, 4/7 \leq q \leq 1.

It measures the largest expected payoff that the row player can achieve against column mixed strategy

q

. The column player minimizes this quantity because its own payoff has the opposite sign. Equality of the two lines gives

5 q - 3 = 1 - 2 q

, or

q = 4/7

. The envelope decreases before that point and increases afterwards, giving

0 \leq q \leq 1 arg min h (q) = \frac{4}{7}, min h = - \frac{1}{7} .

The endpoint values

h (0) = 1

and

h (1) = 2

are both larger. A row mixed strategy cannot exceed the greatest pure-row expected payoff, because its expected payoff is a convex combination of those two values.

Figure 1.
The column player's upper payoff envelope and its minimum at q = 4/7
. **Details**.

d

Solution

The unique Nash equilibrium uses row probabilities $(2/7, 5/7)$ on $(T, B)$ and column probabilities $(4/7, 3/7)$ on $(L, R)$ . The value of a zero-sum game to the row player is $- 1/7$ ; the column player receives $1/7$ .

The first graph solves the row player's max–min optimization: choose a mixed strategy guaranteeing the greatest possible worst-case expected payoff. The second solves the column player's min–max optimization: choose a mixed strategy placing the smallest upper bound on the row player's expected payoff. Their optimal heights agree, illustrating the minimax theorem.

There is also a direct Nash equilibrium certificate, so the conclusion does not depend on reading coordinates from a plot. At

p^{*} = 2/7

, both opposing pure columns give row expected payoff

- 1/7

; at

q^{*} = 4/7

, both pure rows give row expected payoff

- 1/7

. By linearity, every unilateral deviation, including an arbitrary mixed strategy, leaves the deviator's expected payoff unchanged against the fixed opposing equilibrium mixture. Neither player can improve it. This is a mixed-strategy optimality certificate for a matrix game.

The equilibrium outcome is a probability distribution over cells, rather than one deterministic cell. Independent randomization gives

Pr (T L) = \frac{8}{49}, Pr (TR) = \frac{6}{49}, Pr (B L) = \frac{20}{49}, Pr (BR) = \frac{15}{49} .

The resulting row expected payoff is

(16 - 18 - 20 + 15) /49 = - 1/7

. Finally, each envelope has a unique optimum, so any Nash equilibrium must use the displayed optimal mixed strategies. In particular there is no pure strategy Nash equilibrium.

3

a

Solution

Exactly $(T, L)$ , $(M, C)$ and $(B, R)$ can be sustained as constant stage game outcomes. Their long-run average payoffs are $(6, 6)$ , $(4, 4)$ and $(0, 0)$ , respectively. We assume the usual repeated game monitoring convention: both players observe each completed joint action before the next round. The source's colour convention puts the blue lower-left row payoff first and the red upper-right column payoff second.

For necessity, row action

B

earns

(8, 5, 0)

against

(L, C, R)

, so playing it forever guarantees a nonnegative long-run average payoff against every opposing pure strategy. Similarly, column action

R

earns

(8, 5, 0)

against

(T, M, B)

and guarantees zero or more. Conversely, column action

R

holds the row player's best possible stage payoff to

0

, and row action

B

holds the column player's to

0

. Thus each player's minmax payoff is exactly

0

Any Nash equilibrium must give both players at least zero, an individually rational payoff in a repeated game. Every off-diagonal cell has a negative payoff for one player:

(T, C)

and

(T, R)

hurt row,

(M, L)

and

(B, L)

hurt column,

(M, R)

hurts row and

(B, C)

hurts column. Repeating any such cell forever therefore permits a profitable unilateral deviation to the zero-guaranteeing action. The three diagonal cells pass this necessary test.

For sufficiency, fix target

a^{*} = (T, L)

(M, C)

. Each player's finite-state strategy has initial state

F

and an absorbing state

P

. In

F

, output the player's component of

a^{*}

; remain in

F

if the completed joint action equals

a^{*}

, and otherwise move to

P

. In

P

, row always outputs

B

and column always outputs

R

, regardless of further observations. These are two-state grim trigger strategies; the separate machines are drawn below. The input is the observed joint action, so after any off-path history the prescribed continuation states agree.

Figure 1.
Separate finite-state punishment strategies sustaining the two positive-payoff diagonal outcomes
. **Details**.

If neither player deviates, the target is repeated forever. If a player first deviates at a finite round

τ

, the opponent enters

P

for all later rounds. Against column action

R

, every row action earns at most zero; against row action

B

, every column action earns at most zero. All payoffs are bounded, so the total reward before and at

τ

, divided by the horizon, tends to zero. The deviator's upper limiting average is therefore at most

0

, below either target payoff

6

4

. This proof tests arbitrary future deviations, not merely a single changed action. It also rules out improvement by deviations whose averages fail to converge, if the criterion is extended by an upper or lower limit.

For target

(B, R)

, one-state machines outputting

B

and

R

forever suffice: each is a best response to the other in every round. Their long-run average payoffs are zero and no unilateral deviation can improve them. In fact, the punishment is credible because

(B, R)

is a stage Nash equilibrium, so the two positive-target constructions are also subgame perfect equilibria under the stated monitoring assumption. The general punishment mechanism is described in ^[ref].

“Outcomes of the stage game” here means a fixed action pair repeated forever. Allowing time sharing also sustains some average payoff vectors that are not stage cells: for example, a deterministic alternating cycle

(T, L), (M, C)

gives

(5, 5)

, with a two-phase finite-state strategy and the same permanent punishment. An off-diagonal cell may occur in a sustainable cycle; the impossibility above concerns its constant repetition, not every appearance on an equilibrium path. With finite-state pure strategies, an undisturbed path is eventually periodic, so its limiting cell frequencies are rational numbers.

b

Solution

Use the standard repeated game convention that the first round's joint action is observed before round two. The following original game tree represents simultaneous moves by making row move first in each round while hiding that current move from column. Terminal labels are total payoffs over both rounds, ordered row then column.

Figure 1.
The full two-round extensive-form game, with all sixteen terminal payoff pairs and five column information sets
. **Details**.

Formally, round one starts at a row decision with actions

T, B

. The two ensuing column nodes form one information set

I_{2}^{0}

, with available actions

L, R

; column cannot tell which current row action occurred. The four completed first-round histories are

H = {T L, TR, B L, BR}

. At each

h \in H

, round two begins at a separate row node. Its two successors, after row's current

T

B

, form a column information set

I_{2}^{h}

. Distinct

h

have distinct information sets: both players know the whole first-round outcome. There are sixteen terminal histories

(h, k) \in H^{2}

, whose total payoff is

u (h) + u (k)

, as displayed in the tree.

The row player's five information sets are the initial singleton and the four singleton round-two nodes, one per

h

. The column player's five information sets are

I_{2}^{0}

and the four two-node sets

I_{2}^{h}

. Thus each player must specify one binary choice at each of five information sets, including histories that its own first choice might prevent:

∣ S_{1} ∣ = ∣ S_{2} ∣ = 2^{5} = 32.

Counting only the four possible two-round action sequences would miss the distinct contingent responses to the opponent's first action.

For a concrete pair of complete pure strategies, order the second-round histories as

(T L, TR, B L, BR)

and use

s_{1} = (T; B, T, T, T), s_{2} = (L; R, L, L, L) .

The first entry is the initial action, and the four remaining entries prescribe the action after each first-round history. This induces the unique path

T L

in round one followed by

BR

in round two. Hence the total payoff is

(1, 5) + (2, 1) = (3, 6) .

The off-path entries are part of each pure strategy, even though this pair does not reach them.

For randomization, a mixed strategy is a probability distribution over the

32

complete plans, with

31

free probabilities in a general distribution. A behavioural strategy instead gives one binary-action probability at each of five information sets, requiring five parameters. This game has perfect recall: a player never forgets a previous own action or a first-round observation, and the only concealed action is the opponent's current simultaneous choice. Consequently neither kind of randomization has a greater attainable-payoff advantage: Kuhn's theorem gives realization-equivalent strategies against every fixed opposing strategy.^[ref]

The equivalence can be verified directly here. Given a behavioural strategy, sample all five contingent actions independently before play; the resulting product probability distribution over complete plans is an equivalent mixed strategy. Conversely, let

μ

be a mixed strategy for player

i

. Use its marginal probability for the initial action. At history

h

containing own first action

a_{i}

, choose second action

b_{i}

with conditional probability

β_{i} (b_{i} ∣ h) = \frac{μ { s : s ^{0} = a _{i} , s ^{h} = b _{i} }}{μ { s : s ^{0} = a _{i} }},

whenever the denominator is positive; if it is zero, choose arbitrarily at that unreachable history. The opponent's first-round action is simultaneous and cannot depend on the sampled hidden plan beyond the chosen first action. Thus conditioning on

h

preserves exactly these conditional probabilities of actions, and multiplying the first- and second-round factors reproduces each terminal probability. Correlations between prescriptions at mutually exclusive second-round histories have no further observable effect. Behavioural strategies offer the more compact representation, while mixed strategies describe a single random choice of a full plan. Imperfect information here does not mean imperfect recall.

4

a

Solution

If the core is nonempty, it is exactly the singleton allocation $p_{j} = v ({j})$ for every $j$ . Take any

p

in the core of a cooperative game and write

p (C) = \sum_{j \in C} p_{j}

. Core membership gives efficiency of the imputation,

p (N) = v (N)

, and the coalition inequalities

p (C) \geq v (C), p (N ∖ C) \geq v (N ∖ C) .

Using the given complementary-coalition equality in this constant-sum cooperative game, the second inequality yields

p (C) = v (N) - p (N ∖ C) \leq v (N) - v (N ∖ C) = v (C) .

Combining upper and lower bounds gives

p (C) = v (C)

for every coalition

C

. In particular,

p_{j} = p ({j}) = v ({j}) for every j \in N .

Since this holds for any core member and at least one exists by hypothesis, the displayed allocation is in the core and is its only member. The argument also shows why nonemptiness is restrictive: it forces

v (C) = \sum_{j \in C} v ({j})

for every coalition, so the characteristic function of a coalitional game must be additive. No superadditive coalitional game or monotonicity assumption is needed.

b

Solution

$G_{1}$ cannot have an induced subgraph game representation. $G_{2}$ is represented by a weighted triangle with edge weights $w_{12} = 2$ , $w_{13} = 3$ , $w_{23} = 3$ , and has Shapley value vector $(5/2, 5/2, 3)$ .

In an induced subgraph game, players are graph vertices and a coalition receives the sum of the weights of graph edges whose two endpoints lie in it. Therefore each two-player coalition determines the corresponding edge weight. For

G_{1}

these weights would have to be

2, 6, 3

, making the grand coalition worth

2 + 6 + 3 = 11

, whereas its actual value is

15

. No other edge weights can repair that discrepancy without changing a two-player coalition's value. Even a convention allowing vertex weights would not help: its singleton values force all such weights to zero.

For

G_{2}

, the stated weighted graph triangle has grand coalition value

2 + 3 + 3 = 8

and reproduces all three pair values. Empty and singleton coalitions contain no graph edges, so their values are zero. This verifies all eight coalitions and supplies the complete representation.

To compute the Shapley value, reveal players in a uniformly random permutation. An edge's weight contributes to an endpoint's marginal contribution precisely when the other endpoint appeared earlier. Each endpoint is later with probability

1/2

, independently of where the third player appears. Linearity of the expected value therefore splits each edge weight equally between its two endpoints:

ϕ_{1} = \frac{2 + 3}{2} = \frac{5}{2}, ϕ_{2} = \frac{2 + 3}{2} = \frac{5}{2}, ϕ_{3} = \frac{3 + 3}{2} = 3.

The values sum to

8 = v_{2} (N)

, as required by the Shapley value's efficiency property. This is the general Shapley value of an induced subgraph game formula, not an assumption that all three players are symmetric: player

3

has a different incident-weight total.

v (C) = ⌊ ∣ C ∣/2 ⌋

, the two-person instance of the core of the miners game calculation.

Let

x

be in the core. Efficiency requires

x_{1} + x_{2} + x_{3} + x_{4} = 2

, and every pair coalition requires

x_{i} + x_{j} \geq 1

. Summing the six pair inequalities counts each coordinate three times, giving

3 \sum_{i} x_{i} \geq 6

. Efficiency makes this an equality; since every individual slack is nonnegative, all six pair inequalities must be equalities. In particular

x_{1} + x_{2} = x_{1} + x_{3} = x_{1} + x_{4} = 1

forces

x_{2} = x_{3} = x_{4}

, and comparison with

x_{2} + x_{3} = 1

gives every

x_{i} = 1/2

Conversely, for the uniform allocation every coalition satisfies

\sum_{i \in C} x_{i} = \frac{∣ C ∣}{2} \geq ⌊ \frac{∣ C ∣}{2} ⌋ = v (C),

and its total is

2 = v (N)

. It is therefore a core member, completing both existence and uniqueness. In particular, a three-player coalition receives

3/2 \geq 1

; the pair constraints are the tight ones.

ii

Solution

The core is empty. Efficiency would require

x_{1} + x_{2} + x_{3} = v (N) = 1

. Each two-player coalition has value

1

, so core membership would also require

x_{1} + x_{2} \geq 1, x_{1} + x_{3} \geq 1, x_{2} + x_{3} \geq 1.