Jednolite próbkowanie z simpleks

Szukam algorytmu do generowania tablicy N liczb losowych, tak że suma N liczb wynosi 1, a wszystkie liczby mieszczą się w przedziale 0 i 1. Na przykład N = 3, losowy punkt (x, y, z) powinien leżeć w trójkącie:

x + y + z = 1
0 < x < 1
0 < y < 1
0 < z < 1

Idealnie chciałbym, aby każdy punkt w obszarze miał równe prawdopodobieństwo. Jeśli jest to zbyt trudne, mogę zrezygnować z tego wymogu. Dzięki.

Załóżmy najpierw, że chcesz pobrać próbkę

x + y + z = 1
0 ≤ x ≤ 1
0 ≤ y ≤ 1
0 ≤ z ≤ 1

Nie robi to żadnej różnicy, ponieważ punkt próbny nadal będzie znajdować się w żądanym obszarze z dużym prawdopodobieństwem.

Teraz pozostaje Ci próbkowanie punktu z simpleksu . W przykładzie 3d otrzymujesz dwuwymiarowy simpleks (trójkąt) zrealizowany w 3d.

Jak losowo wybrać punkt równomiernie został omówiony w tym poście na blogu (patrz komentarze).

Dla twojego problemu oznaczałoby to, że bierzesz liczb losowych z przedziału , a następnie dodajesz i aby uzyskać listę liczb . Sortujesz listę, a następnie rejestrujesz różnice między dwoma kolejnymi elementami. To daje listę liczby , która sumuje się do . Ponadto pobieranie próbek jest jednolite. Ten pomysł można znaleźć w Donald B. Rubin, The Bayesian bootstrap Ann. Statystyk. 9, 1981, 130–134.( 0 , 1 ) 0 1 n + 1 n $n-1$$(0,1)$$0$$1$$n+1$$n$$1$

Na przykład ( ) masz trzy liczby losowe, a następnie otrzymujesz posortowaną sekwencję, a to daje różnice , a przez konstrukcję te cztery liczby sumują się do 1.$n=4$0.4 0.2 0.10 0.1 0.2 0.4 10.1 0.1 0.2 0.6

Inne podejście jest następujące: pierwsza próbka z hipersześcianu (o której zapominasz x+y+z=1), a następnie normalizacja punktu próbkowania. Normalizacja jest rzutem z hypercube na d - 1 -simplex. Intuicyjnie powinno być jasne, że punkty w centrum simpleks mają więcej „punktów przed obrazem” niż na zewnątrz$d$$d-1$. Stąd, jeśli próbkujesz równomiernie z hipersześcianu, nie zapewni to jednolitego próbkowania w simpleksie. Jeśli jednak pobierzesz próbkę z hipersześcianu o odpowiednim rozkładzie wykładniczym, efekt ten zostanie anulowany. Rysunek pokazuje, w jaki sposób zostaną pobrane próbki obu metod. Jednak wolę metodę „sortowania” ze względu na jej prostą formę. Jest również łatwiejszy do wdrożenia.

Ma to na celu dodanie do istniejących odpowiedzi.

Devroye jest doskonałym źródłem odpowiedzi na tego rodzaju pytania. Rozdział 7 podaje algorytmy potrzebne do generowania jednolitych statystyk zamówień, których szuka OP.

$n$$[0,1]$$O(n \log n)$$n$$x_1,\ldots,x_n$$\mathrm{Exp}(1)$

$[0,1]$$2x+3y+z = 5$

X[0] = 0
for i = 1 to N-1
    X[i] = uniform(0,1)
X[n] = 1
sort X[0..N]
for i = 1 to N
    Z[i] = X[i] - X[i-1]
return Z[1..N]

W tym przypadku uniform(0,1)zwraca liczbę rzeczywistą niezależnie i równomiernie rozmieszczoną między 0 a 1.

Zobacz ten artykuł : Smith, N. i Tromble, R., Próbkowanie równomiernie z jednostkowego druku jednostronnego .