Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

$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.

share|improve this question
1  
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
1  
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
3  
@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
3  
(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
1  
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
show 12 more comments

1 Answer

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}.$

This isn't necessarily a very good heuristic, since if the first two sets are more disjoint, then it becomes much more likely that the third will be contained in the union, so the fact that the probability is small doesn't mean that one can disregard the possibility. But if one does the calculation more carefully, it doesn't seem obvious that the optimum will be at c=1/3.

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.

So this isn't exactly an answer. It's just a suggestion that it ought to be instructive to think about which layer is best if you want to take the uniform distribution on some layer.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.