Diskrete Uniform aus Münzwürfen erzeugen

Angenommen, Sie haben eine faire Münze, die Sie so oft werfen können, wie Sie möchten (möglicherweise zählbar unendlich). Ist es möglich, die diskrete Gleichverteilung auf zu erzeugen , wobei KEINE Potenz von 2 ist? Wie würdest du es machen? $(1,2,...,k)$ $k$

Wenn dies zu allgemein ist, wäre die Beantwortung von wahrscheinlich interessant genug. $k=3$

random-generation uniform Renrenthehamster
quelle

Sicher! Und der Fall ist tatsächlich aufschlussreich. Denken Sie daran, Münzen paarweise zu werfen (bei Bedarf wiederholt). Was sind die möglichen Ergebnisse? Können Sie nun die Ergebnisse der Ergebnisse dieses Verfahrens so abbilden, dass die gewünschte Verteilung erzielt wird?

k = 3

$k=3$

Kardinal

Oh, richtig. Das ist schön. Zum Beispiel ist HH = 1, HT = 2, TH = 3 und TT = Reflip der Paare. Hohoho, jetzt denke ich über die Entropie der Münzwürfe nach und wie die Informationen aus den Münzwürfen maximiert werden können (: Aber das mache ich selbst!

renrenthehamster

Hier ist ein großartiges Papier mit Pseudo-Code für genau das, was Sie tun möchten: arxiv.org/pdf/1304.1916v1.pdf

@renrenthehamster: Ja, es ist denn wenn wir "Erfolg" als Erhalt eines gültigen Ergebnisses aus den Flips definieren, ist die Erfolgswahrscheinlichkeit immer . Die Anzahl solcher Versuche ist also geometrisch mit einem Mittelwert kleiner oder gleich 2. Außerdem nimmt die Wahrscheinlichkeit, mehr als solcher Versuche zu benötigen, exponentiell ab.

O (\log_{2} k)

$O(\log_2 k)$

\log_{2} k

$\log_2 k$

\geq 1 / 2

$\geq 1/2$

m

$m$

Kardinal

@ren: Bitte überlegen Sie, eine Antwort basierend auf Ihrer Entdeckung zu formulieren. Zum einen werde ich gerne positiv stimmen. Prost. :-)

Kardinal

Antworten:

Wie ich oben in meinen Kommentaren sagte, beschreibt das Papier http://arxiv.org/pdf/1304.1916v1.pdf genau, wie aus der diskreten gleichmäßigen Verteilung von Münzwürfen generiert werden kann, und gibt einen sehr detaillierten Beweis- und Ergebnisabschnitt darüber, warum die Methode funktioniert.

Als Proof of Concept habe ich ihren Pseudocode codiert, um Rzu zeigen, wie schnell, einfach und effizient ihre Methode ist.

#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)")

Geben Sie hier die Bildbeschreibung ein

quelle