22,086 reputation
33761
bio website
location
age
visits member for 3 years, 8 months
seen 8 hours ago

?


May
29
revised Probability $k$ bins are non-empty
the bins need not be distinct!
May
29
answered Probability $k$ bins are non-empty
May
29
comment Probability $k$ bins are non-empty
@felix: Oh BTW, they also prove that you can replace the $e\sqrt{N}$ with $2$ when the probability of the event is either monotonically increasing or decreasing in the total number of balls, as is the case here.
May
29
comment Probability $k$ bins are non-empty
@felix: I guess the understanding is that when $k$ is large, it's not large compared to the other factor. This analysis is one that's supposed to help with rare events. But you're right, in small instances (say $m=1024$, $n=128$, and $k=6$?), it may be very large. But then for small instances we can do the probability analysis directly and exactly I guess. BTW, the analysis they do in the book, which I guess is what is reproduced in the slides (and now makes sense), is slightly different; they're using this $e\sqrt{N}$ factor for a different term. So the false positive rate is without it.
May
29
comment If I have three points, is there an easy way to tell if they are collinear?
@ronno: Thanks for pointing it out. Very bad of me; I hope it's right now...
May
29
revised If I have three points, is there an easy way to tell if they are collinear?
ok, not so bad
May
29
answered If I have three points, is there an easy way to tell if they are collinear?
May
29
revised Probability $k$ bins are non-empty
What I learned from the book
May
29
revised Probability $k$ bins are non-empty
cleanup
May
29
comment $R_n = 3(2^n)-4(5^n)$, $n \geq0$, prove $R_n$ satisfies $R_n = 7R_{n-1}-10R_{n-2}$
That's right so far; just go on. :-) If it helps you think more clearly, maybe you can let $2^{n-2} = x$ and $5^{n-2} = y$, so that $2^{n-1} = 2x$ and $5^{n-1} = 5y$, and finally $3(2^n) - 4(5^n) = 3(4x) - 4(25y)$. You're trying to show that that's the same as the RHS, which is $7(3(2x)-4(5y)) - 10(3x-4y)$.
May
28
comment Probability $k$ bins are non-empty
@felix: That's very cool; it makes sense now! It's all rigorous finally... I'll update this answer in a couple of days. Thanks for the reference... the techniques developed there (pages 100 to 104) are very useful in these general situations, for bounding the error we incur by assuming independence.
May
28
comment Probability $k$ bins are non-empty
@felix: It makes sense except for the $er^{1/2}$ factor he introduces for the "exact case" versus "Poisson case"... anyway even if we understand that, he's still doing the same independence assumption, so it doesn't help.
May
27
comment Probability $k$ bins are non-empty
@felix: Another issue is that it's not clear what to give the bounds in terms of: $n$, without assuming anything about $m$ and $k$? Or in terms of $m$? Or $N$?
May
27
revised Probability $k$ bins are non-empty
cleanup, leave unfinished
May
27
comment Probability $k$ bins are non-empty
@felix: Sorry, I guess I don't have precise numerical bounds after all, but you can see from the expressions above that for large $N$ they are very close.
May
27
revised Probability $k$ bins are non-empty
some more similarity-showing
May
27
revised Probability $k$ bins are non-empty
fix typos
May
27
revised Probability $k$ bins are non-empty
fix typos
May
27
answered Probability $k$ bins are non-empty
May
27
comment Subsets - is it possible or not?
This question is plagiarized/lifted from codechef.com/problems/ARRAYTRM