Probabilidade de uma série de k sucessos em uma sequência de n ensaios de Bernoulli

13

Estou tentando encontrar a probabilidade de obter 8 tentativas consecutivas corretas em um bloco de 25 tentativas, você tem 8 bloqueios totais (de 25 tentativas) para obter 8 tentativas corretas consecutivas. A probabilidade de acertar qualquer tentativa com base em adivinhação é 1/3, depois de corrigir 8 em linha, os blocos terminam (portanto, tecnicamente, não é possível obter mais de 8 em linha). Como eu iria encontrar a probabilidade de isso ocorrer? Eu tenho pensado ao longo das linhas de usar (1/3) ^ 8 como a probabilidade de obter 8 em linha correta, existem 17 chances possíveis de obter 8 em linha em um bloco de 25 tentativas, se eu multiplicar 17 possibilidades * 8 blocos que recebo 136, 1- (1- (1/3) ^ 8) ^ 136 me daria a probabilidade de obter 8 em linha correta nesta situação ou estou perdendo algo fundamental aqui?

AcidNynex
fonte
1
Acredito que o problema com o argumento apresentado é que os eventos considerados não são independentes. Por exemplo, considere um único bloco. Se eu te disser que (a) não há prazo de oito que começa na posição 6, (b) não é uma corrida começando na posição 7 e (c) não existe um prazo que começa na posição 8, o que é que isso lhe diz sobre a probabilidade de uma corrida começando nas posições, digamos, 9 a 15?
cardeal

Respostas:

14

Ao acompanhar as coisas, você pode obter uma fórmula exata .

Deixe p=1/3 a probabilidade de sucesso e k=8 ser o número de sucessos em uma linha você deseja contar. Eles foram corrigidos para o problema. Os valores variáveis ​​são m , o número de tentativas restantes no bloco; e j , o número de sucessos sucessivos já observados. Deixe a chance de, eventualmente, alcançar k sucessos seguidos antes que m tentativas sejam esgotadas, seja escrita fp,k(j,m) . Procuramos f1/3,8(0,25) .

Suponha que acabamos de ver nosso jth sucesso em uma linha com m>0 ensaios de ir. O próximo julgamento é um sucesso, com probabilidade p - nesse caso, j é aumentado para j+1 -; ou então é uma falha, com probabilidade 1p - nesse caso j é redefinido para 0 . Nos dois casos, m diminui em 1 . De onde

fp,k(j,m)=pfp,k(j+1,m1)+(1p)fp,k(0,m1).

Como condições iniciais, temos os resultados óbvios para m 0 ( isto é , já vimos k em uma linha) ef p , k ( j , m ) = 0 para k - j > m ( ou seja , não há testes suficientes para obter kfp,k(k,m)=1m0kfp,k(j,m)=0kj>mkseguidas). Agora é rápido e direto (usando programação dinâmica ou, porque os parâmetros deste problema são muito pequenos, recursão) calcular

fp,8(0,25)=18p817p945p16+81p1736p18.

Quando esta rendimentos 80897 / 43046721 0,0018793p=1/380897/430467210.0018793 .

Um Rcódigo relativamente rápido para simular isso é

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

Após 3 segundos de cálculo, a saída é . Embora isso pareça alto, são apenas 1,7 erros padrão desativados. Executei outras 10 6 iterações, produzindo 0,001867 : apenas 0,3 erros padrão abaixo do esperado. (Como checagem dupla, como uma versão anterior desse código tinha um bug sutil, também executei 400.000 iterações no Mathematica, obtendo uma estimativa de 0,00184750.002131060.0018670.30.0018475 .)

Este resultado é menos do que um décimo da estimativa de em questão. Mas talvez eu não tenha entendido integralmente lo: uma outra interpretação de "você tem 8 total de blocos ... para obter 8 ensaios corrigir em uma linha" é que o ser resposta procurada iguais 1 - ( 1 - f 1 / 3 , 8 ( 0 , 25 ) ) 8 ) = 0,0149358 ... .1(1(1/3)8)1360.02051(1f1/3,8(0,25))8)=0.0149358...

whuber
fonte
13

Embora a excelente solução de programação dinâmica da @ whuber valha a pena ser lida, seu tempo de execução é O(k2m) with respect to total number of trials m and the desired trial length k whereas the matrix exponentiation method is O(k3log(m)). If m is much larger than k, the following method is faster.

Ambas as soluções consideram o problema como uma cadeia de Markov com estados representando o número de tentativas corretas no final da cadeia até agora e um estado para alcançar as tentativas corretas desejadas seguidas. A matriz de transição é tal que ver uma falha com probabilidade envia de volta ao estado 0 e, caso contrário, com a probabilidade 1 - p avança para o próximo estado (o estado final é um estado absorvente). Ao elevar esta matriz para o n ° de potência, o valor na primeira fila, e a última coluna é a probabilidade de ver k = 8 cabeças em uma fileira. Em Python:p1pnk=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))

produz 0,00187928367413 conforme desejado.

Neil G
fonte
10

De acordo com esta resposta , explicarei um pouco mais a abordagem de Markov-Chain por @Neil G e fornecerei uma solução geral para esses problemas R. Vamos denotar o número desejado de tentativas corretas seguidas de , o número de tentativas como ne uma tentativa correta de W (vitória) e uma tentativa incorreta de F (falha). No processo de acompanhar as tentativas, você deseja saber se você já teve uma sequência de 8 tentativas corretas e o número de tentativas corretas no final de sua sequência atual. Existem 9 estados ( k + 1 ):knWFk+1

: Ainda não tivemos 8 tentativas corretas seguidas, e a última foi FA8F.

B: We have not had 8 correct trials in a row yet, and the last two trials were FW.

C: We have not had 8 correct trials in a row yet, and the last three trials were FWW.

H: We have not had 8 correct trials in a row yet, and the last eight trials were FWWWWWWW.

I: We've had 8 correct trials in a row!

The probability of moving to state B from state A is p=1/3 and with probability 1p=2/3 we stay in state A. From state B, the probability of moving to state C is 1/3 and with probability 2/3 we move back to A. And so on. If we are in state I, we stay there.

From this, we can construct a 9×9 transition matrix M (as each column of M sums to 1 and all entries are positive, M is called a left stochastic matrix):

M=(2/32/32/32/32/32/32/32/301/30000000001/30000000001/30000000001/30000000001/30000000001/30000000001/30000000001/31)

Each column and row corresponds to one state. After n trials, the entries of Mn give the probability of getting from state j (column) to state i (row) in 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 M25 (i.e. M9125). All we have to do now is calculating M25. 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.

COOLSerdash
fonte
3

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.

Greg Snow
fonte
Does your function include trials where it is impossible to get 8 in a row right, e.g. where the "run" started on trial 20?
Michelle
Most likely me, my R simulation is giving me smaller values as well. I'm just curious if there is an algebraic solution to solve this as a simple probability issue in case someone disputes a simulation.
AcidNynex
1
I think this answer would be improved by providing the output you obtained so that it can be compared. Of course, including something like a histogram in addition would be even better! The code looks right to me at first glance. Cheers. :)
cardinal
3

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:

18p817p945p16+81p1736p18

Evaluating at p=1.03.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

Hossam Karim
fonte