title: Initialization of Weighted Reservoir Sampling (A-Chao implementation)
body: <p>I am trying to implement A-Chao version of weighted reservoir sampling as shown in <a href="https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_A-Chao" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_A-Chao</a></p>
  
  <p>But I found that the pseudo-code described in wiki seems to be wrong, especially on the initialization part. I read the <a href="https://www.jstor.org/stable/2336002?seq=1#metadata_info_tab_contents" rel="nofollow noreferrer">paper</a>, it mentions we need to handle over-weighted data points, but I still cannot get the idea how to initialize correctly.</p>
  
  <p>In my understanding, on initialization step, we want to make sure all initial data points chosen should have same probability*weight to be chosen. However, I don't understand how the over-weighted points is related with that.</p>
  
  <p>Code I implemented according to the wiki, but the results show it is incorrect.</p>
  
  <pre><code>const reservoirSampling = &lt;T&gt;(dataList: T[], k: number, getWeight: (point: T) =&gt; number): T[] =&gt; {
    const sampledList = dataList.slice(0, k);
    let currentWeightSum: number = sampledList.reduce((sum, item) =&gt; sum + getWeight(item), 0);
    for (let i = k; i &lt; dataList.length; i++) {
      const currentItem = dataList[i];
      currentWeightSum += getWeight(currentItem);
      const probOfChoosingCurrentItem = getWeight(currentItem) / currentWeightSum;
      const rand = Math.random();
      if (rand &lt;= probOfChoosingCurrentItem) {
        sampledList[getRandomInt(0, k - 1)] = currentItem;
      }
    }
    return sampledList;
  };
  </code></pre>