Past exam of the computer science course of the University of Oxford / 2015 / Probability and computing / 3

A trial of Amy's rejection sampling uses exactly $2n$ fair Bernoulli trials. Exactly $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ of the $2^{2n}$ equally likely binary sequences have $n$ heads, so the acceptance probability isIndependent retries make the number $T$ of trials a geometric random variable on $\{1,2,\dots \}$ with expectation $1/p_n$. The total number $C$ of coin tosses is $2nT$, soUsing Stirling's approximation, the central binomial coefficient satisfiesConsequentlyThe rejection sampling output is uniform among the balanced binary sequences: they have equal probability on every trial, and conditioning on acceptance preserves that equality. For $n=0$, the empty output needs zero tosses; the formula above concerns $n\ge 1$.

Betty's scheme is biased for every $n\ge 2$. The output $H^n{T}^n$ occurs precisely when the first $n$ tosses are heads: the algorithm stops there and appends $n$ tails. ThusFor comparison, take the output $(HT{)}^n$. Its first $2n-2$ symbols contain $n-1$ heads and $n-1$ tails, so neither stopping threshold has been reached. The next symbol is the $n$th head, at which point the last tail is appended. Its unique generating prefix has length $2n-1$, givingThereforeThe faster stopping rule does not produce a uniform distribution on a finite set of balanced binary sequences. For example, at $n=2$ the six outputs have the following exact probabilities:

For $n=1$, the two possible outputs each have probability $1/2$, so that special case is uniform. For $n=0$, simply return the empty output.

Use uniform balanced binary sequence sampling by choosing the positions of the heads. Number the $2n=2^m$ positions from zero to $2n-1$. Start with no selected positions. Repeatedly toss the fair coin $m$ times, interpret the resulting bits as a position, and select that position if it has not already been selected; otherwise discard this block of tosses and retry. Stop when $n$ distinct positions have been selected. Put heads at those positions and tails everywhere else.

After $s$ positions have been selected, every one of the remaining positions has the same probability of being the next new position. This follows either by summing a geometric series over rejected blocks or by conditioning a uniform distribution on a finite set on avoiding the selected positions. Every ordered list of $n$ distinct selected positions consequently has probabilityEach fixed $n$-element subset has $n!$ such orders, so its probability isThus every balanced binary sequence is equally likely.

When $s$ positions are selected, a block succeeds with probability $(2n-s)/(2n)$, so the geometric distribution gives expectation $2n/(2n-s)$ blocks until the next new position. By linearity of expectation, the total expected toss count isThe strict inequality holds since $s<n$, making each term less than two. A Boolean array records membership of each position; initializing it and constructing the output require $O(n)$ additional work. The scheme terminates with probability one, since every stage has positive success probability.

Colour each edge of the complete graph $K_n$ independently red or blue, with probability $1/2$ for each colour. Every four-element subset $A$ of vertices determines exactly one copy of $K_4$, containing six edges. These six edges are all red with probability $2^{-6}$ and all blue with probability $2^{-6}$. The events are disjoint events, soLet $I_A$ be the indicator random variable for this event and let $Z={\sum }_A{I}_A$ count the monochromatic copies. Linearity of expectation givesThe indicator random variables for overlapping copies need not be independent. Averaging over all edge colorings ensures that at least one has $Z\le \mathbb{E}Z$. Thus the probabilistic method provesFor $0\le n<4$, both sides are zero and any edge coloring works. Copies are counted by their four-vertex subsets, rather than by their $4!$ possible labellings.

Set $N=\left(\genfrac{}{}{0ex}{}{n}{4}\right)$. Independently sample an edge coloring exactly as in part (d), count its monochromatic copies of $K_4$ by examining all four-vertex subsets, and accept precisely when $32Z\le N$. Otherwise start over with a fresh edge coloring.

To prove an expected polynomial time bound, the existence argument alone is insufficient: we need a lower bound on the acceptance probability at this exact threshold. Since $32Z$ is a nonnegative integer with expectation $N$, rejection implies $32Z\ge N+1$. Markov's inequality therefore gives the integer-valued expectation threshold restart boundThe number of attempts has a geometric distribution, with expectation at most $N+1$. Sampling the edge coloring costs $O(n^2)$ random bits, and checking all $N$ four-vertex subsets costs $O(n^4)$ operations, since only six edges must be tested per subset. HenceThis is a randomized algorithm that always returns an edge coloring meeting the original threshold and terminates with probability one. The stated operation count uses $O(\log n)$-bit counters; counting their bit complexity explicitly introduces at most a further logarithm factor and still gives polynomial time. For $n<4$, return any edge coloring immediately.

Order the edges arbitrarily and fix their colours one at a time. After a partial assignment $P$, regard all unassigned edges as independent fair red/blue choices, and computeThe conditional expectation of a monochromatic clique count is easy to compute. For each four-vertex subset $A$, let $r$ be the number of its six edges still unassigned. Its contribution $q_A(P)$ to $Q(P)$ isIn the second case, every remaining edge must match the already fixed colour; this includes a completely fixed monochromatic copy, for which $r=0$ and the contribution is one. In the last case, the six unassigned edges may become either all red or all blue. By linearity of expectation,For the next unassigned edge $e$, compute $Q(P,e=\text{red})$ and $Q(P,e=\text{blue})$. The law of total expectation givesChoose the colour with the smaller value, resolving a tie by a fixed rule. At least one is at most their average, so the loop invariant is that $Q$ never increases. Initially $Q=\left(\genfrac{}{}{0ex}{}{n}{4}\right)/32$; once every edge is fixed, there is no randomness left and $Q=Z$. Therefore the method of conditional expectations guaranteesA direct implementation recomputes both sums over all $O(n^4)$ four-vertex subsets for each of the $O(n^2)$ edges, requiring $O(n^6)$ arithmetic operations. The comparisons can be exact: every contribution is a multiple of $1/32$, so store $32Q$ as an integer with $O(\log n)$ bits. This gives $O(n^6\log n)$ bit complexity with elementary arithmetic, and hence a deterministic polynomial time construction. No random sampling is performed by this derandomization.