5 ms·

> How is this true? If you're drawing from a deck of 2^64 cards then unless you're drawing almost all of them there's not going to be any problem with rejection

> How is this true? If you're drawing from a deck of 2^64 cards then unless you're drawing almost all of them there's not going to be any problem with rejection. Even if you're drawing 2^63 card you're going to be rejecting only half of your draws, so the average slowdown is going a factor of 2. It it though? I'm a but shoddy on my mathematics, but I'd wager from the birthday problem that you'd probably have to reject much more than half of the 'cards', and as you get to the end, you'd have to redraw several times for each card.

kadoban 7y ago
If you think about it one draw at a time it's pretty clear and there's no room to be missing anything really. 2^63 is half of 2^64. For the last draw, each time you try to pick an unused, what's the odds it was taken already? (approx 1/2) You won't have to try too many times. The draws before the last are strictly better, so overall you should be fine.
- mihaifm 7y ago
  That seems correct. On top of that, if you ever need to choose more than half, you choose n-k first then reverse the set. Could it be that the distribution condition is not satisfied? Although I don’t see how. The article could’ve explained the problem better (I mean it keeps reffering to “draw without replacement” - what does that even mean).
  - kadoban 7y ago
    The "choose n-k" trick is quite nice. It has one big downside though, which is that you can't start reporting any results until you're totally done. One algorithm that I haven't yet seen mentioned in this discussion is: shuffle the array of choices, pick the first k. If you're clever about it, this has some nice properties: you can stop shuffling after the first k, and if you want you can start reporting results immediately. (You'd want to use something like Fisher-Yates to shuffle for these properties) This also wouldn't use much extra space, and doesn't require special handling for small or large k. Biggest downside is it will change the order of the original set. And it's only worth doing if you already have an array full of the items to choose, most likely.
    - SamBam 7y ago
      I think the article discusses the fact that shuffling the entire initial set takes up way too much memory.
andreareina 7y ago
Birthday problem says that once you've gone through ~2^8 cards you've got a ~50% of having had to reject at least once. It takes 2^63 until you have a 50% chance of rejecting on each draw.
- AllegedAlec 7y ago
  Ah, right. I wasn't thinking properly. Thanks for the explanation.
- petters 7y ago
  You're right, but it's not 2^8. It is √2^64 = 2^32.
  - andreareina 7y ago
    Yes, thanks. Took the root of the wrong number.
IIAOPSW 7y ago
But on each draw you need to check if its a card you've already drawn. You can hold your cards in a set data structure but then you pick up the complexity of the insertion operation into sets. IIRC sets are basically hash tables that map keys to themselves. Insertion is O(1)...until you need to resize your table due to hash collision.

kadoban 7y ago

If you think about it one draw at a time it's pretty clear and there's no room to be missing anything really. 2^63 is half of 2^64. For the last draw, each time you try to pick an unused, what's the odds it was taken already? (approx 1/2) You won't have to try too many times. The draws before the last are strictly better, so overall you should be fine.

mihaifm 7y ago
That seems correct. On top of that, if you ever need to choose more than half, you choose n-k first then reverse the set. Could it be that the distribution condition is not satisfied? Although I don’t see how. The article could’ve explained the problem better (I mean it keeps reffering to “draw without replacement” - what does that even mean).
- kadoban 7y ago
  The "choose n-k" trick is quite nice. It has one big downside though, which is that you can't start reporting any results until you're totally done. One algorithm that I haven't yet seen mentioned in this discussion is: shuffle the array of choices, pick the first k. If you're clever about it, this has some nice properties: you can stop shuffling after the first k, and if you want you can start reporting results immediately. (You'd want to use something like Fisher-Yates to shuffle for these properties) This also wouldn't use much extra space, and doesn't require special handling for small or large k. Biggest downside is it will change the order of the original set. And it's only worth doing if you already have an array full of the items to choose, most likely.
  - SamBam 7y ago
    I think the article discusses the fact that shuffling the entire initial set takes up way too much memory.

andreareina 7y ago

Birthday problem says that once you've gone through ~2^8 cards you've got a ~50% of having had to reject at least once. It takes 2^63 until you have a 50% chance of rejecting on each draw.

AllegedAlec 7y ago
Ah, right. I wasn't thinking properly. Thanks for the explanation.
petters 7y ago
You're right, but it's not 2^8. It is √2^64 = 2^32.
- andreareina 7y ago
  Yes, thanks. Took the root of the wrong number.

IIAOPSW 7y ago

But on each draw you need to check if its a card you've already drawn. You can hold your cards in a set data structure but then you pick up the complexity of the insertion operation into sets. IIRC sets are basically hash tables that map keys to themselves. Insertion is O(1)...until you need to resize your table due to hash collision.