問題タブ [uniform-distribution]

私の目標は、0、... n-1 から k 個の整数を重複なくサンプリングすることです。サンプリングされた整数の順序は重要ではありません。各呼び出しごとに (非常に頻繁に発生します)、n と k はわずかに異なりますが、それほど大きくはありません (n は約 250,000、k は約 2,000)。私は、次の償却 O(k) アルゴリズムを思い付きました。

1. 項目 0、1、2、...、n-1 を持つ配列 A を準備します。これには O(n) かかりますが、n は比較的安定しているため、コストを償却して一定にすることができます。
2. [0:i] から乱数 r をサンプリングします。ここで、i = n - 1 です。ここで、コストは実際には n に関連していますが、n は非常に大きくないため、この依存関係は重要ではありません。
3. 配列 A の r 番目の項目と i 番目の項目を入れ替えます。
4. i を 1 減らします。
5. ステップ 2 ～ 4 を k 回繰り返します。これで、A の末尾に長さ k のランダム順列ができました。これをコピーします。
6. ステップ 1 のコストを一定に保つために、A を初期状態 (0、...、n-1) にロールバックする必要があります。これは、ステップ 2 の各パスで長さ k のスタックに r をプッシュすることで実行できます。スタックの準備には、償却された定数コストが必要です。

順列/組み合わせの均一なサンプリングは徹底的に研究された問題であるべきだと思うので、（1）はるかに優れた解決策があるか、少なくとも（2）私の解決策はよく知られている解決策（のマイナーな変更）です。したがって、

• (1)の場合、そのより良い解決策を知りたいです。
• (2)の場合は参考文献を探したい。

私を助けてください。ありがとう。

私の編集をここに置くつもりです：

コメントでは、ランダム性の実際の性質が議論されています。私が理解しているのは、「乱数」を生成するときに生成される可能性が高い、または低いということです。

うまくいけば、私の質問のより公平な言い回しは次のとおりです。

どの数値も別の数値より多かれ少なかれ確率が高くない場合、数値が常に一様に分布するとは限らないのに、一様分布関数がそれ自体を呼び出すことができるのはなぜですか?

質問する前にはっきりさせておきますが、私は好奇心から質問しているだけです。幸運なことに、私は猫ではありません。

私は大学のプロジェクト用にクイックソート機能を作成しましたが、(キーボードをしばらく叩くのではなく) ランダムに生成された整数のリストでテストできるのではないかと考えました。

この実装に完全に依存して、常に実際にはランダム (均等に分散) しているように見える乱数を生成できますか?

あなたは私がばかげていると思うかもしれません...明らかに、クラスはそれが一様分布であると述べています.不均一であることは不可能です...しかし、これらの出力のいずれかは可能ですか? もしそうなら、どのくらいの可能性がありますか？

最後の出力は最初または 2 番目の出力よりも可能性が高いと思いますが (特に 0 から 100 の境界を使用する場合)、私の好奇心はまだ私を悩ませています。
私は特に愚かですか？私は数学があまり得意ではなかったので、記号と用語を理解し始めていますが、まだいくつかの説明を見て、単に「うわべだけ」しているので、これまでのグーグル検索は役に立ちませんでした.

この質問のアルゴリズムは、多次元ボールから効率的にサンプリングする方法を教えてくれます。多次元リングから同様に効率的にサンプリングする方法はありますか、つまりr1<r<r2

そのスケーリング関数のあまり複雑でない変更 r*(gammainc(s2/2,n/2).^(1/n))./sqrt(s2)が可能であることを願っています。（平凡な免責事項：元のスケーリング関数の代数/幾何学をまだ理解していません）。

コピーペーストされた元の matlab コード:

ダニエルの答えからのデモと同等のpythonコード：