Probabilitas serangkaian k berhasil dalam serangkaian uji coba Bernoulli

Saya mencoba untuk menemukan kemungkinan mendapatkan 8 percobaan berturut-turut dalam satu blok dengan 25 percobaan, Anda memiliki 8 total blok (dari 25 percobaan) untuk mendapatkan 8 percobaan yang benar dalam satu baris. Probabilitas untuk mendapatkan percobaan yang benar berdasarkan menebak adalah 1/3, setelah mendapatkan 8 berturut-turut koreksi blok akan berakhir (jadi mendapatkan lebih dari 8 berturut-turut benar secara teknis tidak mungkin). Bagaimana saya mencari peluang terjadinya ini? Saya telah berpikir sepanjang garis menggunakan (1/3) ^ 8 sebagai kemungkinan mendapatkan 8 berturut-turut yang benar, ada 17 kemungkinan untuk mendapatkan 8 berturut-turut dalam blok 25 percobaan, jika saya kalikan 17 kemungkinan * 8 blok saya dapat 136, apakah 1- (1- (1/3) ^ 8) ^ 136 memberi saya kemungkinan mendapatkan 8 berturut-turut dengan benar dalam situasi ini atau saya kehilangan sesuatu yang mendasar di sini?

Dengan melacak hal-hal yang Anda bisa dapatkan formula yang tepat .

Biarkan $p=1/3$ adalah probabilitas keberhasilan dan $k=8$ menjadi jumlah keberhasilan berturut-turut Anda ingin menghitung. Ini diperbaiki untuk masalah ini. Nilai variabel adalah $m$ , jumlah uji coba yang tersisa di blok; dan $j$ , jumlah keberhasilan berturut-turut sudah diamati. Biarkan kesempatan akhirnya mencapai $k$ keberhasilan berturut-turut sebelum $m$ percobaan yang be kelelahan ditulis $f_{p,k}(j,m)$ . Kami mencari $f_{1/3,8}(0,25)$ .

Misalkan kita baru saja melihat kami $j^\text{th}$ sukses berturut-turut dengan $m\gt0$ uji coba untuk pergi. Percobaan berikutnya adalah sukses, dengan probabilitas $p$ - dalam kasus $j$ meningkat menjadi $j+1$ -; atau jika tidak, dengan probabilitas $1-p$ --dalam kasus $j$ diatur ulang ke $0$ . Dalam kedua kasus tersebut,$m$ berkurang sebesar$1$ . Dari mana

$$f_{p,k}(j,m) = p f_{p,k}(j+1,m-1) + (1-p)f_{p,k}(0,m-1).$$

Seperti kondisi mulai kita memiliki hasil yang jelas $f_{p,k}(k,m)=1$ untuk $m \ge 0$ ( yaitu , kita telah melihat $k$ berturut-turut) dan $f_{p,k}(j,m)=0$ untuk $k-j \gt m$ ( yaitu , tidak ada cukup percobaan yang tersisa untuk mendapatkan $k$berturut-turut). Sekarang cepat dan mudah (menggunakan pemrograman dinamis atau, karena parameter masalah ini sangat kecil, rekursi) untuk menghitung

$$f_{p,8}(0,25) = 18p^8 - 17p^9 - 45p^{16} + 81p^{17}-36p^{18}.$$

Ketika hasil ini$p=1/3$ .$80897 / 43046721 \approx 0.0018793$

RKode yang relatif cepat untuk mensimulasikan ini

hits8 <- function() {
    x <- rbinom(26, 1, 1/3)                # 25 Binomial trials
    x[1] <- 0                              # ... and a 0 to get started with `diff`
    if(sum(x) >= 8) {                      # Are there at least 8 successes?
        max(diff(cumsum(x), lag=8)) >= 8   # Are there 8 successes in a row anywhere?
    } else {
        FALSE                              # Not enough successes for 8 in a row
    }
}
set.seed(17)
mean(replicate(10^5, hits8()))

Setelah 3 detik perhitungan, hasilnya adalah . Meskipun ini terlihat tinggi, ini hanya 1,7 kesalahan standar. Saya menjalankan 10 6 iterasi lain, menghasilkan 0,001867 : saja$0.00213$$10^6$$0.001867$ kesalahan standar kurang dari yang diharapkan. (Sebagai pemeriksaan ulang, karena versi sebelumnya dari kode ini memiliki bug yang halus, saya juga menjalankan 400.000 iterasi diMathematica,memperoleh perkiraan 0,0018475 .)$0.3$$0.0018475$

Hasil ini kurang dari sepersepuluh perkiraan dalam pertanyaan. Tapi mungkin saya belum sepenuhnya dipahami itu: interpretasi lain dari "Anda memiliki 8 Total blok ... untuk mendapatkan 8 uji coba memperbaiki berturut-turut" adalah bahwa jawaban makhluk dicari sama dengan 1 - ( 1 - f 1 / 3 , 8 ( 0 , 25 ) ) 8 ) = 0,0149358 ... .$1-(1-(1/3)^8)^{136} \approx 0.0205$$1 - (1 - f_{1/3,8}(0,25))^8) = 0.0149358...$

Sementara solusi pemrograman dinamis @ whuber yang sangat baik layak dibaca, runtime-nya adalah sehubungan dengan jumlah total percobaan m dan panjang percobaan yang diinginkan k sedangkan metode matriks eksponensial adalah O ( k 3 log ( m ) ) . Jika m jauh lebih besar dari k , metode berikut ini lebih cepat.$\mathcal O(k^2m)$$m$$k$$\mathcal O(k^3\log(m))$$m$$k$

Kedua solusi menganggap masalah sebagai rantai Markov dengan negara yang mewakili jumlah uji coba yang benar pada akhir string sejauh ini, dan negara untuk mencapai uji coba yang benar yang diinginkan secara berturut-turut. Matriks transisi sedemikian rupa sehingga melihat kegagalan dengan probabilitas mengirim Anda kembali ke status 0, dan sebaliknya dengan probabilitas 1 - p memajukan Anda ke keadaan berikutnya (keadaan akhir adalah keadaan menyerap). Dengan menaikkan matriks ini ke kekuatan ke- n , nilai pada baris pertama, dan kolom terakhir adalah probabilitas untuk melihat k = 8 head dalam satu baris. Dengan Python:$p$$1-p$$n$$k=8$

import numpy as np

def heads_in_a_row(flips, p, want):
    a = np.zeros((want + 1, want + 1))
    for i in range(want):
        a[i, 0] = 1 - p
        a[i, i + 1] = p
    a[want, want] = 1.0
    return np.linalg.matrix_power(a, flips)[0, want]

print(heads_in_a_row(flips=25, p=1.0 / 3.0, want=8))

menghasilkan 0,00187928367413 seperti yang diinginkan.

Menurut jawaban ini , saya akan menjelaskan pendekatan Markov-Chain oleh @Neil G sedikit lebih banyak dan memberikan solusi umum untuk masalah seperti di R. Mari kita tunjukkan jumlah percobaan yang benar yang diinginkan secara berturut-turut oleh , jumlah percobaan sebagai n dan percobaan yang benar oleh W (menang) dan percobaan yang salah oleh F (gagal). Dalam proses melacak uji coba, Anda ingin tahu apakah Anda sudah memiliki 8 uji coba yang benar dan jumlah uji coba yang benar di akhir urutan Anda saat ini. Ada 9 negara ( k + $k$$n$$W$$F$$k+1$ ):

: Kami belum punya 8 uji coba yang benar berturut-turut belum, dan sidang terakhir adalah F .$A$$8$$F$

: Kami belum punya 8 uji coba yang benar berturut-turut belum, dan dua uji coba terakhir adalah F $B$$8$$FW$ .

: Kami belum punya 8 uji coba yang benar berturut-turut belum, dan tiga uji coba terakhir adalah F W W .$C$$8$$FWW$

$\ldots$

$H$ : Kami belum punya uji coba yang benar berturut-turut belum, dan delapan uji coba terakhir adalah F W W W W W W W .$8$$FWWWWWWW$

: Kami sudah$I$$8$ percobaan yang benar berturut-turut!

Probabilitas pindah ke negara bagian dari negara A adalah p = 1 / 3 dan dengan probabilitas 1 - p = 2 / 3 kita tinggal di negara A . Dari negara B , kemungkinan pindah ke negara bagian C adalah 1 / 3 dan dengan probabilitas 2 / 3 kita bergerak kembali ke A . Dan seterusnya. Jika kita dalam keadaan I , kita tinggal di sana.$B$$A$$p=1/3$$1-p=2/3$$A$$B$$C$$1/3$$2/3$$A$$I$

Dari ini, kita dapat membangun transisi matriks M (karena setiap kolom M jumlah untuk 1 dan semua entri yang positif, M disebut matriks stokastik kiri ):$9\times9$ $M$$M$$1$$M$

$$M= \begin{pmatrix} 2/3 & 2/3 & 2/3 & 2/3 & 2/3 & 2/3 & 2/3 & 2/3 & 0 \\ 1/3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1/3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1/3 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1/3 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1/3 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1/3 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1/3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1/3 & 1 \end{pmatrix}$$

$n$$M^{n}$$j$$i$$n$ trials. The rightmost column corresponds to the state $I$ and the only entry is $1$ in the right lower corner. This means that once we are in state $I$, the probability to stay in $I$ is $1$. We are interested in the probability of getting to state $I$ from state $A$ in $n=25$ steps which corresponds to the lower left entry of $M^{25}$$M^{25}_{91}$). All we have to do now is calculating $M^{25}$. We can do that in R with the matrix power function from the expm package:

library(expm)

k <- 8   # desired number of correct trials in a row
p <- 1/3 # probability of getting a correct trial
n <- 25  # Total number of trials 

# Set up the transition matrix M

M <- matrix(0, k+1, k+1)

M[ 1, 1:k ] <- (1-p)

M[ k+1, k+1 ] <- 1

for( i in 2:(k+1) ) {

  M[i, i-1] <- p

}

# Name the columns and rows according to the states (A-I)

colnames(M) <- rownames(M) <- LETTERS[ 1:(k+1) ]

round(M,2)

     A    B    C    D    E    F    G    H I
A 0.67 0.67 0.67 0.67 0.67 0.67 0.67 0.67 0
B 0.33 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0
C 0.00 0.33 0.00 0.00 0.00 0.00 0.00 0.00 0
D 0.00 0.00 0.33 0.00 0.00 0.00 0.00 0.00 0
E 0.00 0.00 0.00 0.33 0.00 0.00 0.00 0.00 0
F 0.00 0.00 0.00 0.00 0.33 0.00 0.00 0.00 0
G 0.00 0.00 0.00 0.00 0.00 0.33 0.00 0.00 0
H 0.00 0.00 0.00 0.00 0.00 0.00 0.33 0.00 0
I 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.33 1

# Calculate M^25

Mn <- M%^%n
Mn[ (k+1), 1 ]
[1] 0.001879284

The probability of getting from state $A$ to state $I$ in 25 steps is $0.001879284$, as established by the other answers.

Here is some R code that I wrote to simulate this:

tmpfun <- function() {
     x <- rbinom(25, 1, 1/3)  
     rx <- rle(x)
     any( rx$lengths[ rx$values==1 ] >= 8 )
}

tmpfun2 <- function() {
    any( replicate(8, tmpfun()) )
}

mean(replicate(100000, tmpfun2()))

I am getting values a little smaller than your formula, so one of us may have made a mistake somewhere.

Here is a Mathematica simulation for the Markov chain approach, note that Mathematica indexes by $1$ not $0$:

M = Table[e[i, j] /. {
    e[9, 1] :> 0,
    e[9, 9] :> 1,
    e[_, 1] :> (1 - p),
    e[_, _] /; j == i + 1 :> p,
    e[_, _] :> 0
  }, {i, 1, 9}, {j, 1, 9}];

x = MatrixPower[M, 25][[1, 9]] // Expand

This would yield the analytical answer:

$$18 p^8 - 17 p^9 - 45 p^{16} + 81 p^{17} - 36 p^{18}$$

Evaluating at $p=\frac{1.0}{3.0}$

x /. p -> 1/3 // N

Will return $0.00187928$

This can also be evaluated directly using builtin Probability and DiscreteMarkovProcess Mathematica functions:

Probability[k[25] == 9, Distributed[k, DiscreteMarkovProcess[1, M /. p -> 1/3]]] // N

Which will get us the same answer: $0.00187928$