3 ms·
I agree the paper is better than the blog post, although one criticism I have of the CVM paper is that it has some termination/algo exit condition instead of wh
by cb321 2y ago
I agree the paper is better than the blog post, although one criticism I have of the CVM paper is that it has some termination/algo exit condition instead of what Knuth's CVM notes (refed else-thread here) do which is just a loop to ensure getting more space in the reservoir halving-step. It seems more work to explain the https://en.wikipedia.org/wiki/Up_tack https://en.wikipedia.org/wiki/Up_tack than just do the loop. [1]
[1] https://news.ycombinator.com/item?id=40388878 https://news.ycombinator.com/item?id=40388878
- imglorp 2y agoOn that note, I'm also unfamiliar with this \ operator notation which is used without explanation. X ← X \ {ai}
- jtanderson 2y agoThat is conventional set subtraction notation. "Assign to X the same set minus all elements of the set {a_i}". One example source, but it is pretty common in general: http://www.mathwords.com/s/set_subtraction.htm http://www.mathwords.com/s/set_subtraction.htm
- rocqua 2y agoSet difference. Set X becomes X without element ai. This is the case whether ai was in the set X before the step was taken.
- _a_a_a_ 2y agoI've known that symbol for decades, never knew it's name - up-tack it is. Ta!
- kuldeepmeel 2y agoYou are indeed right; while has the added advantage of making the estimator unbiased -- i.e., not only strongly (epsilon,delta)-guarantees but also having an expectation of being correct). It wasn't easy to see that loop would have added benefit -- that's where Knuth's ingenuity comes in.