Gleichmäßige Probenahme aus einem Simplex

29

Ich suche nach einem Algorithmus zum Erzeugen eines Arrays von N Zufallszahlen, so dass die Summe der N Zahlen 1 ist und alle Zahlen innerhalb von 0 und 1 liegen. Zum Beispiel ist N = 3, der Zufallspunkt (x, y, z) sollte im Dreieck liegen:

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

Idealerweise möchte ich, dass jeder Punkt innerhalb des Gebiets die gleiche Wahrscheinlichkeit hat. Wenn es zu schwer ist, kann ich die Anforderung fallen lassen. Vielen Dank.

algorithms randomness random-number-generator sampling Ruofeng
quelle

Was ist die Zielverteilung? Was hast du versucht?

Raphael

3

Beachten Sie, dass es immer Ablehnungsstichproben gibt : Nehmen Sie Stichproben mit

einheitlichen Zahlen und lehnen Sie ab, wenn die Zahlen nicht

. Hier ist die erwartete Anzahl von Iterationen unangenehm hoch, daher sollten Sie etwas anderes tun.

n

$n$

1

$1$

Raphael

28

Nehmen wir zunächst an, dass Sie innerhalb probieren möchten

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

Dies macht keinen großen Unterschied, da der Abtastpunkt mit hoher Wahrscheinlichkeit immer noch in Ihrem gewünschten Bereich liegt.

Jetzt müssen Sie einen Punkt von einem Simplex abtasten . Im 3D-Beispiel erhalten Sie ein 2D-Simplex (Dreieck), das in 3D realisiert wurde.

Wie man einen Punkt gleichmäßig zufällig auswählt, wurde in diesem Blog-Beitrag besprochen (siehe die Kommentare).

Für Ihr Problem würde dies bedeuten, dass Sie Zufallszahlen aus dem Intervall und dann und addieren , um eine Liste mit Zahlen zu erhalten. Sie sortieren die Liste und zeichnen dann die Unterschiede zwischen zwei aufeinander folgenden Elementen auf. Dies gibt Ihnen eine Liste mit Zahlen, die sich zu summieren . Darüber hinaus ist diese Abtastung einheitlich. Diese Idee findet sich in Donald B. Rubin, The Bayesian Bootstrap Ann. Statist. 9, 1981, 130-134. $n-1$ $(0,1)$ $0$ $1$ $n+1$ $n$ $1$

Zum Beispiel ( ) haben Sie die drei Zufallszahlen, dann erhalten Sie die sortierte Folge und dies ergibt die Differenzen , und durch Konstruktion summieren sich diese vier Zahlen zu 1. $n=4$ 0.4 0.2 0.10 0.1 0.2 0.4 10.1 0.1 0.2 0.6

Ein anderer Ansatz ist der folgende: Zuerst wird aus dem Hypercube ein Sample erstellt (das ist alles, was Sie vergessen haben x+y+z=1) und dann wird der Sample-Punkt normalisiert. Die Normalisierung ist eine Projektion aus der -hypercube auf die Simplex. Es sollte intuitiv klar sein, dass die Punkte in der Mitte des Simplex mehr "Vorbildpunkte" haben als an der Außenseite $d$ $d-1$ . Wenn Sie also gleichmäßig aus dem Hypercube abtasten, erhalten Sie auf diese Weise keine gleichmäßige Abtastung im Simplex. Wenn Sie jedoch eine Stichprobe aus dem Hypercube mit einer geeigneten Exponentialverteilung erstellen, wird dieser Effekt aufgehoben. Die Abbildung gibt Ihnen eine Vorstellung davon, wie beide Methoden abtasten. Ich bevorzuge jedoch die "Sortier" -Methode aufgrund ihrer einfachen Form. Es ist auch einfacher zu implementieren.

Beispiel der 2 Probenahmemethoden

A.Schulz
quelle

n

$n$

(0, 1)

$(0,1)$

Ich habe Ihre Frage in der erweiterten Antwort angesprochen.

A.Schulz

1

Gibt es einen einfachen Beweis dafür, dass die Sortierung eine gleichmäßige Verteilung ergibt? Ich habe nur einen elementaren Hintergrund in der Wahrscheinlichkeit, also ist das Papier über meinem Kopf.

Chao Xu

5

n

$n$

(0, 1)

$(0, 1)$

n

$n$

n - 1

$n-1$

(0, 1)

$(0, 1)$

1

@Orient: Bitte stellen Sie Ihre Fragen in einem separaten Beitrag und missbrauchen Sie die Kommentare dazu nicht.

A.Schulz

8

Dies dient dazu, die vorhandenen Antworten zu ergänzen.

Devroye ist eine hervorragende Referenz für Fragen dieser Art. In Kapitel 7 sind die Algorithmen aufgeführt, die für die Erstellung einer einheitlichen Auftragsstatistik erforderlich sind, nach der das OP sucht.

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

Wenn ich die Antwort hier befolge : stackoverflow.com/questions/2106503/…. Das Erzeugen einer Zufallszahl aus einer Exponentialverteilung beinhaltet das Auswerten des Logarithmus, der etwas langsam sein kann.

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]

Hier uniform(0,1)gibt eine reelle Zahl unabhängig und gleichmäßig verteilt zwischen 0 und 1.

JeffE
quelle

5

Dies ist die Antwort von A. Schulz im Code ohne Erklärung, oder?

Raphael

1

Siehe dieses Papier : Smith, N. und Tromble, R., Probenahme gleichmäßig von der Einheit Simplex .

Alec
quelle

2

Bitte formatieren Sie Ihre Antwort lesbar: Sie schreiben für Menschen, nicht für den bibtex-Compiler. Wenn das Papier online verfügbar ist, ist es für Sie außerdem effizienter, einen Link bereitzustellen.

David Richerby

Gleichmäßige Probenahme aus einem Simplex

Antworten: