Jednolite próbkowanie z simpleks

29

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.

— Ruofeng
źródło

Jaki jest rozkład docelowy? Czego próbowałeś?

— Raphael

3

Zauważ, że zawsze istnieje próbka odrzucenia : próbkuj liczb jednolitych i odrzuć, jeśli liczby nie sumują się do . Tutaj oczekiwana liczba iteracji jest niewygodnie wysoka, dlatego powinieneś zrobić coś innego.

n

$n$

1

$1$

— Raphael

28

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. $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 -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.

Przykład 2 metod pobierania próbek

— A.Schulz
źródło

Myślę, że naiwny pomysł - narysuj

liczb z

i znormalizuj - jest więc błędny.

n

$n$

(0, 1)

$(0,1)$

— Raphael

Odpowiedziałem na twoje pytanie w rozszerzonej odpowiedzi.

— A.Schulz

1

Czy istnieje prosty dowód, który pokazuje, że sortowanie daje jednolity rozkład? Prawdopodobnie mam tylko elementarne tło, więc papier jest nad moją głową.

— Chao Xu,

5

n

$n$

(0, 1)

$(0, 1)$

n

$n$

n - 1

$n-1$

(0, 1)

$(0, 1)$

1

@Orient: Zadawaj pytania w osobnym poście i nie wykorzystuj w tym celu komentarzy.

— A.Schulz

8

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)$

(y_{i})_{1 \leq i \leq n} = \frac{\sum_{1 \dots i} x_{j}}{\sum_{1 \dots n} x_{j}}

$(y_i)_{1\leq i\leq n} = \frac{\sum \limits_{1\ldots i} x_j}{\sum \limits_{1\ldots n} x_j}$

O (n)

$O(n)$

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

— PKG
źródło

Jeśli podążę za odpowiedzią tutaj: stackoverflow.com/questions/2106503/... Następnie wygenerowanie liczby losowej z rozkładu wykładniczego obejmuje ocenę logarytmu, który może być nieco powolny.

— R zu

3

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.

— JeffE
źródło

5

To jest odpowiedź A. Schulza w kodzie bez wyjaśnienia, prawda?

— Raphael

1

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

— Alec
źródło

2

Sformatuj swoją odpowiedź w czytelny sposób: piszesz dla ludzi, a nie kompilatora bibtex. Ponadto, jeśli gazeta jest dostępna online, udostępnienie linku jest znacznie wydajniejsze.

— David Richerby,