サンプルサイズ1はレザボアサンプリングと考えられますか？

Question

私のコードはリザーバのサンプリングであることを知りたいだけです。私はちょうど処理したいページビューのストリームを持っています。私は一度に1ページビューを処理しています。ただし、ページビューのほとんどは同じなので、ページビューをランダムに選択して（一度に1つずつ処理する）したいだけです。たとえば、ページビューが

です。

[www.example.com, www.example.com, www.example1.com, www.example3.com, ...] 

私は一度に1つの要素を処理しています。ここに私のコードです。

import random 

def __init__(self): 
    self.counter = 0 

def processable(): 
    self.counter += 1 
    return random.random() < 1.0/self.counter 

Answer 1

貯水池サンプリングのためのアルゴリズムに続いて（ここで見つけることができます：https://en.wikipedia.org/wiki/Reservoir_sampling）私達はちょうど1ページビュー（リザーバーサイズ= 1）を格納する場合は、次の実装は、ストリーミングページビューからの確率的選択の方法を戦略することを示しています均一選択確率につながる：

import numpy as np 
import matplotlib.pyplot as plt 
max_num = 10 # maximum number of pageviews we want to consider 
# replicate the experiment ntrials times and find the probability for selection of any pageview 
pageview_indices = [] 
ntrials = 10000 
for _ in range(ntrials): 
    pageview_index = None # index of the single pageview to be kept 
    i = 0 
    while True: # streaming pageviews 
     i += 1 # next pageview 
     if i > max_num: 
      break 
     # keep first pageview and from next pageview onwards discard the old one kept with probability 1 - 1/i 
     pageview_index = 1 if i == 1 else np.random.choice([pageview_index, i], 1, p=[1-1./i, 1./i])[0] 
     #print 'pageview chosen:', pageview_index 
    print 'Final pageview chosen:', pageview_index 
    pageview_indices.append(pageview_index) 
plt.hist(pageview_indices, max_num, normed=1, facecolor='green', alpha=0.75) 
plt.xlabel('Pageview Index') 
plt.ylabel('Probability Chosen') 
plt.title('Reservoir Sampling') 
plt.axis([0, max_num+1, 0, 0.15]) 
plt.xticks(range(1, max_num+1)) 
plt.grid(True) 

上記から分かるように、選択されたページビューのインデックスの確率はほぼ均一（のそれぞれについて1/10 10ページビュー）、それは数学的にも均一であることが証明できる。