A lottery on coins in a convex set

Question

You play the following game.

1. You get $4n$ gold coins and have to arrange them in the unit square in general position (no two coins have the same x or the same y coordinate). Call this set of coins $S_1$.
2. There is a lottery in which each coin in $S_1$ is selected with probability 1/2, independently of the others. Call the set of selected coins $S_2$ (it is a subset of $S_1$).
3. You select an axis-parallel rectangle $C$, with the constraint that it must contain exactly $2n$ original coins ($|C\cap S_1| = 2n$).
4. Your prize is the coins in $C\cap S_2$.

What is the largest number of coins that you can guarantee to yourself in probability at least $1-1/n$, by a sophisticated arrangement of the coins and selection of $C$?

NOTES:

• A. If you have to select $C$ before the lottery (steps 2 and 3 are swapped), then your prize is a binomial variable distributed like $Binom[2n,1/2]$. Its expected value is $n$, and by known tail-bounds, with probability at least $1-1/n$ the prize is at least $n-O(\sqrt{n\log n})$. Here you can select $C$ after seeing the lottery outcomes, so you can potentially do better.
• B. In contrast, if $C$ does not have to be convex, then of course you can just select a set which contains $2n$ coins of $S_2$ and your prize is $\min(|S_2|,2n)$. So the answer should be between $n-O(\sqrt{n\log n})$ and $2n$.
• C. I do not know the answer even in the simpler case in which $C$ must be a square or a 1-dimensional interval (about the latter case I asked in Math.Se).

Answer 1

One quick upper bound for the axis-parallel rectangle case for large $n$: Fix an arbitrary arrangement of $4n$ points. Then there are at most $cn^4$ distinct subsets of $2n$ points that lie inside axis-parallel rectangles containing exactly $2n$ points (the points in a rectangle are determined by an uppermost, lowermost, leftmost, and rightmost point).

For any fixed rectangle containing $2n$ points, the proportion of lotteries for which that rectangle beats $n+C\sqrt{n \log n}$ is $o(n^{-4})$ for sufficiently large $C$, by the same tail bounds you linked to. By the union bound, it follows that with probability approaching $1$ none of the axis-parallel rectangles beat $n+C \sqrt{n \log n}$.