Amostragem uniforme de um simplex

29

Estou procurando um algoritmo para gerar uma matriz de N números aleatórios, de modo que a soma dos N números seja 1 e todos os números estejam entre 0 e 1. Por exemplo, N = 3, o ponto aleatório (x, y, z) deve estar dentro do triângulo:

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

Idealmente, quero que cada ponto dentro da área tenha igual probabilidade. Se for muito difícil, posso cancelar o requisito. Obrigado.

algorithms randomness random-number-generator sampling Ruofeng
fonte

Qual é a distribuição de destino? O que você tentou?

Raphael

3

Observe que sempre há uma amostra de rejeição : faça uma amostra de

números uniformes e rejeite se os números não somarem

. Aqui, o número esperado de iterações é desconfortavelmente alto, portanto, você deve fazer outra coisa.

n

$n$

1

$1$

Raphael

28

Vamos primeiro assumir que você deseja provar dentro de

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

Isso não faz muita diferença, pois o ponto de amostra ainda estará na área solicitada com alta probabilidade.

Agora você fica com a amostragem de um ponto a partir de um simplex . No exemplo 3d, você obtém um 2d simplex (triângulo) realizado em 3d.

Como escolher um ponto uniformemente aleatoriamente foi discutido neste post do blog (veja os comentários).

$n-1$ $(0,1)$ $0$ $1$ $n+1$ $n$ $1$

$n=4$ 0.4 0.2 0.10 0.1 0.2 0.4 10.1 0.1 0.2 0.6

x+y+z=1 $d$ $d-1$ . Portanto, se você fizer uma amostragem uniforme do hipercubo, isso não fornecerá uma amostra uniforme no simplex. No entanto, se você fizer uma amostra do hipercubo com uma distribuição exponencial apropriada, esse efeito será cancelado. A Figura fornece uma idéia de como os dois métodos serão amostrados. No entanto, prefiro o método de "classificação" devido à sua forma simples. Também é mais fácil de implementar.

Exemplo dos 2 métodos de amostragem

A.Schulz
fonte

n

$n$

(0, 1)

$(0,1)$

Abordei sua pergunta na resposta estendida.

A.Schulz

11

Existe uma prova simples que mostre que a classificação dá uma distribuição uniforme? Eu tenho apenas antecedentes elementares em probabilidade, portanto o papel está acima da minha cabeça.

Chao Xu

5

n

$n$

(0, 1)

$(0, 1)$

n

$n$

n - 1

$n-1$

(0, 1)

$(0, 1)$

11

@Orient: Por favor, faça perguntas em um post separado e não abuse dos comentários.

A.Schulz

8

Isso é para adicionar às respostas existentes.

Devroye é uma excelente referência para perguntas desse tipo. A Cap.7 fornece os algoritmos necessários para gerar estatísticas uniformes de ordem, das quais o OP está atrás.

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

Se eu seguir a resposta aqui: stackoverflow.com/questions/2106503/… A geração de números aleatórios a partir da distribuição exponencial envolve a avaliação do logaritmo, que pode ser um pouco lento.

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]

Aqui, uniform(0,1)retorna um número real independentemente e uniformemente distribuído entre 0 e 1.

JeffE
fonte

5

Esta é a resposta de A. Schulz em código sem a explicação, certo?

Raphael

1

Veja este artigo : Smith, N. e Tromble, R., Amostragem uniformemente a partir da unidade simplex .

Alec
fonte

2

Formate sua resposta de forma legível: você está escrevendo para seres humanos, não para o compilador bibtex. Além disso, se o documento estiver disponível online, é muito mais eficiente fornecer um link.

David Richerby

Amostragem uniforme de um simplex

Respostas: