Timeline for How to sample uniformly from a stream of elements, some of which are unsuited?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 18, 2013 at 19:57 | comment | added | Yuval Filmus | @user995435 I added some pseudocode. | |
| Apr 18, 2013 at 19:57 | history | edited | Yuval Filmus | CC BY-SA 3.0 |
added 238 characters in body
|
| Apr 18, 2013 at 19:17 | comment | added | shn | @YuvalFilmus Ok, having an estimate of the number of elements crossing the threshold is more acceptable. So can you please provide the algorithm corresponding to your last suggestion (Edit2) so that I can better see your idea. Thanks. | |
| Apr 18, 2013 at 19:04 | comment | added | Yuval Filmus | @user995435 Ok, I have one more suggestion, which requires you to know in advance how many elements will cross the threshold. | |
| Apr 18, 2013 at 19:03 | history | edited | Yuval Filmus | CC BY-SA 3.0 |
added 396 characters in body
|
| Apr 18, 2013 at 17:54 | comment | added | shn | @Raphael I don't think it is impossible as far as we know the value N beforehand. | |
| Apr 18, 2013 at 16:47 | comment | added | Raphael | @user995434 I think it's obvious that you can't solve the problem online without deselecting elements. Otherwise, you'd have to always keep one slot open for the last element, but it is not always above the threshold. | |
| Apr 18, 2013 at 16:02 | comment | added | shn | So you can not select some B elements then replace them with new selected other elements, because you already finished you budget | |
| Apr 18, 2013 at 15:58 | comment | added | shn | (Firstly) For the first algorithm, do you mean "with probability 1/N" instead of "with probability 1/t" ? because with the first iteration t=1 and thus probability 1/t is 1 (Secondly) For the second algorithm, as soon as the condition "P(x) > T" is verified the other condition "with probability 1/count" is automatically verified because count will be 1 and thus the probability 1/count is 1. (Third) For the two last algorithms, if you carefully read my algorithm (in my question) you will see that you pay 1 dollar when you select x and you should output answer (label of selected x) immediately. | |
| Apr 18, 2013 at 14:05 | history | edited | Yuval Filmus | CC BY-SA 3.0 |
added 1320 characters in body
|
| Apr 18, 2013 at 7:29 | comment | added | shn | But as you can see in my Algorithm, we do not have the N elements beforehand; at each time t we see one new observation x_t. | |
| Apr 17, 2013 at 22:38 | history | answered | Yuval Filmus | CC BY-SA 3.0 |