Łamigłówka: Jak wygenerować 7 liczb całkowitych z jednakowym prawdopodobieństwem przy użyciu stronniczej monety, która ma pr (głowa) = p?


58

Oto pytanie, które znalazłem na Glassdoor : Jak wygenerować 7 liczb całkowitych z jednakowym prawdopodobieństwem, używając monety, która ma P.r(Głowa)=p(0,1) ?

Zasadniczo masz monetę, która może, ale nie musi być uczciwa, i jest to jedyny proces generowania liczb losowych, jaki masz, więc wymyśl generator liczb losowych, który generuje liczby całkowite od 1 do 7, w których prawdopodobieństwo uzyskania każdej z tych liczb całkowitych wynosi 1/7.

Wydajność danych generuje ważne procesy.



12
Istnieją niezliczone sposoby na osiągnięcie tego. Bardziej interesująca wersja pytania wymaga najlepszej metody w ściśle określonym znaczeniu. Naturalnym poczuciem najlepszej jest najmniej oczekiwana liczba rzutów na liczbę całkowitą wygenerowaną. Kolejną interesującą wersją jest opisanie wszystkich możliwych rozwiązań (które polegają na niezależnych rzutach monety i niczym więcej).
whuber

1
@ Whuber dobra sugestia, zredagowałem pytanie, aby odzwierciedlić twój komentarz.
Amazonian

<<< Zasadniczo masz monetę, która może, ale nie musi być uczciwa, i jest to jedyny proces generowania liczb losowych, jaki masz >>> Czy to oznacza, że ​​używasz monety w inny sposób niż przerzucanie jej i sprawdzanie głowy kontra ogon jest „zabroniony”, ponieważ byłby to kolejny proces generowania liczb losowych?
TinglTanglBob

9
Mod 7 roku na monecie.
Nat

Odpowiedzi:


56

Rzuć monetą dwa razy. Jeśli wyląduje HHlub TTzignoruj ​​go i dwukrotnie odwróć.

Teraz moneta ma jednakowe prawdopodobieństwo pojawienia się HTlub TH. Jeśli się pojawi HT, zadzwoń H1. Jeśli się pojawi TH, zadzwoń T1.

Zdobywaj kolejne H1lub T1dopóki nie będziesz mieć trzech z rzędu. Te trzy wyniki dają liczbę na podstawie poniższej tabeli:

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]

Twierdzę, że to działałoby idealnie dobrze, chociaż miałbyś wiele zmarnowanych rzutów!


4
Jedynym ograniczeniem jest to, że prawdopodobieństwo głów wynosi „p”. Zauważ, że p może wynosić lub 1 . Nie gwarantuje to, że zadziała, ale Sycorax (lub Sephan) działałoby, nawet w takich przypadkach. 01
gung - Przywróć Monikę

8
@gung: Nie jestem pewien, czy będę pracował na monetę z dwiema głowami lub dwoma ogonami.
S. Kolassa - Przywróć Monikę

6
Z prawdopodobieństwem zakończy się w skończonym czasie. 1
clark

18
Nazywa się to wybielaniem von Neumana.
DonFusili

4
Możesz iterować ekstraktor von Neumanna, aby pełniej wyodrębnić entropię z sekwencji. Zbierz wszystkie pary HH i TT, weź pod uwagę sekwencję, zastosuj do tego ekstraktor von Neumanna itp.
A Simmons

47

Załóżmy, że .p(0,1)

Etap 1: . Rzuć monetą 5 razy.

Jeśli wynik jest

, zwróć 1 i zatrzymaj.(H,H,H,T,T)1

, zwróć 2 i zatrzymaj się.(H,H,T,T,H)2

, zwróć 3 i zatrzymaj.(H,T,T,H,H)3

, zwróć 4 i zatrzymaj.(T,T,H,H,H)4

, zwróć 5 i zatrzymaj.(T,H,H,H,T)5

, wróć 6 i zatrzymaj się.(H,H,T,H,T)6

, zwróć 7 i zatrzymaj się.(H,T,H,T,H)7

Etap 2: . Jeśli wynik nie jest żadnym z powyższych, powtórz krok 1.

Pamiętaj, że niezależnie od wartości , każdy z siedmiu wymienionych powyżej wyników ma prawdopodobieństwo q = p 3 ( 1 - p ) 2 , a oczekiwana liczba rzutów monetą wynosi 5p(0,1)q=p3(1p)2 . Rzutnik nie musi znać wartościp(z wyjątkiem tego, żep0ip1); gwarantowane jest, że siedem liczb całkowitych zostanie jednakowo zwróconych przez eksperyment po jego zakończeniu (i gwarantuje się, że zakończy się z prawdopodobieństwem1).57qpp0p11


6
Czy możemy zmniejszyć oczekiwaną liczbę rzutów w tym celu, pozwalając na sekwencję określoną tutaj LUB na tę sekwencję z każdym odwróceniem. np .: Dla 1 albo (H, H, H, T, T) lub (T, T, T, H, H)?
więcejON

5
Możesz również dodać uzupełnienie. Jeśli wynikiem jest (H, H, H, T, T) lub (T, T, T, H, H), zwróć 1 i zatrzymaj itd. W takim przypadku prawdopodobieństwo dla każdego wyniku wynosi . q=p3(1p)2+p2(1p)3
Sextus Empiricus

2
Czy nie byłoby możliwe dodanie kolejnego rzutu monetą, jeśli wynik nie jest związany z żadnym układem (H, H, H, T, T)? Z dodatkowym rzutem monetą potrzebujesz innego mapowania (H, H, H, T, T, T) i (H, H, T, T, T, T) i każdej kombinacji xT (7-x) H które mogą być ułożone w 7 lub więcej różnych kolejności od liczb od 1 do 7. Zamiast ponownego losowania wszystkich 5 monet dodałoby to tylko 1 dodatkowy los, ale nie jestem pewien, czy to działa: D
TinglTanglBob

5
Być może najlepszą rzeczą może być natychmiastowe odwrócenie monety 7 razy, ponieważ poza tym jest gwarantowane, że otrzymasz z niej losową liczbę (jedynym wyjątkiem jest to, że moneta wyląduje głową w górę lub ogonem wszystkie 7 prób) . Więc z 7 rzutami możesz skończyć z 1 do 6 głowami (wykluczam tutaj opcję 0 i 7, ponieważ jest to bezcelowe). Jeśli jedna głowa ma 7 różnych ustawień (H, T, T, T, T, T, T); Jeśli 2 głów to 21; jeśli 3 głów to 35; jeżeli 4 35 sztuk; jeżeli 5 21 sztuk; jeżeli 6 7 głów; Każda z nich może być doskonale odwzorowana na numer 1-7 bez utraty kombinacji.
TinglTanglBob,

2
@TinglTanglBob To jest w zasadzie odpowiedź Martijn Weterings ;-)
M.Herzkamp

22

Uogólnienie przypadku opisanego przez Dilip Sarwate

Niektóre metody opisane w innych odpowiedziach wykorzystują schemat, w którym rzucasz sekwencją n monet w „turze” iw zależności od wyniku wybierasz liczbę od 1 do 7 lub odrzucasz turę i rzucasz ponownie.

Sztuką jest znalezienie w rozszerzeniu możliwości wielu 7 wyników o tym samym prawdopodobieństwie pk(1p)nk i dopasowanie ich do siebie.

Ponieważ łączna liczba wyników nie jest wielokrotnością liczby 7, mamy kilka wyników, których nie możemy przypisać do liczby, i istnieje pewne prawdopodobieństwo, że musimy odrzucić wyniki i zacząć od nowa.


Przypadek użycia 7 rzutów monetą na turę

Intuicyjnie możemy powiedzieć, że rzucie kostką siedem razy byłoby bardzo interesujące. Ponieważ musimy wyrzucić tylko 2 z 27 możliwości. Mianowicie 7 razy głowy i 0 razy głowy.

Dla wszystkich pozostałych 272 możliwości zawsze występuje wiele 7 skrzynek z tą samą liczbą głowic. Mianowicie 7 skrzyń z 1 głowami, 21 skrzyń z 2 głowami, 35 skrzynek z 3 głowami, 35 skrzynek z 4 głowami, 21 skrzynek z 5 głowami i 7 skrzynek z 6 głowami.

Więc jeśli policzysz liczbę (odrzucając 0 głów i 7 głów)

X=k=17(k1)Ck

z Ck Bernoulliego rozproszone zmiennych (wartość 0 lub 1), wówczas X modulo 7 jest jednolity zmiennej z siedmiu możliwych wyników.


Porównywanie różnej liczby rzutów monetą na turę

Pozostaje pytanie, jaka byłaby optymalna liczba rzutów na turę. Rzucanie większą ilością kości na turę kosztuje więcej, ale zmniejszasz prawdopodobieństwo ponownego rzutu.

Poniższy obraz pokazuje ręczne obliczenia dla pierwszych kilku liczb rzutów monetą na turę. (być może istnieje rozwiązanie analityczne, ale uważam, że można bezpiecznie powiedzieć, że system z 7 rzutami monetą stanowi najlepszą metodę pod względem wartości oczekiwanej dla wymaganej liczby rzutów monetą)

oczekiwana liczba rzutów monetą

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

Korzystanie z reguły wczesnego zatrzymywania

Uwaga: poniższe obliczenia, dla wartości oczekiwanej liczby rzutów, dotyczą uczciwej monety p=0.5 , zrobienie tego byłoby bałaganem dla różnych p , ale zasada pozostaje ta sama (chociaż różne księgowanie skrzynie są potrzebne)

Powinniśmy być w stanie wybrać przypadki (zamiast formuły dla X ), tak abyśmy mogli zatrzymać wcześniej.

  • Z 5 rzutami monet mamy sześć możliwych różnych nieuporządkowanych zestawów głów i reszek:

    1 + 5 + 10 + 10 + 5 + 1 zamówionych zestawów

    I możemy użyć grup z dziesięcioma przypadkami (to jest grupa z 2 głowami lub grupa z 2 ogonami), aby wybrać (z jednakowym prawdopodobieństwem) liczbę. Dzieje się tak w 14 z 2 ^ 5 = 32 przypadków. To pozostawia nam:

    1 + 5 + 3 + 3 + 5 + 1 zamówionych zestawów

  • Z dodatkowym (6-tym) rzutem monetą mamy siedem możliwych różnych nieuporządkowanych zestawów głów i reszek:

    1 + 6 + 8 + 6 + 8 + 6 + 1 zamówionych zestawów

    I możemy użyć grup z ośmioma przypadkami (to jest grupa z 3 głowami lub grupa z 3 ogonami), aby wybrać (z jednakowym prawdopodobieństwem) liczbę. Dzieje się tak w 14 na 2 * (2 ^ 5-14) = 36 przypadków. To pozostawia nam:

    1 + 6 + 1 + 6 + 1 + 6 + 1 zamówionych zestawów

  • Z kolejnym (7-tym) dodatkowym rzutem monetą mamy osiem możliwych różnych nieuporządkowanych zestawów głów i reszek:

    1 + 7 + 7 + 7 + 7 + 7 + 7 + 1 zamówionych zestawów

    I możemy użyć grup z siedmioma przypadkami (wszystkie z wyjątkiem wszystkich ogonów i wszystkich głów), aby wybrać (z jednakowym prawdopodobieństwem) liczbę. Dzieje się tak w 42 z 44 przypadków. To pozostawia nam:

    1 + 0 + 0 + 0 + 0 + 0 + 0 + 1 zamówionych zestawów

    (moglibyśmy to kontynuować, ale tylko w 49 kroku daje to nam przewagę)

Prawdopodobieństwo wyboru liczby

  • przy 5 rzutach jest 1432=716
  • przy 6 rzutach jest 9161436=732
  • przy 7 rzutach jest 11324244=231704
  • nie w 7 rzutach jest 1716732231704=227

To sprawia, że ​​wartość oczekiwana dla liczby przerzutów w jednej turze jest uzależniona od powodzenia, a p = 0,5:

5716+6732+7231704=5.796875

Wartość oczekiwana dla całkowitej liczby przewrotów (do momentu sukcesu), pod warunkiem, że p = 0,5, staje się:

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


Odpowiedź NcAdams wykorzystuje odmianę strategii zatrzymania (za każdym razem wymyślają dwa nowe rzuty monetą), ale nie optymalnie wybiera wszystkie rzuty.

Odpowiedź Clida może być podobna, chociaż może istnieć nierówna zasada wyboru, że każda z dwóch monet może zostać wybrana, ale niekoniecznie z jednakowym prawdopodobieństwem (rozbieżność, która jest naprawiana podczas późniejszych rzutów monetą)


Porównanie z innymi metodami

Inne metody wykorzystujące podobną zasadę to NcAdams i AdamO.

Zasada jest następująca : decyzja o liczbie od 1 do 7 jest podejmowana po określonej liczbie głów i ogonów. Po liczbie x przewrotów dla każdej decyzji prowadzącej do liczby i istnieje podobna, równie prawdopodobna decyzja, która prowadzi do liczby j (ta sama liczba głów i ogonów, ale tylko w innej kolejności). Niektóre serie głów i ogonów mogą prowadzić do podjęcia decyzji o rozpoczęciu od nowa.

W przypadku tego rodzaju metod, ta umieszczona tutaj jest najbardziej wydajna, ponieważ podejmuje decyzje tak wcześnie, jak to możliwe (tak szybko, jak istnieje możliwość 7 równych sekwencji prawdopodobieństwa głów i ogonów, po x przerzucie możemy użyć aby podjąć decyzję w sprawie liczby i nie musimy przewracać dalej, jeśli napotkamy jeden z tych przypadków).

Dowodzi tego poniższy obraz i symulacja:

porównanie

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

inny obraz skalowany przez p(1p) dla lepszego porównania:

porównanie ze skalowanymi wartościami oczekiwanymi

powiększyć metody porównywania opisane w tym poście i komentarzach

metody porównania opisane tutaj

„warunkowe pominięcie siódmego kroku” to niewielka poprawa, którą można wprowadzić na zasadzie wczesnego zatrzymania. W takim przypadku nie wybierasz grup z jednakowymi prawdopodobieństwami po 6-tym rzucie. Masz 6 grup z jednakowymi prawdopodobieństwami i 1 grupy z nieco innym prawdopodobieństwem (dla tej ostatniej grupy musisz przerzucić jeszcze jeden dodatkowy czas, gdy masz 6 głów lub ogonów, a ponieważ odrzucisz 7 głów lub 7 ogonów, skończysz w końcu z takim samym prawdopodobieństwem)


Napisane przez StackExchangeStrike


Właśnie zacząłem wykonywać obliczenia dla przypadku n = 7, ponieważ miałem wrażenie, że może być lepsze niż n = 1. Proszę o głos, proszę pana!
M.Herzkamp

@ M.Herzkamp niewielka poprawa jest nadal możliwa. Jedna liczba (jedna rzut monetą) nie jest konieczna do obliczenia X , ponieważ ma współczynnik 0. Liczba ta jest konieczna tylko do określenia wielkości wszystkich głów lub ogonów i można ją pominąć, gdy już wiemy, że mamy mieszany przypadek. dokX
Sextus Empiricus

Ulepszenie sprowadza więc do nieco więcej niż 6 rzutów monetą jako wartości oczekiwanej dla liczby wymaganych rzutów monetą. Byłoby to jednak różne, aby udowodnić, że jest to optymalne rozwiązanie. Schemat stworzony przez Clida różni się nieco, pozwalając wybrać liczbę przy określonej liczbie rzutów monetą, ale nie z jednakowym prawdopodobieństwem (przynajmniej nie dla tego konkretnego kroku, zostanie poprawiony później).
Sextus Empiricus

Ale jeśli decydujesz, czy rzucić szóstą monetą na podstawie pierwszych pięciu wyników, to czy prawdopodobieństwo każdego zestawu jest uwarunkowane uzyskaniem sześciu rzutów, tak samo jak w przypadku innych zestawów?
Akumulacja

@Acccumulation możesz go narysować jako drzewo binarne z 7 poziomami. Będziemy wybierać spośród węzłów tylko wtedy, gdy będzie ich 7 z jednakowym prawdopodobieństwem. To tak, jakbyś wcześniej ścinał niektóre gałęzie (na poziomie 5 lub 6). Jeśli chcesz, możesz kontynuować do 7 kroków, zamiast wcześniej, ale w tych szczególnych przypadkach 6 i 7 rzut monetą nie mają znaczenia.
Sextus Empiricus

20

Podziel pole na siedem regionów o równej powierzchni, każdy oznaczony liczbą całkowitą. Wrzuć monetę do pudełka w taki sposób, aby prawdopodobieństwo wylądowania było równe w każdym regionie.

To tylko połowa żartu - jest to w zasadzie ta sama procedura, co oszacowanie π za pomocą fizycznej procedury Monte Carlo, na przykład upuszczenie ziaren ryżu na papier z narysowanym kółkiem.

Jest to jedna z jedynych odpowiedzi, która działa w przypadku lub p = 0 .p=1p=0


2
Czy możesz zasugerować sposób podzielenia pudełka na siedem regionów o równej powierzchni, aby zminimalizować odchylenie od przewracania, odbijania się od ścian itp.? Siedem sektorów o kącie 360/7?
smci,

1
@smci Dlatego zastrzegam, że musisz rzucić monetą, aby istniało jednolite prawdopodobieństwo, że wyląduje ona na każdym polu. Jeśli odbicie od ściany wpływa na to prawdopodobieństwo, musisz uwzględnić to w swoim rzucie.
Przywróć Monikę

17
Tak, wiem o tym i zwracam uwagę na to , że samo powiedzenie „rzuć to bezstronnie” bez dokładnego określenia, jak to osiągnąć, nie jest tak naprawdę pełną odpowiedzią ... w takim przypadku flipping-H / T metody oparte są lepsze.
smci

1
„Równe obszary z rzutami, które mają równe prawdopodobieństwo lądowania w każdym regionie” może być trudne do ustalenia w praktyce. W praktyce może być łatwiej wyznaczyć dużą liczbę „biegów próbnych”, a następnie podzielić empirycznie obszar lądowania na odpowiednie pola (np. Z 700 rzutami, wykluczyć linię, która odcina 100 najdalszych rzutów, a następnie kolejną na następne 100 i tak dalej). Uproszczenie tego, aby wygenerować pojedynczy losowy bit, polegałoby na rzuceniu monetą dwa razy - jeśli pierwszy rzut pójdzie dalej, bit będzie 0, a jeśli drugi rzut pójdzie dalej, to1
Silverfish

4
@TheScienceBoy ma dobrą odpowiedź, która niestety została usunięta z ciekawą alternatywą - efektywnie, używając monety jako spinnera i zaznaczając 7 odcinków na obwodzie - która zachowuje ducha tej odpowiedzi, ale może być bardziej fizycznie prosta wynieść!
Silverfish,

8

EDYCJA: w oparciu o opinie innych.

Oto interesująca myśl:

ustaw listę {1,2,3,4,5,6,7}. Rzuć monetą kolejno dla każdego elementu na liście. Jeśli wyląduje głową do góry dla określonego elementu, usuń numer z listy. Jeśli wszystkie liczby z określonej iteracji listy zostaną usunięte, powtórz próbkowanie. Rób tak, aż pozostanie tylko jedna liczba.

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)

daje mi w przybliżeniu równomierny rozkład

> 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.


Ocena wartości oczekiwanej liczby rzutów monetą

xy

M=[q700000117p1q6q600000021p2)q56p1q5q50000035p3)q415p2)q45q4q4000035p4q3)20p3)q3)10p2)q3)4p1q3)q3)00021p5q2)15p4q2)10p3)q2)6p2)q2)3)p1q2)q2)007p6q16p5q15p4q14p3)q13)p2)q12)p1q100p7p6p5p4p3)p2)00]

(M.-ja)v=0 ) pokazuje, ile czasu relatywnie spędza się w jakim stanie. W takim razie stan siódmy to, jak często będziesz w stanie narysować liczbę od 1 do 7. Inne stany mówią, ile kosztuje rzut monetą.

E(n)=247p(1p)

porównanie wartości oczekiwanej dla rzutów monetą

p>2/3 . Ale także wydajność jest niesymetryczna. Symetryczna i lepsza ogólna wydajność mogłaby zostać osiągnięta, gdyby utworzona została probabilistyczna reguła przełączania, która zmienia regułę decyzji z ogonów na głowy, gdy głowy okazują się nieprawdopodobne.

Rozwiązanie znalezione w wxMaxima

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);

Obliczenia w 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))

1
Sprytny pomysł (+1). Intuicyjnie powinno to działać, ponieważ wydaje się, że symetria niweluje stronniczość względem dowolnej określonej liczby. Mimo to chciałbym zobaczyć dowód.
Przywróć Monikę

6
Ten pomysł jest naprawdę fajny, ale z dużym prawdopodobieństwem dla głowy (znokautuj tę liczbę) myślę, że ostatnia liczba z rzędu ma największe szanse na „przetrwanie”, ponieważ wszyscy inni przed wykopaniem są bardzo prawdopodobni przed pierwszym biegiem? Może można to zmienić, nie rzucając kolejno monetą, ale równolegle dla wszystkich liczb w x?
Wydaje mi się,

2
Zgadzam się z @TinglTanglBob - kiedy ustawiam p <- 0.99, otrzymuję wynik0.89 0.02 0.02 0.02 0.02 0.02 0.02
Silverfish

6
Czy wykonanie eliminacji w „rundach” nie rozwiązałoby problemu uprzedzeń? Zacznij od 7 liczb. Rzuć monetą dla każdej pozostałej liczby i wyeliminuj te, które rzucają głową. Jeśli wszystkie pozostałe liczby zostaną wyeliminowane w rundzie, podrap wyniki tej rundy i spróbuj ponownie. Nie wiem, jak to udowodnić, ale intuicyjnie kolejność liczb nie ma już znaczenia, czy są one „zwycięzcami”
Phil

1
p=0,01

5

Pytanie jest nieco dwuznaczne, czy pyta „wygeneruj losową liczbę całkowitą równą lub mniejszą niż 7 z jednakowym prawdopodobieństwem”, czy też pytasz „wygeneruj 7 losowych liczb całkowitych z jednakowym prawdopodobieństwem?” - ale jaka jest przestrzeń liczb całkowitych?!?

Zakładam, że jest to pierwsza, ale ta sama logika, którą stosuję, może zostać rozszerzona na tę drugą sprawę, gdy problem zostanie rozwiązany.

Za pomocą stronniczej monety możesz wyprodukować uczciwą monetę, postępując zgodnie z następującą procedurą: https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_part_coin

Liczbę 7 lub mniejszą można zapisać dwójkowo jako trzy cyfry {0,1}. Wystarczy więc trzykrotnie wykonać powyższą procedurę i przekonwertować wyprodukowaną liczbę binarną na dziesiętną.


1
porównując moją odpowiedź z @NcAdams, jasne jest, że podam 0 jako możliwy pożądany wynik!
Cam.Davidson.Pilon

Nie rozumiem, jak twoja odpowiedź jest inna. Jeśli podasz {0,0,0} -> 1, to na co mapuje {1,1,1}? Istnieje 8 możliwości.
AdamO,

1
000 odwzorowuje na 0, stąd mój komentarz do włączenia 0 jako możliwej wartości. Zostało to opublikowane przed edycją OP i prawie jednocześnie jako NcAdams.
Cam.Davidson.Pilon

Połowa tej odpowiedzi to komentarz, a rzeczywista treść odpowiedzi jest tylko linkiem. Podaj rzeczywistą odpowiedź, a nie tylko link do niej.
Cubic

3

Rozwiązanie, które nigdy nie marnuje flipów, co bardzo pomaga w przypadku bardzo tendencyjnych monet.

Wadą tego algorytmu (przynajmniej tak jak napisano) jest to, że używa arytmetyki o dowolnej precyzji. Praktycznie prawdopodobnie chcesz tego używać, aż do przepełnienia liczb całkowitych, a dopiero potem wyrzuć go i zacznij od nowa.

Musisz także wiedzieć, na czym polega uprzedzenie ... czego możesz nie powiedzieć, jeśli jest zależne od temperatury, jak większość zjawisk fizycznych.


Zakładając, że szansa na głowę wynosi, powiedzmy, 30%.

  • Zacznij od zakresu [1, 8).
  • Rzuć monetą. Jeśli masz głowy, użyj lewego 30%, więc twój nowy zakres to [1, 3.1). W przeciwnym razie użyj właściwych 70%, więc nowy zakres to [3.1, 8).
  • Powtarzaj, aż cały zakres będzie miał tę samą liczbę całkowitą.

Pełny kod:

#!/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()

3
[0,1]00006666k

To samo dotyczy pojedynczego wyjścia, prawda? Po prostu lepiej dla wielu? Pisałbym tak, jak diff *= 7myślę ... w rzeczywistości nie ma szczególnej potrzeby korzystania z tej samej bazy przy każdej próbie.
o11c

Tak, to samo, jeśli chcesz mieć jedno wyjście; poprawia wydajność tylko wtedy, gdy chcesz wielu.
Federico Poloni,

pp

To absolutnie marnuje przewroty, jeśli chcesz mieć jedno wyjście. W przypadku uczciwej monety standardowa technika (rzuć monetą trzy razy i powtórz, jeśli dostaniesz TTT) daje oczekiwaną liczbę 24/7 = 3 + 3/7 rzutów. Jeśli użyjesz tej techniki kodowania arytmetycznego, rzucisz co najmniej cztery razy, chyba że otrzymasz HHH lub TTT, co daje oczekiwaną liczbę więcej niż 15/4 = 3 + 3/4 rolki.
Peter Shor,

3

Jak wspomniano we wcześniejszych komentarzach, zagadka ta odnosi się do artykułu Johna von Neumanna z 1951 r. „Różne techniki stosowane w związku z przypadkowymi cyframi” opublikowanego w czasopiśmie badawczym National Bureau of Standards:

wprowadź opis zdjęcia tutaj

pfa(p)fa fa(p)=min{1,2)p}N. prób.


2

p1p0

Najpierw zamieniamy (prawdopodobnie) nieuczciwą monetę na monetę uczciwą, korzystając z procesu z NcAdams :

Rzuć monetą dwa razy. Jeśli wyląduje HHlub TTzignoruj ​​go i dwukrotnie odwróć.

Teraz moneta ma jednakowe prawdopodobieństwo pojawienia się HTlub TH. Jeśli się pojawi HT, zadzwoń H1. Jeśli się pojawi TH, zadzwoń 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(n-1)/717


1
1/7

1
1/7k=1(1/8)k=17

1
nT(n)=2n62nn3
3+n=31T(n)=4.5
8733.42

2

Zainspirowany odpowiedzią AdamO, oto rozwiązanie Python, które pozwala uniknąć stronniczości:

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

Istnieją tutaj dwie główne zmiany: Główna polega na tym, że jeśli wszystkie liczby zostaną odrzucone w rundzie, powtórz rundę. Również zmieniam wybór, czy głowy czy ogony oznaczają odrzucanie za każdym razem. Zmniejsza to liczbę potrzebnych przerzutów w przypadkach, gdy p jest bliskie 0 lub 1 o ~ 70%, gdy p = 0,999


2
„Za każdym razem zmieniam, czy głowy lub reszki oznaczają odrzucenie. Zmniejsza to liczbę potrzebnych przewrotów w przypadkach, gdy p jest bliskie 0 lub 1 o ~ 70%, gdy p = 0,999” - inteligentne myślenie!
Silverfish,

1
Naprzemienne główki lub reszki to zdecydowanie ulepszenie w stosunku do zawsze odrzucanych głów - ale być może byłoby lepiej, gdyby po rzucie monetą dla każdej pozostałej opcji, jeśli wszystkie są takie same, powtarzamy je wszystkie, w przeciwnym razie, jeśli są przynajmniej tyle głów, ile ogonów, eliminujemy pozostałe opcje odpowiadające głowom, w przeciwnym razie eliminujemy pozostałe opcje odpowiadające ogonom.
David Cary,

2

Wygląda na to, że za każdym razem możemy zmieniać mapowanie wyniku każdego przerzucenia . Tak więc, używając dla wygody pierwszych siedmiu liczb całkowitych dodatnich, wydajemy następujące zamówienia:

H.1
H.2)

H.7
H.1

itp

T.


ZAP.T.

P.ZAP.(nie wygenerowano liczb całkowitych)=(1-p)7

N.b

LiczyćZAP.(bezużyteczne koziołki)7N.b(1-p)7

b(p,n=5)p3)(1-p)2)

P.reS.(nie wygenerowano liczb całkowitych)=1-7p3)(1-p)2)

Liczba bezużytecznych przewrotów będzie tutaj miała tendencję do

LiczyćreS.(bezużyteczne koziołki)5N.b[1-7p3)(1-p)2)]

ZAP.

LiczyćZAP.(bezużyteczne koziołki)<LiczyćreS.(bezużyteczne koziołki)

7N.b(1-p)7<5N.b[1-7p3)(1-p)2)]

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

p>0,0467ZAP. RNG generuje mniej bezużytecznych przewrotów.

pZAP.reS.p0,5967

LiczyćZAP.(bezużyteczne koziołki)LiczyćreS.(bezużyteczne koziołki)

0,67p=0,10,3p=0.20,127p=0,4


p(0,1)

1
@Sycorax Dodałem coś, chociaż nie jestem pewien, czy jest to zgodne z sugestiami.
Alecos Papadopoulos

H

1
12345679999999

1
p17p
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.