Reservoir sampling algorithm probability
The whole reason for performing this sampling method is to get an uniform sample even if the population size is unknown at the start. So, if this method works, the probability cannot be skewed.

What happens, is that the samples chosen in the beginning have a chance to be overwritten by the samples chosen later. Intuitively, this balances it somewhat. But we must show that this 'balance' holds precisely: 

The probability of $\frac{k}{i}$ refers to the  probability that sample $i$ is added to the reservoir, as it is added when a uniform random integer from $[1,i]$ is less than $k$, i.e. $k$ positions in the range $[1,i]$ lead to inclusion in the reservoir. (Total number of events is $i$, number of events that we 'want' is $k$, all events are equally likely, so final probability is $\frac{k}{i}$)

Now what is the probability that $i$, when chosen, remains in the reservoir until the end? It gets removed when a single integer in the range $[1,m]$ is picked, for all $i&lt;m\leq N$. The probability that it doesn't get replaced at position $m$ is $1-\frac{1}{m}$. As these events are independent, the total probability that $i$ doesn't get replaced is $\prod_{m=i+1}^N (1-\frac{1}{m}) = \frac{i}{N}$ $^*$. As $i$ is in the reservoir at the end if it gets picked and not replaced, this probability is $\frac{k}{i}\cdot \frac{i}{N} = \frac{k}{N}$.

We're not done yet, as the calculation above only holds for the samples not originally in the reservoir. However, that case is similar: as they are always put in the reservoir, we only need the probability they stay, which is $\prod_{m=k+1}^N (1-\frac{1}{m}) = \frac{k}{N}$.

So the probability of being included in the final sample is the same for all positions, which means the final sample is uniform.

*: The expression $\prod_{m=i+1}^N (1-\frac{1}{m})$ can be simplified as follows: 

\begin{align}\prod_{m=i+1}^N (1-\frac{1}{m}) &amp;= \prod_{m=i+1}^N (\frac{m-1}{m})\\ &amp;= \frac{i}{i+1}\cdot\frac{i+1}{i+2}\cdots \frac{N-2}{N-1}\cdot \frac{N-1}{N}\\ &amp;= i\cdot\frac{i+1}{i+1}\cdot\frac{i+2}{i+2} \cdots \frac{N-1}{N-1}\cdot \frac{1}{N} =\frac{i}{N}.
\end{align}

It is also possible to show by induction on $N$, but I think the previous is more insightful.