Timeline for Expected size of the smallest preimage set
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 8, 2019 at 17:15 | vote | accept | Ievgeni | ||
| Jan 8, 2019 at 6:53 | comment | added | Anthony Quas | This gives (I think) $L=M-2\sqrt{\log M}$ as a fairly good approximation to the smallest bin size. | |
| Jan 8, 2019 at 6:49 | comment | added | Anthony Quas | I would use the following heuristic: as mentioned you are taking a random function from $M^2$ points to $M$ points. The number of times that the value $i$ is taken is close to normal with mean and variance both equal to $M$. These random variables are close to independent. So we'll approximate by $Z_i\sim \mathcal N(M,M)$, or $Z=M+(\sqrt M)N$ where $N$ is a standard normal and $Z_i$ is the number of times the value $i$ is taken. Now since there are $M^2$ random variables, you solve $\mathbb P(Z<L)=1/M^2$ for a good approximation of the typical smallest bin size. | |
| Jan 8, 2019 at 1:14 | answer | added | kodlu | timeline score: 1 | |
| Jan 7, 2019 at 18:49 | comment | added | esg | I don't have time now for a long answer. You are considering the order statistics of the multinomial distribution. A precise answer to your question (in form of a limit theorem for the occupation of the smallest cell occupancy) is given in the book [1] (theorem 7 on p.112 (essentially confirming Gerhard Paseman's intuition)). [1] Kolchin,V.F. and Sevast'yanov,B.A. and Chistyakov, V.P., Random Allocations. V.H. WINSTON & SONS, Washington, D.C., 1978. | |
| Jan 7, 2019 at 18:40 | review | Close votes | |||
| Jan 12, 2019 at 3:05 | |||||
| Jan 7, 2019 at 17:41 | comment | added | Gerhard Paseman | The reasoning with Y is that if the expected set size is small, then (by looking at all subsets of that size), there should be a lot of functions on the complement of Y with less than full image. I maintain there aren't enough if the size of Y is logarithmic with respect to the size of the whole space. Try a sum over all small subsets Y of all functions whose image off of Y is not full. Even with overcounting, the number should be exponentially small with respect to all functions when Y is quite small. Gerhard "A Big Use Of Smallness" Paseman, 2019.01.07. | |
| Jan 7, 2019 at 17:27 | comment | added | Ievgeni | I'm agree that most of the set will be of same size of $X$. But it's not obvious (and chebychev inequality don't give any intuition on that result) that there is no set with small cardinality, and I don't understand the reasoning with $Y$... | |
| Jan 7, 2019 at 17:19 | comment | added | Gerhard Paseman | I doubt the preimage is that small. With relabeling, your random function is from $X^2$ to $X$, so I would expect most if not all preimage sets close to the size of $X$. To strengthen this intuition, pick a small subset $Y$ of $X^2$. Off of $Y$, the number of functions on the complement with less than full image is so much smaller than those with full image. Gerhard "Multinomial Distribution Has Small Tails" Paseman, 2019.01.07. | |
| Jan 7, 2019 at 17:14 | history | edited | YCor | CC BY-SA 4.0 |
added 2 characters in body; edited title
|
| Jan 7, 2019 at 17:03 | history | asked | Ievgeni | CC BY-SA 4.0 |