Tag Archives: probability

Weighted Reservoir Sampling

Based on last Reservoir Sampling problem, I will develop it a little bit more. What if each element has a weight. Let’s say we have below elements. The struture is: [id, weight]: e0=[0, 2], e1=[1, 1], e2=[2, 1], e3=[3, 1], e4=[4, 1]. And we want to sample 2 of them. Let’s compute the possibilite that e0 will be… Read More »

Reservoir Sampling

I have a post about how to return a value by it’s weight by inputing a stream. http://allenlipeng47.com/PersonalPage/index/view/129/nkey Based on that, I will develop this to another problem: Reservoir Sampling. The probelm of Reservoir Sampling is like this. There are elements inputted by stream, which lenght is n. How can we uniformly choose m out of n elements. We assume… Read More »