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( 1 - p )n - k 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 2)7 możliwości. Mianowicie 7 razy głowy i 0 razy głowy.
Dla wszystkich pozostałych 2)7- 2 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(k−1)⋅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ą)
# 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 1−716−732−231704=227
To sprawia, że wartość oczekiwana dla liczby przerzutów w jednej turze jest uzależniona od powodzenia, a p = 0,5:
5⋅716+6⋅732+7⋅231704=5.796875
Wartość oczekiwana dla całkowitej liczby przewrotów (do momentu sukcesu), pod warunkiem, że p = 0,5, staje się:
(5⋅716+6⋅732+7⋅231704)2727−2=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:
#### 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∗(1−p) dla lepszego porównania:
powiększyć metody porównywania opisane w tym poście i komentarzach
„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