python - 与えられた確率行列 P[i, j] で確率 P[i, j] のペア (i, j) をランダムに選択する

Question

P[i, j] >= 0 で、すべての P[i, j] の合計が 1 になるような numpy の 2 次元配列 P があります。確率 P[i, j] でインデックス (i, j) のペアを選択する方法は?

編集: numpy ビルド機能に興味があります。この問題には何かありますか？1次元配列の可能性がありますか？

Answer 1

これは、あなたが期待していることを行うPythonの簡単なアルゴリズムです。

たとえば、[0.1,0.3,0.4,0.2] に等しい単一次元配列 P を考えてみましょう。ロジックは、任意の数の次元に拡張できます。

ここで、各要素をそれに先行するすべての要素の合計に設定します: P => [0, 0.1, 0.4, 0.8, 1]

乱数発生器を使用して、0 から 1 の間の数値を生成します。x = 0.2 としましょう。単純な二分探索を使用して、x が最初の要素と 2 番目の要素の間にあることを確認できます。この x の値の最初の要素を選択するだけです。

よく見ると、0 =< X < 0.1 である確率は 0.1 です。0.1 =< x < 0.4 の確率は 0.3 などです。

2D 配列の場合は、2D 配列バイナリ検索アルゴリズムを実装できるはずですが、1D 配列に変換することをお勧めします。

Answer 2

# setup
import bisect
import numpy as np
cs = P.cumsum()

# get random value
r = np.random.uniform()
i, j = divmod(cs.searchsorted(r), P.shape[1])

O(n) 初期設定、O(log n) 選択。