# A probability question related to extremal combinatorics

$k$ people play the following game: person $i$ independently picks a subset $S_i$ of $\{ 1,2,\ldots,n \}$ according to some distribution $p$ on the $2^n$ subsets; each person uses the same distribution $p$. If some $S_i$ is contained in $\cup_{j \neq i} S_j$, they all lose; else, they all win. What distribution $p$ maximizes the probability of winning?

I am actually only interested in the case where $n/k$ is an integer, in which case I would conjecture that the optimal distribution is for each person to pick a random subset with $n/k$ elements. I can prove this only for $k=2$, in which case it follows straightforwardly from Sperner's theorem.

Edit: JBL points out in the comments that its also easy to confirm the $n=k$ case of the conjecture in the previous paragraph.

-
I'm not sure what "replaced" means in this context; they are not picking balls out of a common bin. Each person independently picks a subset of $1,2,\ldots,n$. – alex Jul 14 '10 at 23:44
Regardless of n/k it seems to me that the most likely optimum is where each randomly picks a set of size $\lfloor n/2 \rfloor$. If everyone is always picking sets of the same size, then they lose only when two of them pick the same set, so it makes sense to have as many sets available as possible. – Michael Albert Jul 15 '10 at 1:17
@Michael Albert, that's not true: if we're picking pairs and we get {1, 2} and {1, 3} and {2, 3}, we lose. – JBL Jul 15 '10 at 1:19
(In fact, for $n = k$ I think it shouldn't be hard to show that a uniform distribution over singletons is optimal, since any positive probability on a non-singleton is completely wasted, no?) – JBL Jul 15 '10 at 1:57
The conjecture is false for $k=3$. If $n=6$ it's better to choose random singletons (the probability to lose is $4/9$) than random doubletons (the probability to lose is, counting conditionally on the number of elements in the intersection of doubletons of the first two players, $\frac1{15} + \frac8{15}\times \frac{9}{15} + \frac{6}{15}\times \frac{6}{15} = \frac{41}{75}$, unless I messed up). In fact, for $n$ big enough, when $k=3$ it is better to pick random singletons than random doubletons. – zhoraster Oct 17 '10 at 16:07

Here's a quick thought about the case k=3. Let's suppose we go for the uniform distribution on sets of size cn. Then with very high probability the union of the first two sets has size about (2c-c^2)n, so that almost all the time the conditional probability that the third set is contained in the union is about $\binom{(2c-c^2)n}{cn}/\binom n{cn}.$
Actually, for comparison let's look at the probability that the first two sets are disjoint and that their union contains the third. This is $\binom{(1-c)n}{cn}/\binom n{cn}$ multiplied by $\binom {2cn}{cn}/\binom n{cn}$. Again, we get an unpleasant enough number that I would be surprised if it were optimized at c=1/3.
Thanks; maybe I was too hasty in conjecturing an answer. I'll write some maple code to evaluate the probability explicitly for various $n,k$. – alex Jul 16 '10 at 1:46