Simule um dado justo com um dado tendencioso

18

Dado um dado tendencioso do lado , como um número aleatório no intervalo ser gerado uniformemente? A distribuição de probabilidade das faces do dado não é conhecida, tudo o que se sabe é que cada face tem uma probabilidade diferente de zero e que a distribuição de probabilidade é a mesma em todos os arremessos (em particular, os arremessos são independentes). Esta é a generalização óbvia dos resultados justos com dados injustos . $N$ $[1,N]$

Colocando isso em termos de ciência da computação, temos um oráculo representando os dados do dado: modo que seja diferente de zero e independente de . Nós estamos em busca de um algoritmo determinista que é parametrizada por (ou seja, pode fazer chamadas para ) de modo a que . O algoritmo deve terminar com a probabilidade 1, ou seja, a probabilidade de que faça mais de chamadas para deve convergir para como . $D : \mathbb{N} \to [1,N]$ $p_i = P(D(k)=i)$ $k$ $A$ $D$ $A$ $D$ $P(A()=i) = 1/N$ $A$ $n$ $D$ $0$ $n\to\infty$

Para (simule uma moeda justa a partir de lançamentos de moedas com uma moeda tendenciosa), existe um algoritmo bem conhecido: $N=2$

Repita “virar duas vezes” até que os dois lançamentos tenham resultados distintos ((cara, coroa) ou (coroa, cara)). Em outras palavras, faça um loop para até $k = 0..\infty$ $D(2k+1) \ne D(2k)$
Retorne 0 se o último par de flips foi (cara, coroa) e 1 se foi (coroa, cara). Em outras palavras, retorne que é o índice no qual o loop foi finalizado. $D(2k)$ $k$

Uma maneira simplista de fazer um dado imparcial a partir de um dado tendencioso é usar o método de não-oscilação da moeda para construir uma moeda justa e construir um dado justo com amostragem por rejeição, como em Desencadeamento de sequências . Mas isso é ideal (para valores genéricos da distribuição de probabilidade)?

Especificamente, minha pergunta é: o que é um algoritmo que requer o menor número esperado de chamadas para o oráculo ? Se o conjunto de valores esperados alcançáveis estiver aberto, qual é o limite inferior e qual é a classe de algoritmos que converge para esse limite inferior?

Caso diferentes famílias de algoritmos sejam ótimas para diferentes distribuições de probabilidade, vamos nos concentrar em dados quase justos: estou procurando um algoritmo ou uma família de algoritmos ideal para distribuições como para alguns . $\forall i, \bigl|p_i - 1/N\bigr| \lt \epsilon$ $\epsilon \gt 0$

probability-theory randomized-algorithms random-number-generator Gilles 'SO- parar de ser mau'
fonte

p_{1} = 1 - ϵ

$p_1 = 1-\epsilon$

p_{i} = ϵ / (N - 1)

$p_i = \epsilon/(N-1)$

i > 1

$i > 1$

max_{i} p_{i} \leq 1 - ϵ

$\max_i p_i \leq 1-\epsilon$

@usul Eu não entendo o seu comentário. Existem algoritmos mais eficientes para alguns valores de (por exemplo, se ), mas só estou solicitando algoritmos que não dependem de . Qual é o sentido de ?

p_{i}

$p_i$

\forall i, p_{i} = 1 / N

$\forall i, p_i = 1/N$

(p_{i})

$(p_i)$

ϵ

$\epsilon$

Gilles 'SO- stop be evil'

Como você mede a eficiência de um algoritmo que não depende de ? Provavelmente para qualquer algoritmo desse tipo, não há limite superior para o número esperado de chamadas necessárias, tomando meu exemplo de dado tendencioso com . É isso que quero dizer com "o supremo do ideal ... provavelmente não tem limites". Portanto, se todos os algoritmos podem exigir arbitrariamente muitas rolagens de dados em expectativa, como decidimos qual é o melhor?

(p_{i})

$(p_i)$

ϵ \to 0

$\epsilon \to 0$

usul

@usul Não há limite superior no número de lances, é claro, mas estou perguntando sobre o valor esperado (ou seja, o número médio de lances). Para uma determinada distribuição , o valor esperado para o algoritmo que cria uma moeda justa e o usa para a amostragem por rejeição é finito, não é? É verdade que a expectativa depende da distribuição; portanto, diferentes (famílias de) algoritmos podem ser ótimos para diferentes distribuições. Se for esse o caso, digamos que eu esteja interessado em dados quase justos.

(p_{i})

$(p_i)$

Gilles 'SO- stop being evil'

Não é exatamente exatamente a pergunta, mas você gostaria de procurar apenas um resultado que seja quase uniforme (em / distância total da variação)? Nesse caso, dependendo da garantia que você solicita da distribuição original, isso é estudado em um artigo recente (em envio), sob o nome "melhorador de amostragem para uniformidade" - que mostra em particular que você pode obter números de empates independentemente de para melhorar de distance para distance .

ℓ_{1}

$\ell_1$

N

$N$

ℓ_{1}

$\ell_1$

ε

$\varepsilon$

ε^{'}

$\varepsilon^\prime$

Clement C.

3

O artigo a seguir responde a uma variante próxima dessa questão: A construção eficiente de uma sequência aleatória imparcial, Elias 1972 .

A pergunta parece ser a seguinte: Dado acesso a essa fonte independente enviesada, imprima uma sequência de números aleatórios em (observe a diferença da sua pergunta na qual apenas um símbolo de saída é solicitado). À medida que o comprimento da saída desejada chega ao infinito, a "eficiência" do esquema no artigo (que parece uma generalização natural de von Neumann) passa para , significando, acredito, que uma entrada com entropia é convertida em uma saída de entropia se aproximando . $[1,N]$ $1$ $h$ $h$

A pergunta parece muito melhor comportada quando formulada dessa maneira, em vez de solicitar um único dígito de saída, porque, por exemplo, se extrairmos amostras e acabarmos com uma saída com muita informação (por exemplo, todos os símbolos de entrada são distintos) , podemos usar todas essas informações para produzir muitos símbolos de saída, enquanto que com a pergunta aqui formulada, qualquer informação além daquela usada para produzir um símbolo de saída é desperdiçada. $N$ $N$

Eu acredito que o esquema pega repetidamente draws, olha a sequência e mapeia algumas saídas ou a string vazia. Talvez exista uma maneira de melhorar o esquema da sua pergunta observando prefixos e parando se tivermos informações "suficientes" para gerar um símbolo? Eu não sei. $N$

usul
fonte

Eu não procurou trabalho posterior ou trabalhar citando o papel, então eu não sei, mas talvez alguém tenha melhorado o esquema, ofereceu outra, respondi a sua pergunta, etc.

usul

2

O método que você descreve para generaliza. Usamos que todas as permutações de são igualmente prováveis, mesmo com um dado inclinado (uma vez que os rolos são independentes). Portanto, podemos continuar rolando até vermos uma permutação como os últimos rolos e produzir o último rolo. $N=2$ $[1..N]$ $N$

Uma análise geral é complicada; é claro, no entanto, que o número esperado de rolagens cresce rapidamente em uma vez que a probabilidade de ver uma permutação em uma determinada etapa é pequena (e não é independente das etapas anteriores e posteriores, portanto complicadas). Ele é maior que para fixo , no entanto, portanto, o procedimento termina quase com certeza (ou seja, com probabilidade ). $N$ $0$ $N$ $1$

Para fixo , podemos construir uma cadeia de Markov sobre o conjunto de vetores Parikh que somam , resumindo os resultados dos últimos rolos e determinar o número esperado de etapas até alcançarmos pela primeira vez . Isso é suficiente, pois todas as permutações que compartilham um vetor Parikh são igualmente prováveis; as cadeias e cálculos são mais simples dessa maneira. $N$ $\leq N$ $N$ $(1,\dots,1)$

Assuma que estão em estado com . Então, a probabilidade de obter um elemento (ou seja, o próximo lançamento é ) é sempre dada por $v=(v_1,\dots,v_N)$ $\sum_{i=1}^n v_i \leq N$ $i$ $i$

$\qquad\displaystyle \operatorname{Pr}[\text{gain } i] = p_i$ .

Por outro lado, a propabilidade de retirar um elemento da história é dada por $i$

$\qquad\displaystyle \operatorname{Pr}_v[\text{drop } i] = \frac{v_i}{N}$

sempre que (e caso contrário) precisamente porque todas as permutações com o vetor Parikh são igualmente prováveis. Essas probabilidades são independentes (já que os rolos são independentes), para que possamos calcular as probabilidades de transição da seguinte maneira: $\sum_{i=1}^n v_i = N$ $0$ $v$

$\qquad\begin{align*} &\operatorname{Pr}[v \to (v_1,\dots,v_j + 1,\dots,v_N)] \\ &\qquad=\begin{cases} \operatorname{Pr}[\text{gain } j] &, \sum v < N \\ 0 &, \text{ else} \end{cases}\;,\\[3ex] &\operatorname{Pr}[v \to (v_1,\dots,v_i - 1, \dots v_j + 1,\dots,v_N)] \\ &\qquad=\begin{cases} 0 &, \sum v < N \lor v_i=0 \lor v_j=N \\ \operatorname{Pr}_v[\text{drop } i] \cdot \operatorname{Pr}[\text{gain } j] &, \text{ else} \end{cases}\;\text{ and}\\[3ex] &\operatorname{Pr}[v \to v] \\ &\qquad=\begin{cases} 0 &, \sum v < N \\ \sum_{v_i \neq 0} \operatorname{Pr}_v[\text{drop } i] \cdot \operatorname{Pr}[\text{gain } i] &, \text{ else} \end{cases}\;; \end{align*}$

todas as outras probabilidades de transição são zero. O único estado absorvente é , o vetor Parikh de todas as permutações de . $(1,\dots,1)$ $[1..N]$

Para a cadeia de Markov resultante¹ é $N=2$

Cadeia de Markov para N = 2
^{[ fonte ]}

com o número esperado de etapas até a absorção

$\qquad\displaystyle \mathbb{E}\,\text{steps} = 2 p_0 p_1 \cdot 2 + \sum_{i\geq 3} (p_0^{i-1}p_1 + p_1^{i-1}p_0)\cdot i = \frac{1 - p_0 + p_0^2}{p_0-p_0^2}\;,$

usando para simplificação que . Se agora, como sugerido, por alguns , então $p_1=1-p_0$ $p_0 = \frac{1}{2} \pm \epsilon$ $\epsilon \in [0,\frac{1}{2})$

$\qquad\displaystyle \mathbb{E}\,\text{steps} = \frac{3 + 4\epsilon^2}{1 - 4\epsilon^2}$ .

Para e distribuições uniformes (o melhor caso), realizei os cálculos com álgebra computacional²; como o espaço de estados explode rapidamente, é difícil avaliar valores maiores. Os resultados (arredondados para cima) são $N \leq 6$

NormalPlot LogPlot
^{Os gráficos mostram como uma função de ; à esquerda um gráfico regular e à direita um gráfico logarítmico. $\mathbb{E}\,\text{steps}$ $N$}

O crescimento parece ser exponencial, mas os valores são muito pequenos para fornecer boas estimativas.

Quanto à estabilidade contra perturbações do , podemos observar a situação para : $p_i$ $N=3$

Número esperado de etapas para N = 3 e opções diferentes
^{O gráfico mostra como uma função de e ; naturalmente, . $\mathbb{E}\,\text{steps}$ $p_0$ $p_1$ $p_2 = 1 - p_0 - p_1$}

Supondo imagens semelhantes para maior (o kernel trava computando resultados simbólicos mesmo para ), o número esperado de etapas parece ser bastante estável para todas as escolhas, exceto as mais extremas (quase todas ou nenhuma massa em algum ). $N$ $N=4$ $p_i$

Para comparação, a simulação de uma moeda com polarização (por exemplo, atribuindo os resultados do dado a e mais uniforme possível), usando-a para simular uma moeda justa e, finalmente, realizando amostragem por rejeição bit a bit, requer no máximo $\epsilon$ $0$ $1$

$\qquad\displaystyle 2\lceil \log N \rceil \cdot \frac{3 + 4\epsilon^2}{1 - 4\epsilon^2}$

rolos de morrer na expectativa - você provavelmente deve ficar com isso.

Como a corrente está absorvendo as arestas com a indicação cinza nunca são atravessadas e não influenciam os cálculos. Eu os incluo apenas para fins completos e ilustrativos. $(11)$
Implementação no Mathematica 10 ( Notebook , Bare Source ); desculpe, é o que eu sei sobre esses tipos de problemas.

Rafael
fonte

1

Apenas um comentário rápido sobre o caso . Pegue um número grande e experimente jogadas do dado. Se você tiver cabeças, poderá extrair bits. Supondo que o dado é inclinado, a quantidade média de informação é Para obter essa estimativa, use o fato de que a variável binomial está concentrada em torno de juntamente com a estimativa . À medida que aumenta, obtemos a taxa ideal de $N = 2$ $m$ $m$ $k$ $\log \binom{m}{k}$ $p$

\sum_{k = 0}^{m} p^{k} (1 - p)^{m - k} (\binom{m}{k}) \log (\binom{m}{k}) \approx m h (p) .

$\sum_{k=0}^m p^k (1-p)^{m-k} \binom{m}{k} \log \binom{m}{k} \approx m h(p).$

k = p m

$k = pm$

\log (\binom{m}{k}) \approx m h (k / m)

$\log \binom{m}{k} \approx mh(k/m)$

m

$m$

h (p)

$h(p)$ por lançamento de moeda (isso é ideal por razões teóricas da informação, por exemplo, a propriedade de equipartição assintótica).

Você pode usar o mesmo método para geral e provavelmente obterá o mesmo . Esses algoritmos são ótimos apenas no limite e pode haver algoritmos que atingem o limite mais rapidamente que estes. Na verdade, eu esqueci de calcular a velocidade da convergência - pode ser um exercício interessante. $N$ $H(\vec{p})$

Yuval Filmus
fonte

1

Eu arriscaria a seguinte resposta.

O caso específico de 2 que você mencionou acima é o caso específico de expansão (onde é prob de cabeça e prob de cauda), que fornece um termo Isso significa que você pode obter para um caso e para o outro caso. Você precisará repetir a amostragem até ver ou (cabeça-cauda ou cauda-cabeça). Usando-as como simulação, você dará a mesma probabilidade. $(p + q)^2$ $p$ $q$ $2pq$ $pq$ $qp$ $pq$ $qp$

Quando você tem a expansão que fornece o termo . Nesse caso, você faz a mesma coisa, amostrando até ver todos os três resultados , , em alguma ordem em três tentativas consecutivas. $N=3$ $(p + q + r)^3$ $pqr$ $q$ $p$ $r$

O mesmo se aplica ao caso geral. Pensando com cuidado, devo dizer que o caso 2 é o melhor caso em que se pode resolver as coisas na expansão. Quando existem 6 sequências diferentes para e existem muitos outros termos na expansão. Eu me sentiria bastante desconfortável com outros termos em que existem muitos outros resultados. $N=3$ $pqr$

.

Extra:

Isso me faz pensar na idéia de simplesmente amostrar muito para estimar a probabilidade de cada resultado dos dados. Neste caso mais simples de um modelo de camada sem camada oculta (um modelo conhecido), podemos elaborar um limite para concluir que a estimativa converge rapidamente. De fato, o limite de Chernoff nos mostra que o erro diminui exponencialmente à medida que a amostragem aumenta (linearmente).

Agora que uma boa estimativa das probabilidades para cada lado dos dados é conhecida, há muitas opções. Uma opção é que podemos fazer a expansão acima novamente, mas desta vez podemos usar muitos outros termos na expansão que tenham o mesmo valor que (ou qualquer termo que você usa como sequência baseada). Isso será um pouco mais eficiente, porque mais termos na expansão serão usados. Mas admito que não sei se isso resultará no menor número de chamadas ao oráculo para garantir quaisquer condições prévias (como o parâmetro de confiança), se forem fornecidas. $\prod_{i=1}^{i=n} p_i$

No entanto, essa abordagem é uma resposta para diferentes sabores da pergunta. A questão pede garantia de imparcialidade perfeita e garantida, ao custo de amostragens potencialmente grandes (embora com baixa probabilidade). Essa abordagem usa apenas amostragem finita com parâmetro ligado à confiança. Portanto, não acho que essa abordagem seja apropriada para essa pergunta, embora seja muito interessante.

InformedA
fonte

Simule um dado justo com um dado tendencioso

Respostas:

Extra: