Brain teaser: Bagaimana cara menghasilkan 7 bilangan bulat dengan probabilitas yang sama menggunakan koin bias yang memiliki pr (head) = p?

58

Ini adalah pertanyaan yang saya temukan di Glassdoor : Bagaimana cara menghasilkan 7 bilangan bulat dengan probabilitas yang sama menggunakan koin yang memiliki ?Pr(Kepala)=hal(0,1)

Pada dasarnya, Anda memiliki koin yang mungkin atau mungkin tidak adil, dan ini adalah satu-satunya proses penghasil angka acak yang Anda miliki, jadi buatlah generator bilangan acak yang menghasilkan bilangan bulat dari 1 hingga 7 di mana kemungkinan mendapatkan masing-masing bilangan bulat ini adalah 1/7.

Efisiensi data-menghasilkan hal-hal proses.

Orang Amazon
sumber
12
Ada banyak cara untuk mencapai ini. Versi pertanyaan yang lebih menarik menanyakan metode terbaik dalam arti yang terdefinisi dengan baik. Rasa alami terbaik adalah jumlah flips yang diharapkan paling sedikit per bilangan bulat yang dihasilkan. Versi lain yang menarik adalah untuk menggambarkan semua solusi yang mungkin (yang bergantung pada flip independen dari koin dan tidak lebih).
Whuber
1
@whuber saran yang bagus, saya telah mengedit pertanyaan untuk mencerminkan komentar Anda.
Amazon
<<< Pada dasarnya, Anda memiliki koin yang mungkin atau mungkin tidak adil, dan ini adalah satu-satunya proses menghasilkan angka acak yang Anda miliki >>> Apakah ini berarti, menggunakan koin dalam metode yang berbeda dari membalik dan memeriksa kepala vs. ekor "dilarang", karena itu akan menjadi proses penghasil angka acak lainnya?
TinglTanglBob
9
Mod 7 tahun ini di koin.
Nat

Jawaban:

56

Balikkan koin dua kali. Jika itu mendarat HHatau TT, abaikan dan balikkan dua kali lagi.

Sekarang, koin memiliki probabilitas yang sama untuk muncul HTatau TH. Jika muncul HT, panggil ini H1. Jika muncul TH, panggil ini T1.

Terus dapatkan H1atau T1sampai Anda memiliki tiga berturut-turut. Tiga hasil ini memberi Anda angka berdasarkan tabel di bawah ini:

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]

Saya berpendapat bahwa ini akan bekerja dengan baik, meskipun Anda akan memiliki banyak lemparan yang sia-sia dalam prosesnya!

NcAdams
sumber
4
Satu-satunya kendala adalah bahwa probabilitas kepala adalah "p". Perhatikan bahwa p bisa , atau . Jadi ini tidak dijamin berhasil, tetapi milik Sycorax (atau Sephan) akan berhasil, bahkan dalam kasus-kasus itu. 101
gung - Reinstate Monica
8
@ungung: Saya tidak yakin saya akan bekerja untuk koin dengan dua kepala, atau dua ekor.
S. Kolassa - Reinstate Monica
6
Dengan probabilitas itu akan selesai dalam waktu yang terbatas. 1
clark
18
Ini disebut Von-Neuman whitening.
DonFusili
4
Anda dapat mengulangi ekstraktor von Neumann untuk mengekstraksi entropi lebih lengkap dari urutan. Kumpulkan semua pasangan HH dan TT, pertimbangkan urutan itu, terapkan von Neumann extractor untuk itu, dll.
A Simmons
47

Asumsikan .p(0,1)

Langkah 1: . Lempar koin 5 kali.

Jika hasilnya

1(H,H,H,T,T) , kembali dan berhenti.1

2(H,H,T,T,H) , kembali dan berhenti.2

3(H,T,T,H,H) , kembali dan berhenti.3

4(T,T,H,H,H) , kembali dan berhenti.4

5(T,H,H,H,T) , kembali dan berhenti.5

6(H,H,T,H,T) , kembali dan berhenti.6

7(H,T,H,T,H) , kembali dan berhenti.7

Langkah 2: . Jika hasilnya tidak ada di atas, ulangi Langkah 1.

Perhatikan bahwa terlepas dari nilai , masing-masing dari tujuh hasil yang tercantum di atas memiliki probabilitas , dan jumlah lemparan koin yang diharapkan adalah . Server tidak perlu mengetahui nilai (kecuali bahwa dan ); dijamin bahwa tujuh bilangan bulat memiliki kemungkinan yang sama untuk dikembalikan oleh percobaan ketika berakhir (dan dijamin berakhir dengan probabilitas ).q = p 3 ( 1 - p ) 2 5p(0,1)q=p3(1p)2 pp0p1157qpp0p11

Dilip Sarwate
sumber
6
Bisakah kita mengurangi jumlah lemparan yang diharapkan untuk ini dengan memungkinkan urutan yang ditentukan di sini ATAU urutan itu dengan setiap flip terbalik. misalnya: Untuk 1, baik (H, H, H, T, T) atau (T, T, T, H, H)?
moreON
5
Anda bisa menambahkan pelengkap juga. Jika hasilnya adalah (H, H, H, T, T) atau (T, T, T, H, H), kembalikan 1 dan berhenti, dll. Dalam hal itu probabilitas untuk setiap hasil adalah . q=p3(1p)2+p2(1p)3
Sextus Empiricus
2
Apakah tidak mungkin untuk hanya menambahkan koin-flip jika hasilnya tidak ada dalam pengaturan (H, H, H, T, T)? Dengan koin-lemparan tambahan Anda memerlukan pemetaan lain (H, H, H, T, T, T) dan (H, H, T, T, T, T) dan setiap kombinasi xT (7-x) H yang dapat diatur dalam 7 atau lebih pesanan yang berbeda ke angka 1 hingga 7. Alih-alih memasang kembali semua 5 koin ini akan menambah hanya 1 lemparan tambahan, tetapi saya tidak yakin apakah itu berhasil: D
TinglTanglBob
5
Mungkin itu mungkin hal terbaik untuk langsung melempar koin 7 kali, karena daripada yang dijamin, bahwa Anda akan mendapatkan nomor acak darinya (hanya pengecualian karena itu, bahwa koin mendarat ke atas atau mengikuti semua 7 percobaan) . Jadi dengan 7 kali lemparan, Anda bisa berakhir dengan 1 hingga 6 kepala (saya mengecualikan opsi 0 dan 7 di sini karena tidak ada gunanya). Jika satu kepala ada 7 pengaturan yang berbeda dari (H, T, T, T, T, T, T) mungkin; Jika 2 mengepalai 21 nya; jika 3 kepala 35 nya; jika 4 35 kepala; jika 5 21 kepala; jika 6 7 kepala; Masing-masing dapat dipetakan dengan sempurna ke nomor 1-7 tanpa kombinasi yang hilang.
TinglTanglBob
2
@TinglTanglBob Ini pada dasarnya adalah jawaban Martijn Weterings ;-)
M.Herzkamp
22

Generalisasi kasus yang dijelaskan oleh Dilip Sarwate

Beberapa metode yang dijelaskan dalam jawaban lain menggunakan skema di mana Anda melempar urutan n koin dalam 'belokan' dan tergantung pada hasil Anda memilih angka antara 1 atau 7 atau membuang belokan dan melempar lagi.

Kuncinya adalah menemukan dalam perluasan kemungkinan kelipatan 7 hasil dengan probabilitas yang sama pk(1p)nk dan mencocokkannya dengan satu sama lain.

Karena jumlah total hasil bukan kelipatan 7, kami memiliki beberapa hasil yang tidak dapat kami tetapkan ke suatu angka, dan memiliki beberapa probabilitas bahwa kami perlu membuang hasil dan memulai lagi.


Kasus menggunakan 7 koin membalik per giliran

Secara intuitif kita bisa mengatakan bahwa melempar dadu tujuh kali akan sangat menarik. Karena kita hanya perlu membuang 2 dari 27 kemungkinan. Yakni, 7 kali head dan 0 kali head.

Untuk semua kemungkinan selalu ada kelipatan 7 kasus dengan jumlah kepala yang sama. Yaitu 7 kasus dengan 1 kepala, 21 kasus dengan 2 kepala, 35 kasus dengan 3 kepala, 35 kasus dengan 4 kepala, 21 kasus dengan 5 kepala, dan 7 kasus dengan 6 kepala.272

Jadi jika Anda menghitung angka (membuang 0 kepala dan 7 kepala)

X=k=17(k1)Ck

dengan variabel terdistribusi Bernoulli (nilai 0 atau 1), maka X modulo 7 adalah variabel seragam dengan tujuh kemungkinan hasil.Ck


Membandingkan jumlah flips koin yang berbeda per giliran

Pertanyaannya adalah berapa jumlah gulungan optimal per giliran. Menggulirkan lebih banyak dadu per gilirannya akan membuat Anda lebih mahal, tetapi Anda mengurangi kemungkinan harus berguling lagi.

Gambar di bawah ini menunjukkan perhitungan manual untuk beberapa angka pertama flips koin per giliran. (mungkin mungkin ada solusi analitis, tapi saya yakin aman untuk mengatakan bahwa sistem dengan 7 membalik koin memberikan metode terbaik mengenai nilai ekspektasi untuk jumlah membalik koin yang diperlukan)

jumlah koin yang diharapkan terlontar

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

Menggunakan aturan penghentian awal

catatan: perhitungan di bawah ini, untuk nilai ekspektasi jumlah flips, adalah untuk koin yang adil , itu akan menjadi berantakan untuk melakukan hal ini untuk berbeda , tetapi prinsipnya tetap sama (meskipun pembukuan yang berbeda dari kasus diperlukan)p=0.5p

Kita harus bisa memilih kasing (bukan rumus untuk ) sehingga kita bisa berhenti lebih awal.X

  • Dengan 5 koin membalik kita miliki untuk enam set kepala dan ekor yang tidak berurutan yang berbeda:

    1 + 5 + 10 + 10 + 5 + 1 set yang dipesan

    Dan kita dapat menggunakan kelompok dengan sepuluh kasus (yaitu kelompok dengan 2 kepala atau kelompok dengan 2 ekor) untuk memilih (dengan probabilitas yang sama) angka. Ini terjadi pada 14 dari 2 ^ 5 = 32 kasus. Ini membuat kita dengan:

    1 + 5 + 3 + 3 + 5 + 1 set yang dipesan

  • Dengan flip koin ekstra (6-th) yang kami miliki untuk tujuh set kepala dan ekor unordered yang berbeda:

    1 + 6 + 8 + 6 + 8 + 6 + 1 set yang dipesan

    Dan kita dapat menggunakan kelompok dengan delapan kasus (yaitu kelompok dengan 3 kepala atau kelompok dengan 3 ekor) untuk memilih (dengan probabilitas yang sama) angka. Ini terjadi pada 14 dari 2 * (2 ^ 5-14) = 36 kasus. Ini membuat kita dengan:

    1 + 6 + 1 + 6 + 1 + 6 + 1 set yang dipesan

  • Dengan flip koin ekstra lain (7-th) yang kami miliki untuk delapan set kepala dan ekor unordered yang berbeda:

    1 + 7 + 7 + 7 + 7 + 7 + 7 + 1 set yang dipesan

    Dan kita dapat menggunakan kelompok dengan tujuh kasus (semua kecuali semua ekor dan semua kasus kepala) untuk memilih (dengan probabilitas yang sama) angka. Ini terjadi pada 42 dari 44 kasus. Ini membuat kita dengan:

    1 + 0 + 0 + 0 + 0 + 0 + 0 + 1 set pesanan

    (kita bisa melanjutkan ini tetapi hanya pada langkah ke-49 hal ini memberi kita keuntungan)

Jadi probabilitas untuk memilih nomor

  • pada 5 membalik adalah 1432=716
  • pada 6 membalik adalah 9161436=732
  • pada 7 membalik adalah 11324244=231704
  • tidak dalam 7 membalik adalah 1716732231704=227

Ini membuat nilai ekspektasi untuk jumlah flips dalam satu giliran, dengan syarat bahwa ada keberhasilan dan p = 0,5:

5716+6732+7231704=5.796875

Nilai ekspektasi untuk jumlah total flips (sampai ada keberhasilan), dengan syarat bahwa p = 0,5, menjadi:

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


Jawaban oleh NcAdams menggunakan variasi dari strategi stopping-rule ini (setiap kali menghasilkan dua flips koin baru) tetapi tidak secara optimal memilih semua flips.

Jawaban oleh Clid mungkin serupa juga walaupun mungkin ada aturan pemilihan yang tidak rata bahwa masing-masing dua koin membalik nomor mungkin dipilih tetapi tidak harus dengan probabilitas yang sama (perbedaan yang sedang diperbaiki selama membalik koin kemudian)


Perbandingan dengan metode lain

Metode lain yang menggunakan prinsip serupa adalah yang dilakukan oleh NcAdams dan AdamO.

Prinsipnya adalah : Keputusan untuk angka antara 1 dan 7 dibuat setelah sejumlah kepala dan ekor. Setelah jumlah x membalik, untuk setiap keputusan yang mengarah ke nomor i ada keputusan yang sama, kemungkinan sama, yang mengarah ke nomor j (jumlah kepala dan ekor yang sama tetapi hanya dalam urutan yang berbeda). Beberapa seri kepala dan ekor dapat mengarah pada keputusan untuk memulai kembali.

Untuk jenis metode seperti itu, yang ditempatkan di sini adalah yang paling efisien karena membuat keputusan sedini mungkin (segera setelah ada kemungkinan untuk 7 urutan probabilitas kepala dan ekor yang sama, setelah flip ke- x , kita dapat menggunakan mereka untuk membuat keputusan pada nomor dan kita tidak perlu membalik lebih jauh jika kita menemukan salah satu dari kasus-kasus itu).

Ini ditunjukkan oleh gambar dan simulasi di bawah ini:

perbandingan

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

gambar lain yang diskalakan dengan p(1p) untuk perbandingan yang lebih baik:

perbandingan dengan nilai ekspektasi yang diskalakan

perbesar metode perbandingan yang dijelaskan dalam pos dan komentar ini

metode perbandingan yang dijelaskan di sini

'lompatan bersyarat dari langkah ke-7' adalah sedikit perbaikan yang dapat dilakukan pada aturan penghentian awal. Dalam hal ini Anda memilih bukan grup dengan probabilitas yang sama setelah membalik ke-6. Anda memiliki 6 grup dengan probabilitas yang sama, dan 1 grup dengan probabilitas yang sedikit berbeda (untuk grup terakhir ini Anda perlu membalik satu kali lagi ketika Anda memiliki 6 kepala atau ekor dan karena Anda membuang 7 kepala atau 7 ekor, Anda akan berakhir setelah itu dengan probabilitas yang sama)


Ditulis oleh StackExchangeStrike

Sextus Empiricus
sumber
Saya baru saja mulai membuat perhitungan untuk kasus n = 7, karena saya merasa mungkin lebih baik daripada n = 1. Terima kasih, tuan!
M.Herzkamp
CkX
Jadi peningkatan membawanya ke sedikit lebih dari 6 membalik koin sebagai nilai ekspektasi untuk jumlah membalik koin yang diperlukan. Akan bervariasi walaupun untuk membuktikan bahwa ini adalah solusi optimal. Skema yang dibuat oleh Clid agak menyimpang yang memungkinkan untuk memilih nomor pada sejumlah koin tertentu tetapi tidak dengan probabilitas yang sama (setidaknya tidak untuk langkah tertentu, itu akan diperbaiki kemudian).
Sextus Empiricus
Tetapi jika Anda memutuskan untuk membalik koin keenam berdasarkan lima hasil pertama, apakah probabilitas masing-masing set, dikondisikan pada Anda mendapat enam membalik, sama seperti untuk set lainnya?
Akumulasi
@Accumulation Anda bisa menggambarnya sebagai pohon biner dengan 7 level. Kami hanya akan memilih di antara node jika ada 7 dengan probabilitas yang sama. Ini seperti Anda memotong beberapa cabang sebelumnya (pada level 5 atau 6). Jika Anda suka maka Anda dapat melanjutkan sampai 7 langkah, bukan sebelumnya, tetapi untuk kasus-kasus tertentu flip koin 6 dan 7 tidak membuat perbedaan.
Sextus Empiricus
20

Bagilah kotak menjadi tujuh wilayah dengan luas yang sama, masing-masing diberi label dengan bilangan bulat. Lempar koin ke dalam kotak sedemikian rupa sehingga memiliki kemungkinan pendaratan yang sama di setiap wilayah.

π

p=1p=0

Pasang kembali Monica
sumber
2
Dapatkah Anda menyarankan cara untuk membagi kotak menjadi tujuh wilayah dengan luas yang sama, untuk meminimalkan bias dari membalik, memantul dinding dll? Tujuh sektor sudut 360/7?
smci
1
@smci Itu sebabnya saya menetapkan bahwa Anda harus melempar koin sehingga ada kemungkinan seragam untuk mendarat di setiap kotak. Jika memantul dari dinding memengaruhi probabilitas itu, maka Anda harus memperhitungkannya dalam lemparan Anda.
Pasang kembali Monica
17
Ya saya tahu itu, dan saya menunjukkan kepada Anda bahwa hanya mengatakan "membuangnya dengan cara yang tidak memihak" tanpa mendefinisikan secara tepat bagaimana mencapai itu, sebenarnya bukan jawaban penuh ... dalam hal ini flipping-H / T metode berbasis lebih unggul.
smci
1
"Area yang sama, dengan lemparan yang memiliki probabilitas pendaratan yang sama di setiap wilayah" mungkin sulit ditentukan dalam praktiknya. Dalam praktik mungkin akan lebih mudah untuk menandai sejumlah besar "latihan lari" dan kemudian membagi area pendaratan menjadi ruang yang dapat dilengkapi secara empiris (misalnya dengan 700 lemparan, menyingkirkan garis yang memotong 100 lemparan terjauh, lalu satu lagi untuk yang berikutnya) 100 dan seterusnya). Penyederhanaan ini untuk menghasilkan bit acak tunggal akan membuang koin dua kali - jika lemparan pertama lebih jauh, bit adalah 0, dan jika lemparan kedua melangkah lebih jauh itu adalah1
Silverfish
4
Ada jawaban yang bagus oleh @TheScienceBoy yang sayangnya dihapus dengan alternatif yang menarik untuk ini - secara efektif, menggunakan koin sebagai pemintal, dan menandai 7 bagian sepanjang kelilingnya - yang mempertahankan banyak semangat jawaban ini tetapi secara fisik lebih mudah secara langsung untuk dilakukan!
Silverfish
8

EDIT: berdasarkan umpan balik orang lain.

Inilah pemikiran yang menarik:

atur daftar {1,2,3,4,5,6,7}. Lempar koin untuk setiap elemen dalam daftar secara berurutan. Jika kepala mengarah ke atas untuk elemen tertentu, hapus nomor dari daftar. Jika semua angka dari iterasi tertentu dari daftar dihapus, ulangi pengambilan sampel. Lakukan sampai hanya satu nomor yang tersisa.

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)

memberi saya distribusi sekitar seragam

> 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


Evaluasi nilai ekspektasi untuk jumlah lemparan koin

xy

M=[q700000117p1q6q600000021p2q56p1q5q50000035p3q415p2q45q4q4000035p4q320p3q310p2q34p1q3q300021p5q215p4q210p3q26p2q23p1q2q2007p6q16p5q15p4q14p3q13p2q12p1q100p7p6p5p4p3p200]

(MI)v=0

E(n)=247p(1p)

perbandingan nilai ekspektasi untuk flips koin

p>2/3

Solusi ditemukan dengan 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);

Perhitungan dalam 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
sumber
1
Gagasan pintar (+1). Secara intuitif, itu harus bekerja, karena simetri akan muncul untuk meniadakan bias terhadap angka tertentu. Tetap saja, saya ingin sekali melihat bukti.
Pasang kembali Monica
6
Ide ini benar-benar bagus, tetapi dengan probabilitas tinggi untuk head (merobohkan angka itu) saya pikir angka terakhir dalam barisan memiliki peluang terbaik untuk "bertahan" karena semua yang lain dihadang karena kemungkinan ditendang sebelum menjalankan 1? Mungkin bisa diubah dengan tidak melempar koin secara berurutan tetapi sejajar untuk semua angka dalam x? Runtime dari script mungkin meningkat saya kira :)
TinglTanglBob
2
Saya setuju dengan @TinglTanglBob - ketika saya mengatur p <- 0.99saya mendapatkan hasilnya0.89 0.02 0.02 0.02 0.02 0.02 0.02
Silverfish
6
Tidakkah melakukan eliminasi dalam 'putaran' memperbaiki masalah bias? Mulai dengan 7 angka. Lempar koin untuk setiap angka yang tersisa, dan hilangkan yang melempar kepala. Jika semua angka yang tersisa dihilangkan dalam satu putaran, gores hasil dari putaran itu dan coba lagi. Saya tidak tahu bagaimana membuktikannya, tetapi secara intuitif urutan angka tidak lagi penting apakah mereka adalah 'pemenang'
Phil
1
p=0.01
5

Pertanyaannya agak ambigu, apakah ia bertanya "menghasilkan bilangan bulat acak sama atau kurang dari 7 dengan probabilitas sama", atau apakah ia bertanya "menghasilkan 7 bilangan bulat acak dengan probabilitas sama?" - tapi apa ruang bilangan bulat?!?

Saya akan berasumsi itu yang pertama, tetapi logika yang sama yang saya terapkan dapat diperluas ke kasus yang terakhir juga, setelah masalah itu diselesaikan.

Dengan koin bias, Anda dapat menghasilkan koin yang adil dengan mengikuti prosedur berikut: https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_ gantung_coin

Angka 7 atau kurang dapat ditulis dalam biner sebagai tiga {0,1} digit. Jadi yang perlu dilakukan adalah mengikuti prosedur di atas tiga kali, dan mengonversi angka biner yang dihasilkan menjadi desimal.

Cam.Davidson.Pilon
sumber
1
membandingkan jawaban saya dengan @NcAdams, jelas saya menyertakan 0 sebagai hasil yang diinginkan!
Cam.Davidson.Pilon
Saya tidak mengerti bagaimana jawaban Anda berbeda. Jika Anda memasukkan {0,0,0} -> 1 lalu apa yang dipetakan {1,1,1}? Ada 8 kemungkinan.
AdamO
1
000 peta ke 0, maka komentar saya tentang memasukkan 0 sebagai nilai yang mungkin. Ini diposting sebelum OP mengedit dan hampir bersamaan sebagai NcAdams.
Cam.Davidson.Pilon
Separuh dari jawaban ini adalah komentar, dan konten sebenarnya dari jawaban tersebut adalah tautan saja. Harap sebutkan jawaban Anda yang sebenarnya daripada hanya menautkannya.
Cubic
3

Sebuah solusi yang tidak pernah membuang membalik, yang banyak membantu untuk koin yang sangat bias.

Kerugian dari algoritma ini (seperti yang ditulis, setidaknya) adalah bahwa ia menggunakan aritmatika presisi arbitrer. Secara praktis, Anda mungkin ingin menggunakan ini sampai integer overflow, dan hanya kemudian membuangnya dan memulai lagi.

Juga, Anda perlu tahu apa bias adalah ... yang Anda mungkin tidak, katakanlah, jika suhu tergantung seperti fenomena fisik yang paling.


Dengan asumsi peluang kepala, katakanlah, 30%.

  • Mulai dengan kisaran [1, 8).
  • Balikkan koin Anda. Jika menuju, gunakan 30% kiri, jadi rentang baru Anda [1, 3.1). Lain, gunakan 70% yang tepat, jadi rentang baru Anda [3.1, 8).
  • Ulangi sampai seluruh rentang memiliki bagian integer yang sama.

Kode lengkap:

#!/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
sumber
3
[0,1]00006666k
Itu sama untuk satu output, kan? Lebih baik untuk banyak? Saya akan menulis seperti yang diff *= 7saya pikirkan ... pada kenyataannya, tidak ada kebutuhan khusus untuk menggunakan basis yang sama untuk setiap upaya.
o11c
Ya, sama saja jika Anda menginginkan satu output; itu hanya meningkatkan efisiensi jika Anda ingin yang lebih banyak.
Federico Poloni
pp
Ini benar-benar membuang limbah jika Anda menginginkan satu output. Untuk koin yang adil, teknik standar (gulung koin tiga kali, dan ulangi jika Anda mendapatkan TTT) memberikan jumlah yang diharapkan 24/7 = 3 + 3/7 gulungan. Jika Anda menggunakan teknik gaya pengkodean aritmatika ini, Anda menggulung setidaknya empat kali kecuali Anda mendapatkan HHH atau TTT, yang memberi Anda jumlah yang diharapkan lebih dari 15/4 = 3 + 3/4 gulungan.
Peter Shor
3

Seperti disebutkan dalam komentar sebelumnya, teka-teki ini berkaitan dengan makalah John von Neumann tahun 1951 "Berbagai Teknik yang Digunakan Sehubungan dengan Digit Acak" yang diterbitkan dalam jurnal penelitian National Bureau of Standards:

masukkan deskripsi gambar di sini

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

Xi'an
sumber
2

p1p0

Kami pertama-tama mengubah (mungkin) koin yang tidak adil menjadi koin yang adil menggunakan proses dari jawaban NcAdams :

Balikkan koin dua kali. Jika itu mendarat HHatau TT, abaikan dan balikkan dua kali lagi.

Sekarang, koin memiliki probabilitas yang sama untuk muncul HTatau TH. Jika muncul HT, panggil ini H1. Jika muncul TH, panggil ini 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
sumber
1
1/7
1
1/7k=1(1/8)k=17
1
nT(n)=2n62nn3
3+n=31T(n)=4.5
8733.42
2

Terinspirasi oleh jawaban AdamO, berikut adalah solusi Python yang menghindari bias:

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

Ada dua perubahan utama di sini: Yang utama adalah jika semua nomor dibuang dalam satu putaran, ulangi putaran itu. Saya juga membalik pilihan apakah kepala atau ekor berarti membuang setiap waktu. Ini mengurangi jumlah flips yang dibutuhkan dalam kasus di mana p mendekati 0 atau 1 hingga ~ 70% ketika p = 0,999

Phil
sumber
2
"Saya membalik pilihan apakah kepala atau ekor berarti membuang setiap waktu. Ini mengurangi jumlah flips yang dibutuhkan dalam kasus di mana p mendekati 0 atau 1 hingga ~ 70% ketika p = 0,999" - pemikiran cerdas!
Silverfish
1
Kepala atau ekor yang berganti-ganti jelas merupakan peningkatan dari pada selalu membuang kepala - tetapi mungkin akan lebih baik jika, setelah membalik koin untuk setiap opsi yang tersisa, jika semuanya sama kita ulangi refleksikan semuanya, jika tidak setidaknya ada sebanyak kepala sebagai ekor kita menghilangkan opsi yang tersisa sesuai dengan kepala, jika tidak kita menghilangkan opsi yang tersisa sesuai dengan ekor.
David Cary
2

Tampaknya kita diizinkan untuk mengubah pemetaan hasil setiap flip, setiap kali kita flip . Jadi, untuk kenyamanan tujuh bilangan bulat positif pertama, kami memberikan perintah berikut:

H1
H2

H7
H1

dll

T


APT

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

Nb

MenghitungSEBUAHP(membalik tidak berguna)7Nb(1-hal)7

B(hal,n=5)hal3(1-hal)2

PDS(tidak ada bilangan bulat yang dihasilkan)=1-7hal3(1-hal)2

Hitungan flips yang tidak berguna di sini akan cenderung

MenghitungDS(membalik tidak berguna)5Nb[1-7hal3(1-hal)2]

SEBUAHP

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
sumber
p(0,1)
1
@ Scorax Saya menambahkan sesuatu, meskipun saya tidak yakin itu sesuai dengan saran Anda.
Alecos Papadopoulos
H
1
12345679999999
1
p17p