Reservoir Sampling: psuedocode, and proof.
Debajyoti Roy
118
Interview

Given:

  • a[i] where, 1 <= i <= n
  • randint(a, b) draws an integer r with uniform probability such that, a <= r <= b where, 1 <= a <= b.
  1. Pick s such that P(s = a[i]) is same for any a[i]
  • Pseudocode:
s = a[1]
for i = 2 -> n:
    if randint(1, i) = i:
	    s = a[i]
return(s)
  • Proof:
P(s = a[i]) 
 = P(a[i] gets picked) * P(a[i+1] doesn't get picked) * P(a[i+2] doesn't get picked) *...* P(a[n] doesn't get picked)
  = P(a[i] gets picked) * {1 - P(a[i+1] gets picked)} * {1 - P(a[i+2] gets picked)} *...* {1 - P(a[n] gets picked)}
  = (1/i) * (1 - 1/(i+1)) * (1 - 1/(i+2)) *...* (1 - 1/n)
  = 1/i * i/(i+1) * (i+1)/(i+2) *...* (n-1)/n
  = 1/n
  1. Pick s[j] where, 1 <= j <= k such that P(a[i] element of s) is same for any a[i]
  • Pseudocode:
s[1] = a[1], s[2] = a[2]...s[k] = a[k]
for i = k+1 -> n:
    j = randint(1, i)
	if j <= k:
	    s[j] = a[i]
return(s)
  • Proof:
P(a[i] element of s) 
  = P(a[i] gets picked as s[j]) * P(a[i+1] doesn't swap s[j]) * P(a[i+2] doesn't swap s[j]) *...* P(a[n] doesn't swap s[j])
  = P(a[i] gets picked as s[j]) * {1 - P(a[i+1] swaps s[j])} * {1 - P(a[i+2] swaps s[j])} *...* {1 - P(a[n] swaps s[j])}
  = (k/i) * (1 - 1/(i+1)) * (1 - 1/(i+2)) *...* (1 - 1/n)
  = k/i * i/(i+1) * (i+1)/(i+2) *...* (n-1)/n
  = k/n

Note: Probability of a[i] getting picked is k/i however, for a[i] to replace s[j] the probability is 1/i since there is only one choice out of i indices.

  • Practice Problem: WIP
Comments (0)