Comment by ridiculous_fish | Hacker News Reader

Comment by ridiculous_fish | Hacker News Reader

ridiculous_fish

> The first obstacle that makes the “dealing” (without replacement) hard is that the “draw” method doesn’t work. If you draw (with replacement) over and over again, ignoring cards you’ve already picked, you can simulate a deal, but you run into problems. The main one is that eventually you’re ignoring too many cards and the algorithm doesn’t finish on time (this is the coupon collector’s problem).

I don't think this is true!

First note that if you want to pick 98 values from 100, it is much simpler to instead decide which 2 to skip. Similarly when picking 75 out of 100 - better to just cross out 25. The hardest case is picking half: N/2 out of N, without replacement.

This is the Coupon Collector's problem, except we're stopping at half the coupons. We can use the analysis given in the Wikipedia page [1], except we only take the second half of the series.

This gives an expected time of

    N * (H(N) - H(N/2))

where H(X) is the Xth Harmonic number.

In the asymptote this yields:

    N * (γ + ln(N) - γ - ln(N/2))
    = N * (ln 2)

so the expected time of the "retry on duplicates" approach is linear in N. (Of course, the worst case is infinite, if you keep redrawing the same card.)

edit: To complete the analysis, the requirement is that the answer be linear in k, the number of items selected. But we have k < N, so if we are O(N) we are also O(k) or better. So I think the argument works.

[1] https://en.wikipedia.org/wiki/Coupon_collector%27s_problem

I think it is true. We head off discussion here by referring to the naive approach, but what you're doing is past naive coupon collector's and past the technical scope of the context.

There are several steps where your method could (will) fail. Since you don't introduce any machinery for the hand, you imply an O(k^2) checking algorithm. You also imply an unsorted hand. If you generate the hand in random order, then you fall to an O(k*lg(k)) sort. "Sorted" is an implicit requirement that we initially omit, but revisit later, because introducing it early makes the discussion harder to follow.

If you try to introduce machinery like a hashtable, the next thing you might suggest, you violate an implicit O(1) additional space requirement, which I've grudgingly reintroduced to the more-formal description ("why is this here?"). This conversation keeps going, but other failure paths we leave unexamined.

In addition to not being sorted it's also not "online." You won't get the first value out of it in constant time if k is too big, and you need to access elements in a random order.

This is not correct as written: "But we have k < N, so if we are O(N) we are also O(k) or better."

That's right. We can fix it up though. The E(t_i) we care about are bounded above by a constant (2), so the sum of k such expectations is linear in k.

For the cases where k > n/2, the "full table scan" portion is of course also linear in k.

Nice save! FWIW, here's the fix I wrote up before I saw yours. Yours is much better ;)

We only need to consider values in the range 0 < k <= N/2. If k > N/2, we "pick the losers instead of winners" and that reduces k to that range.

The expected time E to pick k out of N, is N times the last k terms of H(N):

    E(k) = N * (H(N) - H(N-k))

Applying the asymptote:

   E(k) ~ N * (γ + ln(N) - γ - ln(N-k))
        = N * (ln(N) - ln(N-k))

We wish to determine its behavior as a function of k. Taking the derivative:

   dE/dk ~ N/(N - k)

which is positive and bounded above by 2 for 0 < k <= N/2:

   dE/dk <= 2

Using the fact that E(1) = 1, we have:

   E(k) <= 2k

So E cannot be worse than linear in k.

This crossing out is, of course, not possible if you have a stream coming in, which is the case for which these sampling algorithms are used the most.

Reply on news.ycombinator.com