Timeline for Smallest $k$ so that $k$-wise independence guarantees a constant expected minimum
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 5, 2015 at 15:17 | vote | accept | Simd | ||
| Mar 29, 2015 at 18:18 | history | bounty ended | Simd | ||
| Mar 24, 2015 at 13:39 | comment | added | Will Sawin | I think it's $1/m$, just like the answer for $2$ moments, because you can cancel the contribution of $N_m=0$ to the skewness by slightly adjusting the probability that $N_m$ is large, while not affecting the variance very much. The next question is whether you can choose dependencies of the $N_m$s such that the intermediate moments are OK. | |
| Mar 24, 2015 at 13:36 | comment | added | Will Sawin | @dorothy I think that one has a constant expected minimum. I think getting a nonconstant expected minimum, if possible, requires a distribution that does not treat $1$ to $n$ symmetrically. A related question: If $N_m$ is a random variable valued in $\mathbb N$ whose first three moments are the same as a Poisson variable with mean $m$, what is the largest possible value of $P(N_m=0)$? | |
| Mar 23, 2015 at 10:53 | comment | added | Simd | Thank you! I don't know if it is helpful but Douglas Zare gave a very nice $3$-wise independent process at mathoverflow.net/a/102214/48334 previously. It was interesting as it showed that in that case $4$-wise independence really was necessary. | |
| Mar 22, 2015 at 20:36 | history | answered | Will Sawin | CC BY-SA 3.0 |