Gerando uniforme discreto a partir de lançamentos de moedas

Suponha que você tenha uma moeda justa que possa ser lançada quantas vezes quiser (possivelmente infinita). É possível gerar a distribuição uniforme discreta em , onde NÃO é uma potência de 2? Como você faria? $(1,2,...,k)$ $k$

Se isso for muito geral, responder provavelmente seria interessante o suficiente. $k=3$

random-generation uniform renrenthehamster
fonte

Certo! E o caso

é realmente instrutivo. Pense em jogar moedas em pares (repetidamente, conforme necessário). Quais são os possíveis resultados? Agora, você pode mapear os resultados dos resultados deste procedimento para obter a distribuição desejada?

k = 3

$k=3$

cardeal

Oh, certo. Isso é bom. Por exemplo, HH = 1, HT = 2, TH = 3 e TT = refletem os pares. Hohoho, agora eu estou pensando sobre entropia do coin flips e como a informação de flips pode ser maximizada (: Mas eu vou fazer isso sozinha!

renrenthehamster

Aqui está um ótimo artigo com o código psuedo para exatamente o que você deseja fazer: arxiv.org/pdf/1304.1916v1.pdf

@renrenthehamster: Sim, é

porque, se definimos "sucesso" como a obtenção de um resultado válido a partir do

vira, então a probabilidade de sucesso é sempre

. Assim, o número de tais tentativas é geométrico com uma média menor ou igual a 2. Além disso, a probabilidade de precisar de mais que

tentativas diminui exponencialmente.

O (\log_{2} k)

$O(\log_2 k)$

\log_{2} k

$\log_2 k$

\geq 1 / 2

$\geq 1/2$

m

$m$

cardeal

@ren: considere formular uma resposta com base em sua descoberta. Eu, por exemplo, ficarei feliz em votar. Felicidades. :-)

cardeal

Respostas:

Como eu disse acima em meus comentários, o artigo http://arxiv.org/pdf/1304.1916v1.pdf , detalha exatamente como gerar a partir da distribuição uniforme e discreta de lançamentos de moedas e fornece uma seção muito detalhada de provas e resultados de por que o método funciona.

Como prova de conceito, codifiquei seu pseudo-código Rpara mostrar quão rápido, simples e eficiente é o método deles.

#Function for sampling from a discrete uniform distribution
rdunif = function(n){

v = 1 
c = 0
a = 0
while(a > -1){
    v = 2*v
    c = 2*c + rbinom(1,1,.5) #This is the dice roll part

    if(v >= n){
        if(c < n){
            return(c)
        }else{
            v = v-n
            c = c-n
        }
    }
}
}

#Running the function k times for n = 11
n = 11
k = 10000
random.samples = rep(NA,k)

for(i in 1:k){
    random.samples[i] = rdunif(n)
}

counts = table(random.samples)
barplot(counts,main="Random Samples from a Discrete Uniform(0,10)")

insira a descrição da imagem aqui

fonte