Timeline for A probability question related to extremal combinatorics
Current License: CC BY-SA 2.5
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 23, 2018 at 20:35 | answer | added | Kevin P. Costello | timeline score: 5 | |
| Oct 17, 2010 at 21:38 | comment | added | JBL | By the way, why wasn't that an answer? It has substantive content. | |
| Oct 17, 2010 at 21:35 | comment | added | JBL | zhoraster, I agree with your computation for $k = 3$, $n = 6$, but I disagree with your final conclusion: for $n \leq 8$, the probability of winning with singletons is better, but for $n > 8$, pairs win out. (I'm comparing $\frac{(n - 1)(n - 2)}{n^2}$ with $\binom{n}{2}^{-2} \cdot \left(\binom{n - 2}{2} \cdot \left(\binom{n}{2} - 6\right) + (2n - 2)\cdot \binom{n - 2}{2} \right)$ (the summands count the cases that the first two sets have intersection of size 0 vs. 1) and the latter is larger for $n > 8$.) | |
| Oct 17, 2010 at 16:07 | comment | added | zhoraster | 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. | |
| Jul 16, 2010 at 1:48 | comment | added | alex | @David Speyer - thanks, that's a good suggestion; I'll update the question with some simulation results soon. | |
| Jul 15, 2010 at 23:29 | comment | added | David E Speyer | I would suggest running some numerical simulations for $k=3$, choosing uniformly among sets of size $cn$ for various values of $c$. It's worth seeing whether your conjecture is plausible before we think too hard about proving it. | |
| Jul 15, 2010 at 22:30 | answer | added | gowers | timeline score: 5 | |
| Jul 15, 2010 at 20:24 | history | edited | alex | CC BY-SA 2.5 |
added 138 characters in body
|
| Jul 15, 2010 at 8:12 | history | edited | Charles Matthews | CC BY-SA 2.5 |
upper case title
|
| Jul 15, 2010 at 4:42 | comment | added | Michael Albert | @alex Sorry, stupid misreading of the question on my part. | |
| Jul 15, 2010 at 4:25 | comment | added | alex | @JBL - I think you're right. | |
| Jul 15, 2010 at 1:57 | comment | added | JBL | (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?) | |
| Jul 15, 2010 at 1:42 | comment | added | alex | @Michael Albert: consider $n=4,k=4$, i.e. four people picking subsets of $1,2,3,4$. If everyone picks a random singleton, the probability of winning is positive (should equal $4!/4^4$); but if everyone picks a random two-element subset, I believe (unless I messed up) the probability of winning is zero. | |
| Jul 15, 2010 at 1:19 | comment | added | JBL | @Michael Albert, that's not true: if we're picking pairs and we get {1, 2} and {1, 3} and {2, 3}, we lose. | |
| Jul 15, 2010 at 1:17 | comment | added | Michael Albert | 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. | |
| Jul 15, 2010 at 0:47 | comment | added | alex | Right: if two people pick the same subset, everybody loses. So this should not be happening too often under the optimal distribution $p$. | |
| Jul 15, 2010 at 0:42 | comment | added | BlueRaja | @Jonathan: but that will mean a guaranteed loss | |
| Jul 14, 2010 at 23:49 | comment | added | alex | Yes, absolutely. | |
| Jul 14, 2010 at 23:48 | history | edited | alex | CC BY-SA 2.5 |
added 32 characters in body
|
| Jul 14, 2010 at 23:46 | comment | added | Jonathan Fischoff | What I mean, is if one person picks (2,3,4) can another person pick (2,3,4) | |
| Jul 14, 2010 at 23:44 | comment | added | alex | 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$. | |
| Jul 14, 2010 at 23:42 | history | edited | alex | CC BY-SA 2.5 |
added 14 characters in body
|
| Jul 14, 2010 at 23:37 | comment | added | Jonathan Fischoff | I'm still trying to grasp the problem. When a combination is selected is it replaced | |
| Jul 14, 2010 at 23:14 | history | asked | alex | CC BY-SA 2.5 |