Reservoir Sampling Technique

In this article, we have explained the Reservoir Sampling Technique which is the basis of Randomized Algorithms. We have covered two methods Simple Reservoir and Variable Probability.

Table of ContentsIntroductionMethod 1: Simple ReservoirMethod 2: Variable ProbabilityInitial proofRevision of algorithmProof of new algorithmApplicationsOverview

Prerequisite: Randomized Algorithms

Introduction

Reservoir Sampling is a group of randomised algorithms which helps us choose random samples ...