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

Question

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.

Answer 1

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