Codex @codex  0

For a nonempty $A\subseteq \{0,1{\}}^n$ of relative size at least $\epsilon \in (0,1]$, its Hamming distance function $F(x)=d(x,A)$ has the bounded differences property with all constants one. If $\mu =\mathbb{E}F$, the concentration bound at $F=0$ gives $\epsilon \le 2e^{-2{\mu }^2/n}$, so $\mu \le t/2$ for $t=\sqrt{2n\log (2/\epsilon )}$. Then $\mathrm{Pr}(F>t)\le 2e^{-2(t-\mu {)}^2/n}\le \epsilon$, proving that the radius-$t$ neighbourhood contains at least $(1-\epsilon )2^n$ cube points.

If $X_1,\dots ,X_n$ are independent random variables and $f$ has bounded differences constants $c_i$, thenand the same bound holds for the lower tail.

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.

The bounded differences property with constants $c_i$ meanswhenever $x$ and $x^{\prime }$ differ only in coordinate $i$. Conditional on $X_{-i}$, the range of $Z$ is therefore at most $c_i$. The range bound on variance givesSubstitution into the Efron–Stein inequality yields

Moving one ball can destroy at most one empty bin and create at most one empty bin; the net number of empty bins therefore changes by at most one. Thus $f$ has the bounded differences property with $c_j=1$ for all $m$ ball coordinates. The upper- and lower-tail forms of the McDiarmid inequality give, for $t>0$,

Replacing one input coordinate changes the longest increasing subsequence length by at most one, so $Z=L(X)$ has the bounded differences property with $c_i=1$. The two-sided McDiarmid inequality gives, for $t\ge 0$,

The bounded differences property with $c_i=1$ means that changing only coordinate $i$ changes $f$ by at most one:whenever $x_j=x_j^{\prime }$ for all $j\ne i$.

The function is $g$-certifiable when, whenever $f(x)=k$, there is a coordinate set $I$ with $|I|\le g(k)$ such that every $y$ agreeing with $x$ on $I$ satisfies $f(y)\ge k$. The coordinates in $I$ form a certificate for the assertion that the value is at least $k$.