Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Discrete mathematics, probability and continuous mathematics / 7

The joint probability mass function is $p_{X,Y}(x,y)=\mathbb{P}(X=x,Y=y)$ for $(x,y)\in S^2$. It is nonnegative and its sum over $S^2$ equals one. Summing over one coordinate gives the other variable's marginal distribution.

For $\mathbb{P}(X=x)>0$, the conditional probability mass function isThe positive denominator makes the expression well-defined, and its sum over $y$ is one.

A partition of a sample space is a finite or countable family of pairwise disjoint events $B_i$ whose union is the whole sample space. For an integrable random variable, the partition form of the law of total expectation isZero-probability cells contribute zero and are omitted because elementary event-conditioning on them is undefined. The formula also holds with extended nonnegative values when $X\ge 0$. Integrability makes the signed series legitimate in the finite-expectation case.

The first exchange removes one red ball from urn 1 and replaces it with a blue ball. Hence $R_1=n-1$ with probability one.

At state $r$, urn 1 has $r$ red and $n-r$ blue balls, while urn 2 has $n-r$ red and $r$ blue balls. Conditional on the state, the two choices are independent, each assigning probability $1/n$ to every ball. A red–blue exchange decreases $r$; a blue–red exchange increases it; equal colours leave it unchanged. Thus the conditional probability mass function isThe three numerators sum to $n^2$. At $r=0$ or $n$, the outward transition has probability zero. These are the transitions of the Bernoulli-Laplace diffusion model. The displayed formula is a transition kernel on every state; a literal conditional probability at a particular time requires the conditioning event to have positive probability.

Compute the conditional expectation from the possible increments:Therefore $\alpha =1$ and $\beta =1-2/n$. This calculation uses the conditional independence of the two selections, not independence of the successive counts $R_k$.

Apply the law of total expectation to the bounded random variable $R_{k+1}$. Linearity of expectation givesThis also holds for the first step from $r_0=n$.

Put $\beta =1-2/n$. The fixed point of this affine recurrence is $n/2$. Subtracting it gives $r_{k+1}-n/2=\beta (r_k-n/2)$. Repeated substitution, or mathematical induction, therefore yieldsFor $n>2$ this expression applies to every $k\ge 0$. For $n=2$, state the initial value $r_0=2$ separately and obtain $r_k=1$ for every $k\ge 1$, avoiding any need to interpret $0^0$. The expected red imbalance decays towards zero, although the urn composition itself remains random.