Timeline for What is the expected number of missing random integers?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 30, 2018 at 5:32 | vote | accept | Conifold | ||
| Jan 30, 2018 at 3:39 | answer | added | Brendan McKay | timeline score: 4 | |
| Jan 29, 2018 at 9:12 | comment | added | N. Gast | I must say that I do not know a general way to obtain such estimate. If I were to try, I would use the same approach as you do and would try to get rid of the epsilon by using some kind of uniform bound like Hoeffding's inequality. | |
| Jan 29, 2018 at 0:43 | history | edited | Conifold | CC BY-SA 3.0 |
deleted 4 characters in body
|
| Jan 26, 2018 at 19:31 | history | edited | Conifold | CC BY-SA 3.0 |
added 112 characters in body; edited tags
|
| Jan 26, 2018 at 17:06 | comment | added | Conifold | @N.Gast Yes, I'd like to know what the leading term(s) are for $n-S_n$ (number of present integers), naive guess is $n-S_n\sim\frac12\pi n\ln n+\frac12\pi\!\ln\pi\,n$, but I do not know how to get rid of the $\varepsilon$-s so it is possible that the growth is more subtle. And I'd like to know a general approach for refining the asymptotic for similar sums (which would come in estimating variance, etc.), if there is one, these estimates seem ad hoc and unimprovable along these lines. | |
| Jan 26, 2018 at 7:40 | comment | added | N. Gast | From what you wrote, it seems that you are able to obtain that $1-O(1/\sqrt{n\log(n)})$ elements will be missing. Are you looking for something sharper? | |
| Jan 25, 2018 at 20:42 | history | edited | Conifold |
edited tags
|
|
| Jan 24, 2018 at 23:46 | comment | added | Conifold | @MattF. Let's hope someone has better ideas. I expected suggestions along these lines because they were made in somewhat similar problems (where only one range contributes to the leading term and the rest are estimated as negligible), so this is to suggest that some additional ideas are needed to make it work here. But I will be happy with a completely different idea that works. | |
| Jan 24, 2018 at 4:25 | comment | added | user44143 | This question might be improved by cutting it off after “probability 1/2”. In particular I recommend against describing bad ideas with more than one sentence. | |
| Jan 23, 2018 at 19:02 | history | asked | Conifold | CC BY-SA 3.0 |