Hacker News Reader

Comment by cb321 | Hacker News Reader

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 than just do the loop. [1]

[1] https://news.ycombinator.com/item?id=40388878

View on HN

You 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.

On that note, I'm also unfamiliar with this \ operator notation which is used without explanation.

    X ← X \ {ai}

That 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

Set difference.

Set X becomes X without element ai. This is the case whether ai was in the set X before the step was taken.

I've known that symbol for decades, never knew it's name - up-tack it is. Ta!

Reply on news.ycombinator.com