Timeline for Estimate number of distinct items
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:19 | history | edited | CommunityBot |
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
|
|
| Feb 23, 2013 at 16:45 | answer | added | Simd | timeline score: 0 | |
| Dec 11, 2012 at 9:25 | answer | added | Aaron Meyerowitz | timeline score: 0 | |
| Dec 10, 2012 at 20:22 | answer | added | Carl Feynman | timeline score: 3 | |
| Nov 26, 2012 at 18:45 | answer | added | Arthur B | timeline score: 0 | |
| Nov 24, 2012 at 10:20 | comment | added | Benjamin Dickman | This problem seems very difficult. Consider just the case where your array is the elements of an $n \times n$ multiplication table. Then the problem reduces to one first studied by Erdos in the mid 1950s. See, for example, mathoverflow.net/questions/31663/… | |
| Nov 24, 2012 at 8:32 | comment | added | Arnott | @QiaochuYuan, Ideally I would like to do a constant number of samples but I am also in just understanding the stats so I can see if I can change the setup to make something else work. I may, for example, be able to get away with just answering "the number is large" or "the number is small" but as pointed out, in the worst case you can't even do that. | |
| Nov 24, 2012 at 8:19 | comment | added | Arnott | A good point. Does it help if I put a limit on the maximum number of times the most frequent item can occur? Also, if I just want to answer the question "How likely is the number of distinct items to be more than $x$, say?", is that any easier (depending on what $x$ is)? | |
| Nov 24, 2012 at 4:36 | comment | added | fedja | The problem is that the worst case scenario is dismal here: take $N\ll n$ and put in the numbers $1,2,\dots,N,1,1,1,\dots,1$. The beginning part, which is the only important one, is virtually invisible in the sea of ones when you are doing the uniform sampling: until you've done at least $n/N$ samples, there is a good chance it is not detected at all and it is quite a question whether you are willing to get up to linear in $n$ when choosing the sample size. | |
| Nov 24, 2012 at 4:03 | comment | added | Qiaochu Yuan | There is a tension here between taking fewer samples and obtaining a more accurate estimate. You need to specify how you want to balance these competing demands before "best" is well-defined. | |
| Nov 23, 2012 at 22:16 | history | asked | Arnott | CC BY-SA 3.0 |