# How to sample uniformly from a stream of elements, some of which are unsuited?

I get values $x_t$ in an online fashion and want to buy "good" ones, where "good" means that some measure $P(x_t) >T$. Consider the following simple algorithm.

T = 0.7
N = 100 // or any value N > B
B = 20 // or any value 1 < B < N

l = 0

for t from 1 to N:
input a new observation x_t
let P(x_t) the probability associated to x_t

if P(x_t) > T:
l = l + 1
pay 1 dollar to buy y_t the label of x_t
output immediately the label y_t


If the condition $P(x_t) > T$ is used then we get about $l = 100-70 = 30$, this is ok since the value of $T$ is set to $0.7$.

Now if I want to add a constraint which is: additionally to the fact that elements $x_t$ for which the label $y_t$ is purchased are those for which $P(x_t) > T$, I want also that we do not buy more than $B=20$ labels (for example because we only have 20 dollars as budget).

But the problem is that, if I replace the the condition ($P(x_t) > T$) by ($P(x_t) > T \wedge l < B$), then the elements $x_t$ for which we buy a label are more likely to be among the first elements $t$ that we browse (that is, for an element $x_{95}$ for $t = 95$ for example we will never have a chance to buy its label even if its probability was $P(x_{95}) \gg T$). But I want that all the elements from $t = 1$ to $N$ will have equal chance to buy their label (not advantaging only the first elements).

Note: the condition that $P(x_t) > T$ for buying the label of a new observation $x_t$, should not be removed from my code. This is important for me: only labels of observations for which $P(x_t)$ was higher than $T$ at time $t$, are possibly purchased; and we should not purchase more than our budget $B$. Note also that a purchased label should immediately be output after we buy it, we should not wait until the end to decide if we buy it or not.

Also, note that we do not have the N elements beforehand; at each time $t$ we see just one new observation $x_t$. And note that you pay 1 dollar when you select a given $x_t$ to ask for its label and that you should output answer (label of selected $x_t$) immediately; so you can not select some $B$ elements then replace them with new selected other elements, because your budget $B$ will already be finished.

• Throwing out the specifics, is this what you want to do: given some elements online, select a uniform sample out of those suited by some time-dependent measure? – Raphael Apr 18 '13 at 8:31
• @Raphael Given some elements online, I want to select no more than B informative elements according to an informativeness measure (P(x_t)). – shn Apr 18 '13 at 11:43
• That can't be everything. Buying the first $B$ elements over the threshold solves that problem, yet you say it does not solve yours. – Raphael Apr 18 '13 at 13:07
• @Raphael well, so I said in the question that I want that all candidate elements (having P(x_t) > T) have equal chance to be selected, and not only advantaging the first elements ... – shn Apr 18 '13 at 14:42

The easiest way to solve this problem might be to randomly permute the input. For example, you could compute a random permutation pi on N elements, and replace the main loop with

for s from 1 to N:
t = pi[s]
...


Edit: If you want to solve this in an online fashion, here is a different suggestion. Consider first the case $B=1$ and a threshold $T$ that always holds. So given a sequence of elements, we want to select a uniformly random one in an online fashion. This is done by the following algorithm:

for t from 1 to N:
x = input()
with probability 1/t:
selected = x
return selected


Now let's still assume that $B=1$, but let the threshold be arbitrary:

 count = 0
for t from 1 to N:
x = input()
if P(x) > T:
count = count + 1
with probability 1/count:
selected = x
return selected


Now assume we have arbitrary $B \geq 1$, but all the elements cross the threshold:

for t from 1 to N:
x = input()
if t <= B:
selected[t] = x
else:
with probability B/t:
i = random({1,...,B})
selected[i] = x
return selected


Finally, putting everything together:

count = 0
for t from 1 to N:
x = input()
if P(x) > T:
count = count + 1
if count <= B:
selected[count] = x
else:
with probability B/count:
i = random({1,...,B})
selected[i] = x
return selected


Edit 2: Here is yet another suggestion, assuming that you know both $N$ and the number of elements crossing the threshold, let's say $M$. You choose a random subset $S$ of size $M$ of $\{1,\ldots,N\}$. You select the $k$th element crossing the threshold for each $k \in S$.

If you only have an estimate for $M$, you can try a similar algorithm in which you guess $M$ and hope for the best.

Here is pseudocode for the algorithm:

S = random subset of {1,...,N} of size M
count = 0
for t from 1 to N:
x = input()
if P(x) > T:
count = count + 1
if count in S:
select x

• 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. – shn Apr 18 '13 at 7:29
• (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. – shn Apr 18 '13 at 15:58
• So you can not select some B elements then replace them with new selected other elements, because you already finished you budget – shn Apr 18 '13 at 16:02
• @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. – Raphael Apr 18 '13 at 16:47
• @Raphael I don't think it is impossible as far as we know the value N beforehand. – shn Apr 18 '13 at 17:54