次のようなシャッフルアルゴリズムを考える(簡単のためrand()%Nと表記したが、この部分で0以上N-1未満の一様な整数乱数が生成されると仮定して議論する)。出力されるものは 0, ..., 255 を並び換えたもの(置換)である。 std::vector<int> a(N); for(int i = 0; i < N; ++i) { a[i] = i; } for(int i = 0; i < N; ++i) { std::swap(a[i], a[rand()%N]); } このアルゴリズムは均一ではない。a[i]==jとなる確率は、 i < jのときに高くなり、j <= iのときに低くなる。グラフにすると以下のようになる。 定理 上のシャッフルアルゴリズムで得られる aについて、 a[i]==jとなる確率は、 となる。 証明 2個目のループの本体が 回 実行された時点で a[i]==
![とある偽シャッフルアルゴリズムとその分布 - 簡潔なQ](https://cdn-ak-scissors.b.st-hatena.com/image/square/b12c2db08bd686aac1526cfa34d28fe8679a82ae/height=288;version=1;width=512/http%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2Fq%2Fqnighy%2F20160605%2F20160605175316.png)