Rätsel: Wie man mit einer voreingenommenen Münze mit einem pr (Kopf) = p 7 ganze Zahlen mit gleicher Wahrscheinlichkeit erzeugt?

58

Dies ist eine Frage, die ich bei Glassdoor gefunden habe : Wie erzeugt man mit einer Münze mit einem 7 Ganzzahlen mit gleicher Wahrscheinlichkeit ?Pr(Head)=p(0,1)

Grundsätzlich haben Sie eine Münze, die fair sein kann oder nicht, und dies ist der einzige Zufallsgenerierungsprozess, den Sie haben. Aus diesem Grund haben Sie einen Zufallsgenerator, der Ganzzahlen von 1 bis 7 ausgibt, bei denen die Wahrscheinlichkeit besteht, jede dieser Ganzzahlen zu erhalten ist 1/7.

Die Effizienz der Daten erzeugt Prozessangelegenheiten.

Amazonisch
quelle
Verbunden, nicht betrogen: stats.stackexchange.com/questions/256563/…
Monica
12
Es gibt unzählige Möglichkeiten, dies zu erreichen. In einer interessanteren Version der Frage wird nach der besten Methode in einem genau definierten Sinne gefragt . Ein natürlicher Sinn für das Beste wäre die am wenigsten erwartete Anzahl von Flips pro erzeugter Ganzzahl. Eine andere interessante Version ist die Beschreibung aller möglichen Lösungen (die auf unabhängigen Münzwürfen beruhen und nicht mehr).
Whuber
1
@whuber guter Vorschlag, ich habe die Frage bearbeitet, um Ihren Kommentar widerzuspiegeln.
Amazonian
<<< Grundsätzlich haben Sie eine Münze, die fair sein kann oder nicht, und dies ist der einzige Zufallsgenerierungsprozess, den Sie haben Schwanz ist "verboten", da es ein anderer Zufallsgenerierungsprozess wäre?
TinglTanglBob
9
Mod 7 des Jahres auf der Münze.
Nat

Antworten:

56

Wirf die Münze zweimal um. Wenn es landet HHoder TT, ignoriere es und drehe es noch zweimal um.

Nun hat die Münze die gleiche Wahrscheinlichkeit aufzutauchen HToder TH. Wenn es auftaucht HT, ruf das an H1. Wenn es auftaucht TH, ruf das an T1.

Erhalten Sie weiter H1oder T1bis Sie drei in einer Reihe haben. Diese drei Ergebnisse geben Ihnen eine Zahl basierend auf der folgenden Tabelle:

H1 H1 H1 -> 1
H1 H1 T1 -> 2
H1 T1 H1 -> 3
H1 T1 T1 -> 4
T1 H1 H1 -> 5
T1 H1 T1 -> 6
T1 T1 H1 -> 7
T1 T1 T1 -> [Throw out all results so far and repeat]

Ich behaupte, dass dies perfekt funktionieren würde, obwohl Sie dabei eine Menge vergeudeter Würfe hätten!

NcAdams
quelle
4
Die einzige Einschränkung ist, dass die Wahrscheinlichkeit von Köpfen "p" ist. Beachten Sie, dass p oder . Es ist also nicht garantiert, dass dies funktioniert, aber Sycorax (oder Sephan's) würde auch in diesen Fällen funktionieren. 101
gung - Reinstate Monica
8
@gung: Ich bin mir nicht sicher, ob ich für eine Münze mit zwei Köpfen oder zwei Schwänzen arbeiten würde.
S. Kolassa - Reinstate Monica
6
Mit Wahrscheinlichkeit endet es in endlicher Zeit. 1
Clark
18
Dies nennt man Von-Neuman-Bleaching.
DonFusili
4
Sie können den von Neumann-Extraktor iterieren, um die Entropie aus der Sequenz vollständiger zu extrahieren. Sammeln Sie alle HH- und TT-Paare, denken Sie an eine Sequenz, wenden Sie den von Neumann-Extraktor darauf an usw.
A Simmons
47

Angenommen, .p(0,1)

Schritt 1: . Wirf die Münze 5 Mal.

Wenn das Ergebnis ist

1(H,H,H,T,T) , geben Sie und halten Sie an.1

2(H,H,T,T,H) , kehre zu und halte an.2

3(H,T,T,H,H) , kehre zu und halte an.3

4(T,T,H,H,H) , kehre zu und halte an.4

(T,H,H,H,T) , kehren Sie zu und halten Sie an.5

(H,H,T,H,T) , kehren Sie zu und halten Sie an.6

7(H,T,H,T,H) , kehren Sie zu und halten Sie an.7

Schritt 2: . Wenn das Ergebnis keines der oben genannten ist, wiederholen Sie Schritt 1.

Es ist zu beachten, dass unabhängig vom Wert von jedes der oben aufgeführten sieben Ergebnisse eine Wahrscheinlichkeit und die erwartete Anzahl von Münzwürfen . Der Toster muss den Wert von nicht kennen (außer dass und ); Es ist garantiert, dass die sieben ganzen Zahlen bei Beendigung des Experiments mit gleicher Wahrscheinlichkeit zurückgegeben werden (und es ist garantiert, dass es mit Wahrscheinlichkeit endet ).q = p 3 ( 1 - p ) 2p(0,1)q=p3(1p)2 pp0p1157qpp0p11

Dilip Sarwate
quelle
6
Können wir die erwartete Anzahl von Würfen dafür reduzieren, indem wir entweder die hier angegebene Sequenz oder diese Sequenz mit jedem invertierten Flip zulassen? zB: Für 1 entweder (H, H, H, T, T) oder (T, T, T, H, H)?
Mehron
5
Sie können auch die Ergänzung hinzufügen. Wenn das Ergebnis (H, H, H, T, T) oder (T, T, T, H, H) ist, geben Sie 1 zurück und stoppen Sie usw. In diesem Fall ist die Wahrscheinlichkeit für jedes Ergebnis . q=p3(1p)2+p2(1p)3
Sextus Empiricus
2
Wäre es nicht möglich, einfach einen weiteren Münzwurf hinzuzufügen, wenn das Ergebnis keine (H, H, H, T, T) -Anordnung enthält? Mit dem zusätzlichen Münzwurf benötigen Sie eine weitere Zuordnung von (H, H, H, T, T, T) und (H, H, T, T, T, T) und jeder xT (7-x) H-Kombination das kann in 7 oder mehr verschiedenen Reihenfolgen zu den Nummern 1 bis 7 angeordnet werden. Anstatt alle 5 Münzen zurückzuwerfen, würde dies nur 1 zusätzlichen Wurf hinzufügen, aber
ich bin
5
Vielleicht ist es das Beste, die Münze sofort siebenmal zu werfen, da dann garantiert wird, dass Sie eine Zufallszahl daraus erhalten (einzige Ausnahme ist daher, dass die Münze alle sieben Versuche mit dem Kopf nach oben oder mit dem Schwanz nach oben landet). . Also mit 7 Würfen könnten Sie mit 1 bis 6 Köpfen enden (ich schließe die 0 und 7 Option hier aus, da es sinnlos ist). Bei einem Kopf sind 7 verschiedene Anordnungen von (H, T, T, T, T, T, T) möglich; Wenn 2 Köpfe seine 21; Wenn 3 Köpfe, sind es 35; wenn 4 35 Köpfe; wenn 5 21 Köpfe; wenn 6 7 Köpfe; Jedes kann perfekt auf Nummer 1-7 abgebildet werden, ohne dass eine Kombination verloren geht.
TinglTanglBob
2
@TinglTanglBob Dies ist im Wesentlichen Martijn Weterings Antwort ;-)
M.Herzkamp
22

Verallgemeinerung des von Dilip Sarwate beschriebenen Falls

Einige der in den anderen Antworten beschriebenen Methoden verwenden ein Schema, in dem Sie eine Folge von n Münzen in einer "Runde" und je nach Ergebnis eine Zahl zwischen 1 oder 7 wählen oder die Runde verwerfen und erneut werfen.

Der Trick besteht darin, bei der Erweiterung der Möglichkeiten ein Vielfaches von 7 Ergebnissen mit der gleichen Wahrscheinlichkeit pk(1p)nk und diese gegeneinander abzugleichen.

Da es sich bei der Gesamtzahl der Ergebnisse nicht um ein Vielfaches von 7 handelt, haben wir einige Ergebnisse, die wir keiner Zahl zuordnen können, und es besteht eine gewisse Wahrscheinlichkeit, dass wir die Ergebnisse verwerfen und neu beginnen müssen.


Der Fall der Verwendung von 7 Münzwürfen pro Umdrehung

Intuitiv könnte man sagen, dass es sehr interessant wäre, sieben Mal zu würfeln. Da müssen wir nur 2 von den 27 Möglichkeiten rausschmeißen. Das heißt, die 7-fachen Köpfe und die 0-fachen Köpfe.

Für alle anderen 272 Möglichkeiten gibt es immer ein Vielfaches von 7 Fällen mit der gleichen Anzahl von Köpfen. Nämlich 7 Fälle mit 1 Kopf, 21 Fälle mit 2 Köpfen, 35 Fälle mit 3 Köpfen, 35 Fälle mit 4 Köpfen, 21 Fälle mit 5 Köpfen und 7 Fälle mit 6 Köpfen.

Wenn Sie also die Zahl berechnen (0 Köpfe und 7 Köpfe verwerfen), ist

X=k=17(k1)Ck

mit Ck Bernoulli verteilten Variablen (Wert 0 oder 1) ist X modulo 7 eine einheitliche Variable mit sieben möglichen Ergebnissen.


Vergleich der Anzahl der Münzwürfe pro Spielzug

Es bleibt die Frage, wie viele Rollen pro Umdrehung optimal sind. Das Werfen von mehr Würfeln pro Spielzug kostet Sie mehr, aber Sie verringern die Wahrscheinlichkeit, dass Sie erneut würfeln müssen.

Das Bild unten zeigt eine manuelle Berechnung für die ersten paar Münzwürfe pro Umdrehung. (Möglicherweise gibt es eine analytische Lösung, aber ich glaube, es ist sicher zu sagen, dass ein System mit 7 Münzwürfen die beste Methode hinsichtlich des Erwartungswerts für die erforderliche Anzahl von Münzwürfen darstellt.)

erwartete Anzahl der Münzwürfe

# plot an empty canvas
plot(-100,-100,
     xlab="flips per turn",
     ylab="E(total flips)",
     ylim=c(7,400),xlim=c(0,20),log="y")
title("expectation value for total number of coin flips
(number of turns times flips per turn)")

# loop 1
# different values p from fair to very unfair 
# since this is symmetric only from 0 to 0.5 is necessary 

# loop 2
# different values for number of flips per turn
# we can only use a multiple of 7 to assign 
#   so the modulus will have to be discarded
#   from this we can calculate the probability that the turn succeeds
#   the expected number of flips is 
#       the flips per turn 
#             divided by 
#       the probability for the turn to succeed 

for (p in c(0.5,0.2,0.1,0.05)) {
  Ecoins <- rep(0,16)
  for (dr in (5:20)){
    Pdiscards = 0
    for (i in c(0:dr)) { 
      Pdiscards = Pdiscards + p^(i)*(1-p)^(dr-i) * (choose(dr,i) %% 7)
    }
    Ecoins[dr-4] = dr/(1-Pdiscards)
  }
  lines(5:20, Ecoins)
  points(5:20, Ecoins, pch=21, col="black", bg="white", cex=0.5)
  text(5, Ecoins[1], paste0("p = ",p), pos=2)
}

Verwenden einer Regel zum vorzeitigen Anhalten

Hinweis: Die folgenden Berechnungen für den Erwartungswert der Anzahl der Flips beziehen sich auf eine faire Münze p=0.5 . Es wäre ein Durcheinander, dies für ein anderes p zu tun , aber das Prinzip bleibt dasselbe (obwohl unterschiedliche Buchführung des Fälle werden benötigt)

X

  • Mit 5 Münzwürfen haben wir für die sechs möglichen ungeordneten Sätze Kopf und Zahl:

    1 + 5 + 10 + 10 + 5 + 1 bestellte Sätze

    Und wir können die Gruppen mit zehn Fällen (das ist die Gruppe mit zwei Köpfen oder die Gruppe mit zwei Schwänzen) verwenden, um (mit gleicher Wahrscheinlichkeit) eine Zahl zu wählen. Dies tritt in 14 von 2 ^ 5 = 32 Fällen auf. Dies lässt uns mit:

    1 + 5 + 3 + 3 + 5 + 1 bestellte Sätze

  • Mit einem zusätzlichen (6.) Münzwurf haben wir für die sieben möglichen ungeordneten Sätze von Kopf und Zahl:

    1 + 6 + 8 + 6 + 8 + 6 + 1 bestellte Sätze

    Und wir können die Gruppen mit acht Fällen (das ist die Gruppe mit drei Köpfen oder die Gruppe mit drei Schwänzen) verwenden, um (mit gleicher Wahrscheinlichkeit) eine Zahl zu wählen. Dies tritt in 14 von 2 * (2 ^ 5-14) = 36 Fällen auf. Dies lässt uns mit:

    1 + 6 + 1 + 6 + 1 + 6 + 1 bestellte Sätze

  • Mit einem weiteren (7.) zusätzlichen Münzwurf haben wir für die acht möglichen ungeordneten Sätze von Kopf und Zahl:

    1 + 7 + 7 + 7 + 7 + 7 + 7 + 1 bestellte Sätze

    Und wir können die Gruppen mit sieben Fällen (alle mit Ausnahme der Fälle mit allen Schwänzen und allen Köpfen) verwenden, um (mit gleicher Wahrscheinlichkeit) eine Zahl zu wählen. Dies kommt in 42 von 44 Fällen vor. Dies lässt uns mit:

    1 + 0 + 0 + 0 + 0 + 0 + 0 + 1 geordnete Sätze

    (Wir könnten dies fortsetzen, aber nur im 49. Schritt verschafft uns dies einen Vorteil.)

Also die wahrscheinlichkeit eine nummer zu wählen

  • 1432=716
  • 9161436=732
  • 11324244=231704
  • 1716732231704=227

Dies macht den Erwartungswert für die Anzahl der Flips in einer Runde von Erfolg und p = 0,5 abhängig:

5716+6732+7231704=5.796875

Der Erwartungswert für die Gesamtzahl der Flips (bis ein Erfolg vorliegt), unter der Bedingung, dass p = 0,5, wird zu:

(5716+6732+7231704)27272=539=5.88889


Die Antwort von NcAdams basiert auf einer Variante dieser Stoppregelstrategie (jedes Mal mit zwei neuen Münzwürfen), wählt jedoch nicht alle Würfe optimal aus.

Die Antwort von Clid könnte auch ähnlich sein, obwohl es eine ungerade Auswahlregel geben könnte, dass bei jedem zweiten Münzwurf eine Zahl gewählt werden könnte, jedoch nicht unbedingt mit gleicher Wahrscheinlichkeit (eine Diskrepanz, die während späterer Münzwürfe repariert wird).


Vergleich mit anderen Methoden

Andere Methoden, die ein ähnliches Prinzip verwenden, sind die von NcAdams und AdamO.

xij

x

Dies wird durch das folgende Bild und die Simulation demonstriert:

Vergleich

#### mathematical part #####
set.seed(1)


#plotting this method
p <- seq(0.001,0.999,0.001)
tot <- (5*7*(p^2*(1-p)^3+p^3*(1-p)^2)+
       6*7*(p^2*(1-p)^4+p^4*(1-p)^2)+
       7*7*(p^1*(1-p)^6+p^2*(1-p)^5+p^3*(1-p)^4+p^4*(1-p)^3+p^5*(1-p)^2+p^6*(1-p)^1)+
        7*1*(0+p^7+(1-p)^7) )/
             (1-p^7-(1-p)^7)
plot(p,tot,type="l",log="y",
     xlab="p",
     ylab="expactation value number of flips"
     )

#plotting method by AdamO
tot <- (7*(p^20-20*p^19+189*p^18-1121*p^17+4674*p^16-14536*p^15+34900*p^14-66014*p^13+99426*p^12-119573*p^11+114257*p^10-85514*p^9+48750*p^8-20100*p^7+5400*p^6-720*p^5)+6*
          (-7*p^21+140*p^20-1323*p^19+7847*p^18-32718*p^17+101752*p^16-244307*p^15+462196*p^14-696612*p^13+839468*p^12-806260*p^11+610617*p^10-357343*p^9+156100*p^8-47950*p^7+9240*p^6-840*p^5)+5*
          (21*p^22-420*p^21+3969*p^20-23541*p^19+98154*p^18-305277*p^17+733257*p^16-1389066*p^15+2100987*p^14-2552529*p^13+2493624*p^12-1952475*p^11+1215900*p^10-594216*p^9+222600*p^8-61068*p^7+11088*p^6-1008*p^5)+4*(-
          35*p^23+700*p^22-6615*p^21+39235*p^20-163625*p^19+509425*p^18-1227345*p^17+2341955*p^16-3595725*p^15+4493195*p^14-4609675*p^13+3907820*p^12-2745610*p^11+1592640*p^10-750855*p^9+278250*p^8-76335*p^7+13860*p^6-
          1260*p^5)+3*(35*p^24-700*p^23+6615*p^22-39270*p^21+164325*p^20-515935*p^19+1264725*p^18-2490320*p^17+4027555*p^16-5447470*p^15+6245645*p^14-6113275*p^13+5102720*p^12-3597370*p^11+2105880*p^10-999180*p^9+371000
           *p^8-101780*p^7+18480*p^6-1680*p^5)+2*(-21*p^25+420*p^24-3990*p^23+24024*p^22-103362*p^21+340221*p^20-896679*p^19+1954827*p^18-3604755*p^17+5695179*p^16-7742301*p^15+9038379*p^14-9009357*p^13+7608720*p^12-
           5390385*p^11+3158820*p^10-1498770*p^9+556500*p^8-152670*p^7+27720*p^6-2520*p^5))/(7*p^27-147*p^26+1505*p^25-10073*p^24+49777*p^23-193781*p^22+616532*p^21-1636082*p^20+3660762*p^19-6946380*p^18+11213888*p^17-
           15426950*p^16+18087244*p^15-18037012*p^14+15224160*p^13-10781610*p^12+6317640*p^11-2997540*p^10+1113000*p^9-305340*p^8+55440*p^7-5040*p^6)
lines(p,tot,col=2,lty=2)

#plotting method by NcAdam
lines(p,3*8/7/(p*(1-p)),col=3,lty=2)

legend(0.2,500,
       c("this method calculation","AdamO","NcAdams","this method simulation"),
       lty=c(1,2,2,0),pch=c(NA,NA,NA,1),col=c(1,2,3,1))


##### simulation part ######

#creating decision table
mat<-matrix(as.numeric(intToBits(c(0:(2^5-1)))),2^5,byrow=1)[,c(1:12)]
colnames(mat) <- c("b1","b2","b3","b4","b5","b6","b7","sum5","sum6","sum7","decision","exit")

# first 5 rolls
mat[,8] <- sapply(c(1:2^5), FUN = function(x) {sum(mat[x,1:5])})

mat[which((mat[,8]==2)&(mat[,11]==0))[1:7],12] = rep(5,7) # we can stop for 7 cases with 2 heads
mat[which((mat[,8]==2)&(mat[,11]==0))[1:7],11] = c(1:7)   
mat[which((mat[,8]==3)&(mat[,11]==0))[1:7],12] = rep(5,7) # we can stop for 7 cases with 3 heads
mat[which((mat[,8]==3)&(mat[,11]==0))[1:7],11] = c(1:7)    

# extra 6th roll
mat <- rbind(mat,mat)
mat[c(33:64),6] <- rep(1,32)
mat[,9] <- sapply(c(1:2^6), FUN = function(x) {sum(mat[x,1:6])})

mat[which((mat[,9]==2)&(mat[,11]==0))[1:7],12] = rep(6,7) # we can stop for 7 cases with 2 heads
mat[which((mat[,9]==2)&(mat[,11]==0))[1:7],11] = c(1:7)   
mat[which((mat[,9]==4)&(mat[,11]==0))[1:7],12] = rep(6,7) # we can stop for 7 cases with 4 heads
mat[which((mat[,9]==4)&(mat[,11]==0))[1:7],11] = c(1:7)    

# extra 7th roll
mat <- rbind(mat,mat)
mat[c(65:128),7] <- rep(1,64)
mat[,10] <- sapply(c(1:2^7), FUN = function(x) {sum(mat[x,1:7])})

for (i in 1:6) {
  mat[which((mat[,10]==i)&(mat[,11]==0))[1:7],12] = rep(7,7) # we can stop for 7 cases with i heads
  mat[which((mat[,10]==i)&(mat[,11]==0))[1:7],11] = c(1:7)   
}


mat[1,12] = 7           # when we did not have succes we still need to count the 7 coin tosses
mat[2^7,12] = 7


draws = rep(0,100)
num = rep(0,100)
# plotting simulation
for (p in seq(0.05,0.95,0.05)) {
  n <- rep(0,1000)
  for (i in 1:1000) {
    coinflips <- rbinom(7,1,p)  # draw seven numbers
    I <- mat[,1:7]-matrix(rep(coinflips,2^7),2^7,byrow=1) == rep(0,7)                      # compare with the table
    Imatch = I[,1]*I[,2]*I[,3]*I[,4]*I[,5]*I[,6]*I[,7]        # compare with the table 
      draws[i] <- mat[which(Imatch==1),11]                 # result which number
      num[i]   <- mat[which(Imatch==1),12]                 # result how long it took
  }
  Nturn <- mean(num)                   #how many flips we made
  Sturn <- (1000-sum(draws==0))/1000   #how many numbers we got (relatively)
  points(p,Nturn/Sturn)
}

p(1p)

Vergleich mit skalierten Erwartungswerten

Vergrößern Sie die in diesem Beitrag beschriebenen Vergleichsmethoden und Kommentare

Vergleichsmethoden hier beschrieben

Das "bedingte Überspringen des 7. Schritts" ist eine leichte Verbesserung gegenüber der Regel des vorzeitigen Stopps. In diesem Fall wählen Sie nach dem 6. Flip nicht Gruppen mit gleichen Wahrscheinlichkeiten aus. Sie haben 6 Gruppen mit gleichen Wahrscheinlichkeiten und 1 Gruppe mit leicht unterschiedlicher Wahrscheinlichkeit (für diese letzte Gruppe müssen Sie noch einmal umdrehen, wenn Sie 6 Köpfe oder Schwänze haben, und weil Sie die 7 Köpfe oder 7 Schwänze wegwerfen, werden Sie enden immerhin mit der gleichen Wahrscheinlichkeit)


Geschrieben von StackExchangeStrike

Sextus Empiricus
quelle
Ich war gerade dabei, die Berechnungen für den Fall n = 7 durchzuführen, weil ich das Gefühl hatte, es könnte besser sein als n = 1. Habe mein Votum, Sir!
M.Herzkamp
CkX
Die Verbesserung reduziert sich also auf etwas mehr als 6 Münzwürfe als Erwartungswert für die Anzahl der erforderlichen Münzwürfe. Es würde jedoch variieren, um zu beweisen, dass dies die optimale Lösung ist. Das von Clid erstellte Schema weicht ein wenig voneinander ab, sodass bei einer bestimmten Anzahl von Münzwürfen eine Zahl gewählt werden kann, die jedoch nicht mit der gleichen Wahrscheinlichkeit erreicht wird (zumindest für diesen bestimmten Schritt wird sie später korrigiert).
Sextus Empiricus
Aber wenn Sie auf der Grundlage der ersten fünf Ergebnisse entscheiden, ob Sie die sechste Münze werfen möchten, sind die Wahrscheinlichkeiten für jeden Satz davon abhängig, dass Sie sechs Mal werfen, wie für die anderen Sätze?
Akkumulation
@Akkumulation Sie könnten es als Binärbaum mit 7 Ebenen zeichnen. Wir werden nur unter Knoten auswählen, wenn es 7 mit gleicher Wahrscheinlichkeit gibt. Es ist, als würdest du einige Zweige früher hacken (auf Stufe 5 oder 6). Wenn Sie möchten, können Sie bis zu 7 statt früherer Schritte weitermachen, aber für diese besonderen Fälle machen der 6. und 7. Münzwurf keinen Unterschied.
Sextus Empiricus
20

Teilen Sie ein Kästchen in sieben gleich große Bereiche, die jeweils mit einer Ganzzahl gekennzeichnet sind. Werfen Sie die Münze so in die Schachtel, dass sie mit gleicher Wahrscheinlichkeit in jeder Region landet.

π

p=1p=0

Setzen Sie Monica wieder ein
quelle
2
Können Sie eine Möglichkeit vorschlagen, die Box in sieben gleich große Bereiche zu unterteilen, um die Vorspannung durch Spiegeln, Abprallen von Wänden usw. zu minimieren? Sieben Winkelsektoren 360/7?
SMCI
1
@smci Deswegen setze ich fest, dass du die Münze werfen musst, damit sie mit einer einheitlichen Wahrscheinlichkeit auf jedem Feld landet. Wenn das Abprallen von einer Wand diese Wahrscheinlichkeit beeinflusst, müssen Sie dies bei Ihrem Wurf berücksichtigen.
Setzen Sie Monica
17
Ja, das weiß ich, und ich weise Sie darauf hin , dass es nicht wirklich eine vollständige Antwort ist , wenn Sie einfach "auf unvoreingenommene Weise werfen", ohne genau zu definieren, wie dies erreicht werden soll basierte Methoden sind überlegen.
SMCI
1
"Gleiche Gebiete mit Wurfwahrscheinlichkeiten in jeder Region" sind in der Praxis möglicherweise schwierig zu bestimmen. In der Praxis ist es möglicherweise einfacher, eine große Anzahl von "Übungsläufen" zu markieren und dann die Landefläche empirisch in gleich wahrscheinliche Räume zu unterteilen (z. B. bei 700 Würfen eine Linie ausschließen, die die 100 am weitesten entfernten Würfe abschneidet, dann eine andere für die nächste 100 und so weiter). Eine Vereinfachung davon, um ein einzelnes zufälliges Bit zu erzeugen, wäre, die Münze zweimal zu werfen - wenn der erste Wurf weiter geht, ist das Bit 0und wenn der zweite Wurf weiter geht, ist es ein1
Silberfischchen
4
Es gibt eine nette Antwort von @TheScienceBoy, die leider mit einer interessanten Alternative dazu gestrichen wurde - effektiv unter Verwendung der Münze als Spinner und durch Markieren von 7 Abschnitten entlang ihres Umfangs -, die viel von dem Geist dieser Antwort beibehält, aber physisch unkomplizierter ist Ausführen!
Silberfischchen
8

BEARBEITEN: basierend auf dem Feedback anderer.

Hier ist ein interessanter Gedanke:

setze die Liste von {1,2,3,4,5,6,7}. Wirf die Münze nacheinander für jedes Element in der Liste. Wenn es für ein bestimmtes Element kopfüber angezeigt wird, entfernen Sie die Nummer aus der Liste. Wenn alle Zahlen aus einer bestimmten Iteration der Liste entfernt wurden, wiederholen Sie die Stichprobe. Tun Sie dies, bis nur noch eine Nummer übrig ist.

drop.one <- function(x, p) {
  drop <- runif(length(x)) < p
  if (all(drop))
    return(x)
  return(x[!drop])
}

sample.recur <- function(x, p) {
  if (length(x) > 1)
    return(sample.recur(drop.one(x, p), p))
  return(x)
}

# x <- c(1:7,7:1)
x <- 1:7
p <- 0.01

out <- replicate(1e5, sample.recur(x, p))

round(prop.table(table(out)), 2)

gibt mir eine annähernd gleichmäßige verteilung

> round(prop.table(table(out)), 2)
out
   1    2    3    4    5    6    7 
0.14 0.14 0.15 0.14 0.14 0.14 0.14 

N


Bewertung des Erwartungswertes für die Anzahl der Münzwürfe

xy

M=[q700000117p1q6q600000021p2q56p1q5q50000035p3q415p2q45q4q4000035p4q320p3q310p2q34p1q3q300021p5q215p4q210p3q26p2q23p1q2q2007p6q16p5q15p4q14p3q13p2q12p1q100p7p6p5p4p3p200]

(MI)v=0

E(n)=247p(1p)

Vergleich des Erwartungswertes für Münzwürfe

p>2/3

Lösung mit wxMaxima gefunden

M: matrix(
 [(1-p)^7,        0,          0,0,0,0,1,1], 
 [7* p*(1-p)^6,   (1-p)^6,        0,0,0,0,0,0], 
 [21*p^2*(1-p)^5, 6*p*(1-p)^5,    (1-p)^5,0,0,0,0,0], 
 [35*p^3*(1-p)^4, 15*p^2*(1-p)^4, 5*p*(1-p)^4,(1-p)^4,0,0,0,0], 
 [35*p^4*(1-p)^3, 20*p^3*(1-p)^3, 10*p^2*(1-p)^3,4*p*(1-p)^3,(1-p)^3,0,0,0], 
 [21*p^5*(1-p)^2, 15*p^4*(1-p)^2, 10*p^3*(1-p)^2,6*p^2*(1-p)^2,3*p*(1-p)^2,(1-p)^2,0,0], 
 [7* p^6*(1-p)^1, 6*p^5*(1-p),    5*p^4*(1-p),4*p^3*(1-p),3*p^2*(1-p),2*(1-p)*p,0,0], 
 [p^7,        p^6,        p^5,p^4,p^3,p^2,0,0]
);
z: nullspace(M-diagmatrix(8,1));
x : apply (addcol, args (z));
t : [7,6,5,4,3,2,0,0];
plot2d(t.x/x[7],[p,0,1],logy);

Berechnungen in R

# plotting empty canvas
plot(-100,-100,
     xlab="p",
     ylab="E(total flips)",
     ylim=c(10,1000),xlim=c(0,1),log="y")

# plotting simulation
for (p in seq(0.1,0.9,0.05)) {

  n <- rep(0,10000)
  for (i in 1:10000) {
    success  = 0
    tests = c(1,1,1,1,1,1,1)     # start with seven numbers in the set
    count = 0
    while(success==0) {
      for (j in 1:7)  {
        if (tests[j]==1) {
          count = count + 1
          if  (rbinom(1,1,p) == 1) {
            tests[j] <- 0        # elliminate number when we draw heads
          }
        }
      }
      if (sum(tests)==1) {
        n[i] = count
        success = 1              # end     when 1 is left over
      }
      if (sum(tests)==0) {
        tests = c(1,1,1,1,1,1,1) # restart when 0 are left over
      }
    }
  }
  points(p,mean(n))
}

# plotting formula
p <- seq(0.001,0.999,0.001)

tot <- (7*(p^20-20*p^19+189*p^18-1121*p^17+4674*p^16-14536*p^15+34900*p^14-66014*p^13+99426*p^12-119573*p^11+114257*p^10-85514*p^9+48750*p^8-20100*p^7+5400*p^6-720*p^5)+6*
    (-7*p^21+140*p^20-1323*p^19+7847*p^18-32718*p^17+101752*p^16-244307*p^15+462196*p^14-696612*p^13+839468*p^12-806260*p^11+610617*p^10-357343*p^9+156100*p^8-47950*p^7+9240*p^6-840*p^5)+5*
    (21*p^22-420*p^21+3969*p^20-23541*p^19+98154*p^18-305277*p^17+733257*p^16-1389066*p^15+2100987*p^14-2552529*p^13+2493624*p^12-1952475*p^11+1215900*p^10-594216*p^9+222600*p^8-61068*p^7+11088*p^6-1008*p^5)+4*(-
    35*p^23+700*p^22-6615*p^21+39235*p^20-163625*p^19+509425*p^18-1227345*p^17+2341955*p^16-3595725*p^15+4493195*p^14-4609675*p^13+3907820*p^12-2745610*p^11+1592640*p^10-750855*p^9+278250*p^8-76335*p^7+13860*p^6-
    1260*p^5)+3*(35*p^24-700*p^23+6615*p^22-39270*p^21+164325*p^20-515935*p^19+1264725*p^18-2490320*p^17+4027555*p^16-5447470*p^15+6245645*p^14-6113275*p^13+5102720*p^12-3597370*p^11+2105880*p^10-999180*p^9+371000
   *p^8-101780*p^7+18480*p^6-1680*p^5)+2*(-21*p^25+420*p^24-3990*p^23+24024*p^22-103362*p^21+340221*p^20-896679*p^19+1954827*p^18-3604755*p^17+5695179*p^16-7742301*p^15+9038379*p^14-9009357*p^13+7608720*p^12-
 5390385*p^11+3158820*p^10-1498770*p^9+556500*p^8-152670*p^7+27720*p^6-2520*p^5))/(7*p^27-147*p^26+1505*p^25-10073*p^24+49777*p^23-193781*p^22+616532*p^21-1636082*p^20+3660762*p^19-6946380*p^18+11213888*p^17-
  15426950*p^16+18087244*p^15-18037012*p^14+15224160*p^13-10781610*p^12+6317640*p^11-2997540*p^10+1113000*p^9-305340*p^8+55440*p^7-5040*p^6)
lines(p,tot)

#plotting comparison with alternative method
lines(p,3*8/7/(p*(1-p)),lty=2)

legend(0.2,500,
       c("simulation","calculation","comparison"),
       lty=c(0,1,2),pch=c(1,NA,NA))
AdamO
quelle
1
Kluge Idee (+1). Intuitiv sollte es funktionieren, da die Symmetrie die Tendenz zu einer bestimmten Zahl zunichte zu machen scheint. Trotzdem würde ich gerne einen Beweis sehen.
Setzen Sie Monica
6
Diese Idee ist wirklich nett, aber mit einer hohen Wahrscheinlichkeit für den Kopf (diese Zahl ausknocken) denke ich, dass die letzte Zahl in der Reihe die besten Chancen zum "Überleben" hat, da alle anderen vorne sehr wahrscheinlich vor dem ersten Lauf rausgeschmissen werden? Vielleicht könnte man es ändern, indem man die Münze nicht nacheinander wirft, sondern parallel für alle Zahlen in x? Die Laufzeit des Skripts könnte sich wahrscheinlich erhöhen :)
TinglTanglBob
2
Ich bin mit @TinglTanglBob einverstanden - wenn ich p <- 0.99die Ausgabe einstelle, bekomme ich0.89 0.02 0.02 0.02 0.02 0.02 0.02
Silverfish
6
Würde die Eliminierung in "Runden" nicht das Bias-Problem beheben? Beginnen Sie mit 7 Zahlen. Wirf die Münze für jede verbleibende Zahl und eliminiere die, die den Kopf werfen. Wenn alle verbleibenden Zahlen in einer Runde beseitigt sind, kratzen Sie die Ergebnisse dieser Runde und versuchen Sie es erneut. Ich weiß nicht, wie ich es beweisen soll, aber intuitiv spielt es keine Rolle mehr, ob die Zahlen der Gewinner sind
Phil
1
p=0.01
5

Die Frage ist ein bisschen mehrdeutig, lautet die Frage "Generiere eine zufällige Ganzzahl gleich oder kleiner als 7 mit gleicher Wahrscheinlichkeit" oder lautet die Frage "Generiere 7 zufällige Ganzzahlen mit gleicher Wahrscheinlichkeit"? - aber was ist der Raum von ganzen Zahlen?!?

Ich nehme an, es ist das erstere, aber die gleiche Logik, die ich anwende, kann auch auf den letzteren Fall ausgedehnt werden, sobald dieses Problem geklärt ist.

Mit einer voreingenommenen Münze können Sie eine faire Münze wie folgt produzieren: https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin

Eine Zahl von 7 oder weniger kann als dreistellige {0,1} Zahl binär geschrieben werden. Alles, was Sie tun müssen, ist das obige Verfahren dreimal auszuführen und die erzeugte Binärzahl in eine Dezimalzahl umzuwandeln.

Cam.Davidson.Pilon
quelle
1
Wenn ich meine Antwort mit @NcAdams vergleiche, ist es klar, dass ich 0 als mögliches wünschenswertes Ergebnis einbeziehe!
Cam.Davidson.Pilon
Ich verstehe nicht, wie deine Antwort anders ist. Wenn Sie {0,0,0} -> 1 angeben, worauf bezieht sich dann {1,1,1}? Es gibt 8 Möglichkeiten.
AdamO
1
000 Maps auf 0, daher mein Kommentar zum Einschließen von 0 als möglichen Wert. Dies wurde vor dem OP editiert und fast gleichzeitig als NcAdams gepostet.
Cam.Davidson.Pilon
Die Hälfte dieser Antwort ist ein Kommentar, und der eigentliche Inhalt der Antwort ist nur ein Link. Bitte buchstabieren Sie Ihre eigentliche Antwort, anstatt nur darauf zu verlinken.
Cubic
3

Eine Lösung, die niemals Flips verschwendet, was für sehr voreingenommene Münzen sehr hilfreich ist.

Der Nachteil dieses Algorithmus (zumindest wie geschrieben) ist, dass er Arithmetik mit willkürlicher Genauigkeit verwendet. In der Praxis möchten Sie dies wahrscheinlich verwenden, bis eine Ganzzahl überläuft, und es erst dann wegwerfen und von vorne beginnen.

Außerdem müssen Sie wissen, wie stark die Abweichung ist ... was Sie vielleicht nicht sagen, wenn sie wie die meisten physikalischen Phänomene temperaturabhängig ist.


Angenommen, die Chance von Köpfen liegt bei 30%.

  • Beginnen Sie mit dem Bereich [1, 8).
  • Wirf deine Münze um. Wenn es sich um Köpfe handelt, verwenden Sie die linken 30%, damit Ihre neue Reichweite ist [1, 3.1). Andernfalls verwenden Sie die richtigen 70%, damit Ihre neue Reichweite ist [3.1, 8).
  • Wiederholen, bis der gesamte Bereich den gleichen ganzzahligen Teil hat.

Vollständiger Code:

#!/usr/bin/env python3
from fractions import Fraction
from collections import Counter
from random import randrange


BIAS = Fraction(3, 10)
STAT_COUNT = 100000


calls = 0
def biased_rand():
    global calls
    calls += 1
    return randrange(BIAS.denominator) < BIAS.numerator


def can_generate_multiple(start, stop):
    if stop.denominator == 1:
        # half-open range
        stop = stop.numerator - 1
    else:
        stop = int(stop)
    start = int(start)
    return start != stop


def unbiased_rand(start, stop):
    if start < 0:
        # negative numbers round wrong
        return start + unbiased_rand(0, stop - start)
    assert isinstance(start, int) and start >= 0
    assert isinstance(stop, int) and stop >= start
    start = Fraction(start)
    stop = Fraction(stop)
    while can_generate_multiple(start, stop):
        if biased_rand():
            old_diff = stop - start
            diff = old_diff * BIAS
            stop = start + diff
        else:
            old_diff = stop - start
            diff = old_diff * (1 - BIAS)
            start = stop - diff
    return int(start)


def stats(f, *args, **kwargs):
    c = Counter()
    for _ in range(STAT_COUNT):
        c[f(*args, **kwargs)] += 1

    print('stats for %s:' % f.__qualname__)
    for k, v in sorted(c.items()):
        percent = v * 100 / STAT_COUNT
        print('  %s: %f%%' % (k, percent))


def main():
    #stats(biased_rand)
    stats(unbiased_rand, 1, 7+1)
    print('used %f calls at bias %s' % (calls/STAT_COUNT, BIAS))


if __name__ == '__main__':
    main()
o11c
quelle
3
[0,1]00006666k
Das gilt auch für eine einzelne Ausgabe, oder? Einfach besser für mehrere? Ich würde es so schreiben, wie diff *= 7ich denke ... in der Tat gibt es keine besondere Notwendigkeit, für jeden Versuch dieselbe Basis zu verwenden.
07.07.18 Uhr
Ja, es ist dasselbe, wenn Sie eine einzelne Ausgabe wünschen. Es verbessert nur die Effizienz, wenn Sie mehrere möchten.
Federico Poloni
pp
Wenn Sie eine einzelne Ausgabe wünschen, wird dies absolut zu Makulatur führen. Für eine faire Münze ergibt die Standardtechnik (dreimal rollen und bei TTT wiederholen) eine erwartete Anzahl von 24/7 = 3 + 3/7-Rollen. Wenn Sie diese Technik mit arithmetischer Codierung verwenden, würfeln Sie mindestens vier Mal, es sei denn, Sie erhalten HHH oder TTT, was zu einer erwarteten Anzahl von mehr als 15/4 = 3 + 3/4 Würfen führt.
Peter Shor
3

Wie in früheren Kommentaren erwähnt, bezieht sich dieses Rätsel auf John von Neumanns 1951 erschienene Arbeit "Various Techniques Used in Connection With Random Digits" im Research Journal des National Bureau of Standards:

Bildbeschreibung hier eingeben

pf(p)f f(p)=min{1,2p}N von Studien.

Xi'an
quelle
2

p1p0

Wir wandeln zuerst die (möglicherweise) unfaire Münze in eine faire Münze um .

Wirf die Münze zweimal um. Wenn es landet HHoder TT, ignoriere es und drehe es noch zweimal um.

Nun hat die Münze die gleiche Wahrscheinlichkeit aufzutauchen HToder TH. Wenn es auftaucht HT, ruf das an H1. Wenn es auftaucht TH, ruf das an T1.

01H1=1T1 =00.H1 H1 T10.110

1/7

1/7=0.001001001...

2/7=0.010010010...

3/7=0.011011011...

4/7=0.100100100...

5/7=0.101101101...

6/7=0.110110110...

nn/7(n1)/717

clid
quelle
1
1/7
1
1/7k=1(1/8)k=17
1
nT(n)=2n62nn3
3+n=31T(n)=4.5
8733.42
2

Inspiriert von der Antwort von AdamO ist hier eine Python-Lösung, die Verzerrungen vermeidet:

def roll(p, n):
    remaining = range(1,n+1)
    flips = 0
    while len(remaining) > 1:
        round_winners = [c for c in remaining if random.choices(['H','T'], [p, 1.0-p]) == ['H']]
        flips += len(remaining)
        if len(round_winners) > 0:
            remaining = round_winners
        p = 1.0 - p
    return remaining[0], flips

Hier gibt es zwei wesentliche Änderungen: Die wichtigste besteht darin, dass die Runde wiederholt wird, wenn alle Zahlen in einer Runde verworfen wurden. Auch ich drehe die Wahl, ob Kopf oder Zahl bedeutet, jedes Mal zu verwerfen. Dies reduziert die Anzahl der benötigten Flips in Fällen, in denen p nahe 0 oder 1 liegt, um ~ 70%, wenn p = 0,999

Phil
quelle
2
"Ich drehe die Wahl, ob Kopf oder Zahl bedeutet, dass jedes Mal verworfen wird. Dies reduziert die Anzahl der erforderlichen Dreheffekte in Fällen, in denen p nahe 0 oder 1 liegt, um ~ 70%, wenn p = 0,999" - kluges Denken!
Silverfish
1
Das Abwechseln von Kopf oder Zahl ist definitiv eine Verbesserung gegenüber dem Abwerfen von Köpfen - aber vielleicht ist es besser, wenn wir nach dem Umwerfen einer Münze für jede verbleibende Option, wenn sie alle gleich sind, alle erneut umwerfen, andernfalls, wenn es mindestens solche gibt so viele Köpfe wie Schwänze eliminieren wir die verbleibenden Optionen, die den Köpfen entsprechen, andernfalls eliminieren wir die verbleibenden Optionen, die den Schwänzen entsprechen.
David Cary
2

Es scheint, dass wir die Zuordnung des Ergebnisses jedes Flip jedes Mal ändern dürfen, wenn wir flippen . Aus Bequemlichkeitsgründen geben wir unter Verwendung der ersten sieben positiven ganzen Zahlen die folgenden Befehle ein:

H1
H2

H7
H1

usw

T


APT

PAP(no integers generated)=(1p)7

Nb

CountAP(useless flips)7Nb(1p)7

B(p,n=5)p3(1p)2

PDS(no integers generated)=17p3(1p)2

Die Anzahl der nutzlosen Flips wird hier tendenziell steigen

CountDS(useless flips)5Nb[17p3(1p)2]

AP

CountAP(useless flips)<CountDS(useless flips)

7Nb(1p)7<5Nb[17p3(1p)2]

7(1p)7<5[17p3(1p)2]

p>0.0467AP

pAPDSp0.5967

CountAP(useless flips)CountDS(useless flips)

0.67p=0.10.3p=0.20.127p=0.4

Alecos Papadopoulos
quelle
p(0,1)
1
@Sycorax Ich habe etwas hinzugefügt, obwohl ich nicht sicher bin, ob es in die von Ihnen vorgeschlagene Richtung geht.
Alecos Papadopoulos
H
1
12345679999999
1
p17p