algorithm - 貯留層サンプリング理解確率

Question

貯水池サンプリングに関連する確率を理解するのに苦労しています。以下は、ほぼすべての場所で使用されているサンプル コードです。

    1/*
    2  S has items to sample, R will contain the result, K number of items to select
    3*/
    4ReservoirSample(S[1..n], R[1..k])
    5  // fill the reservoir array
    6  for i = 1 to k
    7      R[i] := S[i]
    8
    9 // replace elements with gradually decreasing probability
    10  for i = k+1 to n
    11    j := random(1, i)   // important: inclusive range
    12    if j <= k
    13        R[j] := S[i]

私の理解は正しいですか(?): k=3 と入力 = [100, 200, 300, 400, 500] があり、i が現在 500 インデックスにあるとします。リザーバー内の 300 を 500 で置き換える確率 (サイズは 3) = リザーバー内で 300 が選択される確率 * 500 が選択される確率。 5 つの選択肢 = 1/3 * 3/5 = 1/5