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

For each of the $b$ balls, let $I_i$ be the indicator random variable that ball $i$ survives the round of uniform balls-in-bins allocation. Condition on its chosen bin. Each of the other $b-1$ balls avoids that bin with probability $1-1/n$, independently, so the probability that ball $i$ is served is $(1-1/n{)}^{b-1}$. Hence, for $b\ge 2$,We used linearity of expectation to sum the indicator random variables; their mutual independence is unnecessary. For $b=0$ or $b=1$, the next count is zero. This states the boundary cases without an ambiguous $0^0$ when $n=1$.

There is no proof of the printed assertion: it is false for the stated expectations. The original explicitly defines $x_j$ as the expected remaining count, so replacing it by a deterministic upper envelope changes the problem.^[ref]

Let $B_j$ be the actual count after $j$ rounds and $x_j=\mathbb{E}{B}_j$. The union bound gives the valid conditional estimateBy the law of total expectation, the resulting unconditional bound isDiscarding the variance term is an expectation closure error for a nonlinear recurrence. In particular, Jensen's inequality says $\mathbb{E}{B}_j^2\ge x_j^2$, which cannot justify the requested upper bound.

For an exact counterexample, start with two balls and two bins. A round serves both balls if they land separately and serves neither if they collide. Each outcome has probability $1/2$, independently in successive rounds while both balls remain. ConsequentlyAt $j=2$, the requested inequality would say $x_3\le x_2^2/2$, but

The printed bound also fails for the actual expectations. In the two-bin counterexample from part (b), at $j=5$ the true value and proposed bound areThe supplied premise $x_2\le n/2$ does hold in this example: $x_2=1/2\le 1$. Thus the problem is the invalid recurrence in part (b), rather than failure of the supplied starting estimate.^[ref]

The intended mathematical induction is valid conditionally on the recurrence. For a deterministic nonnegative sequence $y_j$ satisfying $y_2\le n/2$ and $y_{j+1}\le y_j^2/n$, the base case is $y_2\le n{2}^{-1}$. If $y_j\le n{2}^{-2^{j-2}}$, thenThis proves the proposed form for $y_j$ but cannot identify $y_j$ with $\mathbb{E}{B}_j$.

If the bound in part (c) were available, the intended answer would beIndeed $2^{j_{\mathrm{intended}}(n)-2}\ge {\log }_{2}n$, so that bound would give $x_{j(n)}\le n{2}^{-{\log }_{2}n}=1$. Its growth is $O(\log \log n)$ in Big O notation. Because (c) is false, this substitution alone does not prove the result for the actual repeated singleton-removal allocation.

The requested order can nevertheless be established for the actual process. Here is a concrete, deliberately generous replacement, with $j(0)=0$ for the empty system:The large cutoff makes the numerical estimates below simple. A finite initial range does not affect the $O(\log \log n)$ asymptotic analysis.

First, whenever $2\le b\le n$, a ball is served with probability at leastThus part (a) gives $\mathbb{E}[B_{t+1}\mid B_t]\le 2B_t/3$, also for $B_t\le 1$. The law of total expectation yields $x_t\le n(2/3{)}^t$. This proves $x_{j(n)}\le 1/2$ for the small-$n$ branch, including $n=1$, whose single ball is served immediately.

For the large-$n$ branch, we need control of the random count, rather than an unjustified recurrence for its expectation. If $b$ balls are allocated in a round, changing one chosen bin changes the number of singleton bins by at most two. The surviving count $F_b$ therefore has the bounded differences property with constants $2$. McDiarmid's inequality givesThis can be applied conditionally after any history, since the next allocations are fresh independent random variables.

Use this concentration inequality in three stages. Write $L=\lceil {\log }_2{\log }_{2}n\rceil$.

Every exceptional probability above is at most $e^{-n^{1/6}/300}$, and there are at most $L+10$ opportunities for an exception. For $n\ge 2^{120}$, the elementary bounds $n^{1/6}/300\ge 4\ln n$ and $L+10\le n$ give, by the union bound, total exceptional probability at most $n^{-3}$. The first numerical inequality holds at the cutoff and remains true because $n^{1/6}/\ln n$ is increasing there. On an exceptional history there are at most $n$ balls. Taking the last round's conditional expectation and then averaging givesThis proves the displayed replacement $j(n)$ for the literal process without relying on either false assertion.

Consider any edge $\{u,v\}$ of the simple graph. One endpoint comes first in the permutation $\sigma$; suppose it is $u$. Then $v$ has a graph neighbour preceding it, namely $u$, so $v\notin S(\sigma )$. Therefore no edge has both endpoints in $S(\sigma )$:This argument uses only the order of the endpoints, with no random choice required.

Choose a uniform random permutation of the $n$ vertices, giving every one of the $n!$ orders the same probability. For a fixed vertex $i$, consider $i$ together with its $d_i$ graph neighbours. The relative order of these $d_i+1$ vertices is uniform, so each is equally likely to be first. The membership rule for $S(\sigma )$ therefore givesLet $I_i$ be the indicator random variable of this event. The cardinality is $|S(\sigma )|={\sum }_{i=1}^n{I}_i$, and linearity of expectation givesThe indicator random variables are generally dependent; only the uniform random permutation and linearity of expectation were needed. An isolated vertex has $d_i=0$ and is always included, as the formula correctly predicts.

The expectation from part (f) is the average of $|S(\sigma )|$ over the finite collection of permutations. At least one value is as large as its average. By part (e), the corresponding $S(\sigma )$ is an independent set, soHere $\alpha (G)$ is the independence number. Since its value is an integer, one can equivalently round the right side up with the ceiling function. This application of the probabilistic method is the Caro-Wei bound.