<p>The best way to get the distribution that Chao's algorithm produces is to implement VarOpt<sub>k</sub> sampling as in the pseudocode labeled Algorithm 1 from <a href="https://arxiv.org/abs/0803.0473" rel="nofollow noreferrer">the paper that introduced VarOpt<sub>k</sub> sampling</a> by Cohen et al.</p>

<p>That's an arXiv link and hence very stable, but to summarize, the idea is to separate the items into "heavy" (weight high enough to guarantee inclusion in the sample so far) and "light" (the others). Keep the heavy items in a priority queue where it is easy to remove the lightest of them. When a new item comes in, we have to determine whether it is heavy or light, and which heavy items became light (if any). Then there's a sampling procedure for dropping an item that treats the heavy &rarr; light items specially using weighted sampling and then falls back to choosing a uniform random light item (as in the easy case of Chao's algorithm).</p>

<p>The one trick with the pseudocode is that, if you use floating-point arithmetic, you have to be a little careful about "impossible" cases. Post your finished code on Code Review and ping me here if you would like feedback.</p>
Initialization of Weighted Reservoir Sampling (A-Chao implementation)
<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>