# Distributed Random Sampling

## Introduction

Random Sampling is one of the basic task in a modelling pipeline and a prerequsite to implementing many machine learning algorithms. The post will dwelve into couple of approaches for solving the random sampling problem efficiently for a single machine and extend the solution for a distributed system.

## Problem Statement

The problem would to produce a random sample of $k$ elements without replacement from a population of unknown size.

## Preliminary Approach

The most basic approach would be generate a random number corresponding to each element of the sample using a uniform random number generator in $[0, 1]$ and pick up the top k elements with highest corresponding random values.

This algorithm could be implemented in $O(n\log(k))$ time in an online fashion using a min heap for maintaining $k$ elements which have the highest corresponding random number, where $n$ is the population size.

### Proof

The outline of the proof is to prove that the probability of an element’s corresponding random number to be $i^{th}$ largest is equal to $\frac{1}{n}$ and hence the probability of every element to occur in the sample is $\frac{k}{n}$.

One thing to note is given a uniform random distribution in range $[0, 1]$ the probability of the generated number to be less than $x$ is $x$ and the probability of the generated number to be greater than $x$ is $(1 - x)$.

Now let us compute the probability of for an element’s corresponding random number say $x$, to be in the $i^{th}$ largest, for which we need to select $(i - 1)$ other random numbers to be greater than this one (in $^{(n - 1)}C_{(i - 1)}$ ways) and $(i - 1)$ other random numbers should be greater than $x$ and $(n - i)$ other random numbers has to be less than $x$. Hence the probability is

as we have $\int_0^1 { {x^a} * {(1 - x)^b} }dx$ is the beta intergal which equals to $\frac{ {a!} * {b!} }{(a + b + 1)!}$.

### Code

An implementation in Python would be:

### Extensions

• A simple extension would be to would be to allow for stable sampling which could be achieved by storing index of the element along the generated random and sorting the sample based on the index while returning the sample.
• Another extension would be allow sampling with replacement which could be achieved by generating $k$ random numbers for each element in the stream.

Although this algorithm seems optimal the algorithm is slow for large sample sizes over very large populations, which leads to the next approach.

## Reservoir Sampling Approach

The Reservoir Sampling Algorithm as made popular by Donald Knuth in his 2nd volume of the Art of Computer Programming solves the above problem in an online fashion in $O(n)$ time. The beauty of the algorithm is that has a quite a simple implementation and a simple recursive proof.

The algorithm proceeds by filling the sample with first k elements in the population, and goes onto to process the next element one each at a time employing the following process:

1. Lets say the index of the element is i.
2. Generate a random integer in random [0, i) with uniform random number generattor.
3. If it falls below k swap the element below at that index in the sample with current element.


### Proof

First thing to note is selecting the $i^{th}$ element and replacing an element in the already selected sample are independent events.

Lets assume that at after processing $i$ elements the probability of each element in the sample is $\frac{k}{i}$, now have to show that the probability of each element in the sample is $\frac{k}{(i + 1)}$.

The probability of the $(i + 1)^{th}$ element to be in sample is $\frac{k}{(i + 1)}$ and amongst the previously the probability that the element at $j^{th}$ position will be part of sample after processing $(i + 1)^{th}$ element is $\frac{k}{i}*(1 - \frac{1}{(i + 1)}) = \frac{k}{(i + 1)}$

### Code

An Python implementation would be:

## Extended Problem Statement

We have solved the problem of sampling k elements problem from a population of unknown size, we would like to extended to handle weighted sampling.

The extended problem could be solved by extending the our initial approaches as follows:

## Preliminary Approach

The following algorithm by Efraimidis and Spirakis extends preliminary approach to accomodate weighted sampling by replacing the random number $r _ {i}$ generated for each element $e _ {i}$ with $r _ {i}^{\frac{1}{ w _ {i} } }$.

### Proof

The proof is bit involved and tedious but one could be inututively appreciate the algorithm by computing the probability of a element $e_{i}$ to be in the first position which is:

If any one comes across a simpler proof please let know.

## Reservoir Sampling Approach

The following algorithm by M. T. Chao achieves weighted random sampling by means of reservior. For processing an $i^{th}$ element the algorithm computer probability $p_{k} = \frac{w_{k} }{\sum_{i=0}^{k}{w_{k} } }$ with which it will be included in the sample, if the element is selected it will replace an element in the current sample an random uniformly.

### Proof

It’s easy to observe that the probability of an element $e_{j}$ to be in sample is:

## Final Problem Statement

The problem would to produce a random sample of $k$ elements without replacement from a population of unknown size in a distributed fashion.

### Solution

Weighted versions of both approaches approach could be easily adapated to distributed environment by the paritioning the population into paritions of size $p_{i}$ and assigning the weight of selection for each element in the sample to $\frac{1}{p _ {i}}$ and choose top $k$ from each parition and merge all the top $k$’s to get the final top $k$ elements.