Reservoir Sampling
This example uses reservoir sampling to choose a uniformly random item from a stream while keeping only one candidate. For a reservoir of size one, Algorithm R selects the first item and replaces the current sample with each later item at position with probability [Vitter 1985]. The replacement probability uses only the current position, so the algorithm need not know the final stream length in advance.
We represent a nonempty stream by its positions 1 through n and verify that each position x is the final sample with probability exactly .
Caesar proves an upper probability bound and a matching lower bound using a loop invariant.
A separate termination proof lets us combine these bounds into an equality.
The Programβ
The variable c holds the selected position, with zero marking the initial state before any item is processed.
The variable i is the next position to process.
Each iteration selects that position with probability 1/i, then advances i.
The parameter x identifies the position whose final selection probability we want to verify.
It appears only in the specification and invariant, so sampling does not depend on x.
Verified@wp coproc algorithm_r(n: UInt, x: UInt) -> (c: UInt)
pre !?(1 <= x && x <= n)
pre 1/n
post [c == x]
{
c = 0
var i: UInt = 1
@invariant(!?(1 <= i && i <= n + 1 && c < i) β ite(i <= x, 1/n, ((i - 1)/n) * [c == x]))
while i <= n {
var take: Bool = flip(1/i)
if take { c = i } else {}
i = i + 1
}
}
The postexpectation [c == x] is one when the final sample is x and zero otherwise.
Its expected value is therefore the probability of returning x.
The @wp coproc specification bounds this probability from above by 1/n for every valid position .
The first pre clause expresses this restriction, which also ensures that the stream is nonempty.
Why the Invariant Worksβ
At each loop head, the @invariant annotation bounds the probability of eventually returning x from the current state.
Its ite expression distinguishes whether position x is still to come or has already been processed:
If i > x, position x has already been processed.
When c != x, it cannot be selected again, so its final selection probability is zero.
When c == x, it remains the final sample precisely when no later item replaces it.
At each remaining position , the probability of keeping it is .
The probability of surviving all positions from i through n is
This gives the second case, ((i - 1)/n) * [c == x].
At loop exit, i == n + 1 and there are no remaining positions, so the product is one and this expression equals the postexpectation [c == x].
If i <= x, position x has yet to be processed.
It will be selected at iteration x with probability , then survive the later replacements with probability .
Their product is , giving the first case.
Iterations before x cannot affect this probability because they only choose among earlier positions.
Initially i == 1, so this case gives the required upper bound 1/n.
The additional condition 1 <= i && i <= n + 1 && c < i records the valid index range and ensures that c is either zero or an earlier position.
Outside these states, !?(...) makes the upper invariant infinite, so it imposes no bound there.
The Matching Lower Boundβ
To prove that x is selected with probability at least 1/n, we reuse the same ite expression in a proc under @wlp.
The invariant uses ?(...) β to give value zero outside the valid index range, as required for a lower bound.
@wlp proc algorithm_r_lower(n: UInt, x: UInt) -> (c: UInt)
pre ?(1 <= x && x <= n)
pre 1/n
post [c == x]
{
c = 0
var i: UInt = 1
@invariant(?(1 <= i && i <= n + 1) β ite(i <= x, 1/n, ((i - 1)/n) * [c == x]))
Under wlp, nontermination contributes one to the expected value.
This specification therefore proves that the probability of returning x or not terminating is at least .
We still need to rule out nontermination to obtain the claimed lower bound on returning x.
Termination and Uniformityβ
The loop processes exactly n positions: i starts at one and increases by one on every iteration, regardless of the random choice.
The following specification verifies termination with probability one.
@wp proc algorithm_r_terminates(n: UInt) -> (c: UInt)
pre 1
post 1
{
c = 0
var i: UInt = 1
@ast(1 <= i && i <= n + 1, (n + 1) - i, v, 1, 1)
The @ast annotation uses (n + 1) - i, the number of remaining items, as its variant.
It is positive while the guard holds and decreases by one with probability one on every iteration.
Since the program terminates almost surely, wp and wlp agree.
The verified bounds therefore give
so every stream position is selected with probability exactly .
See Alsoβ
- Morris Counting estimates the number of stream events using a randomized counter.
- Geometric Loop combines matching upper and lower bounds on an expected value.
Referencesβ
-
Vitter (1985). Random Sampling with a Reservoir.
Section 2 describes Algorithm R for a reservoir of arbitrary size. This example uses a reservoir containing one item.
(Section 2)