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

Let $N=m+n$. In a uniformly shuffled deck, each labelled card is equally likely to occupy the first position, and exactly $m$ cards are red. Therefore $\mathbb{P}(\text{first red})=m/(m+n)$. Equivalently, the red positions are a uniformly chosen $m$-element subset of the $N$ positions.

Every position in the random permutation has the same marginal colour probability, so $\mathbb{P}(\text{second red})=m/(m+n)$. One can verify this with the law of total probability, conditioning on the first card:Here $N\ge 2$ because both colour counts are positive.

Let $R_1,R_2$ be the two red-card events. Sampling without replacement givesThis differs from the product $m^2/N^2$, sinceThus the events are not independent, for every positive $m,n$. A first red card reduces the remaining red fraction, a basic instance of how sampling without replacement need not be independent.

The $m$ red positions form a uniformly chosen subset of size $m$, so there are $\left(\genfrac{}{}{0ex}{}{m+n}{m}\right)$ equally likely colour patterns. A contiguous red block can start at positions $1,2,\dots ,n+1$, giving exactly $n+1$ favourable patterns. ThereforeIf the cards are regarded as individually labelled, each colour pattern corresponds to $m!n!$ permutations, so the same counting argument still applies. In the edge case $m=1$, the formula correctly gives probability one.

Conditional on a contiguous red block, its $n+1$ possible starting positions remain equally likely because their original colour patterns had equal probabilities. The first card is red exactly when that block starts at position $1$. HenceThis also follows by dividing the probability of the single favourable block position, $1/\left(\genfrac{}{}{0ex}{}{m+n}{m}\right)$, by the probability of all $n+1$ block positions.