O número esperado de jogadas de dados requer uma soma maior ou igual a K?

9

Um dado de 6 lados é rolado iterativamente. Qual é o número esperado de jogadas necessárias para fazer uma soma maior ou igual a K?

Antes da edição

P(Sum>=1 in exactly 1 roll)=1
P(Sum>=2 in exactly 1 roll)=5/6
P(Sum>=2 in exactly 2 rolls)=1/6
P(Sum>=3 in exactly 1 roll)=5/6
P(Sum>=3 in exactly 2 rolls)=2/6
P(Sum>=3 in exactly 3 rolls)=1/36
P(Sum>=4 in exactly 1 roll)=3/6
P(Sum>=4 in exactly 2 rolls)=3/6
P(Sum>=4 in exactly 3 rolls)=2/36
P(Sum>=4 in exactly 4 rolls)=1/216

Após a edição

P(Sum>=1 in atleast 1 roll)=1
P(Sum>=2 in atleast 1 roll)=5/6
P(Sum>=2 in atleast 2 rolls)=1
P(Sum>=3 in atleast 1 roll)=4/6
P(Sum>=3 in atleast 2 rolls)=35/36
P(Sum>=3 in atleast 3 rolls)=1
P(Sum>=4 in atleast 1 roll)=3/6
P(Sum>=4 in atleast 2 rolls)=33/36
P(Sum>=4 in atleast 3 rolls)=212/216
P(Sum>=4 in atleast 4 rolls)=1

Não tenho certeza se isso está correto antes de tudo, mas acho que essa probabilidade está relacionada ao número esperado de rolagens?

Mas não sei como prosseguir. Estou seguindo na direção certa?

Suspeito usual
fonte
Como você obteve ? P(S2 in 2 rolls)
Glen_b -Reinstala Monica
@Glen_b Você precisa obter um número menor que 2 no primeiro rolo, que é 1. Portanto, a probabilidade de obter 1 é 1/6 e o ​​segundo rolo pode ser qualquer número. se você obtiver um número maior ou igual a 2 no primeiro rolo, não fará um segundo rolo.
Usual Suspect
11
Ah, eu vejo o que está acontecendo. Você não descreve isso como "P (S \ geq 2 em 2 rolos)"; essa expressão implica que o número de rolos é fixo. O que você deseja é "P (exatamente 2 rolos necessários para obter )" ou "P (pelo menos 2 rolos necessários para obter S 2 )". S2S2
Glen_b -Reinstala Monica
@ Glen_b Sim, isso é a confusão. P (exatamente 2 rolos necessários para obter S> 2), eu acho. Tudo o que eu quero calcular é o número esperado de rolagens para atingir uma soma maior que K?
Usual Suspect
@Glen_b devo usar pelo menos ou exatamente para esse fim? E como calcular o número esperado de rolos para uma soma maior como 10000?
Usual Suspect

Respostas:

2

Até agora, são apenas algumas idéias para outra abordagem mais exata, com base na mesma observação que minha primeira resposta. Com o tempo vou estender isso ...

Primeiro, alguma notação. Seja um dado inteiro positivo (grande). Queremos a distribuição de N , que é o número mínimo de lança de um dado comuns para obter soma, pelo menos K . Então, em primeiro lugar, definimos X i como o resultado de lance de dados I , e X ( n ) = x 1 + + X n . Se pudermos encontrar a distribuição de X ( n ) para todos os n , podemos encontrar a distribuição de N usando P ( N KNKXiiX(n)=X1++XnX(n)nN e terminamos.

P(Nn)=P(X1++XnK),

Agora, os valores possíveis para são n , n + 1 , n + 2 , , 6 n e para k nesse intervalo, para encontrar a probabilidade P ( X 1 + + X n = k ) , precisamos encontrar o número total de maneiras de escrever k como uma soma de exatamente n números inteiros, todos no intervalo 1 , 2 , X1++Xnn,n+1,n+2,,6nkP(X1++Xn=k)kn . Mas isso é chamado de composição inteira restrita, um problema bem estudado em combinatória. Algumas perguntas relacionadas à matemática SE são encontradas em https://math.stackexchange.com/search?q=integer+compositions1,2,,6

Então, pesquisando e estudando essa literatura combinatória, podemos obter resultados precisos e silenciosos. Vou acompanhar isso, mas depois ...

kjetil b halvorsen
fonte
2

Existe uma fórmula simples e fechada em termos das raízes de um polinômio de grau 6.

Na verdade, é um pouco mais fácil considerar um dado justo geral com d2 faces rotuladas com os números 1,2,,d.

Vamos ek ser o número esperado de rolos necessários para igualar ou exceder k. Para k0, ek=0. Caso contrário, a expectativa é uma mais que a expectativa do número de rolagens para atingir o valor imediatamente anterior, que estaria entre kd,kd+1,,k1, onde

(1)ek=1+1d(ekd+ekd+1++ek1).

Essa relação de recorrência linear tem uma solução na forma

(2)ek=2kd+1+i=1daiλik

onde λi são as raízes d complexas do polinômio

(3)Td1d(Td1+Td2++T+1).

As constantes de ai encontram-se aplicando-se a solução para os valores , onde em todos os casos. Isso fornece um conjunto de equações lineares nas constantes e possui uma solução única. Que a solução funciona pode ser demonstrada verificando a recorrência usando o fato de que toda raiz satisfaz(2)k=(d1),(d2),,1,0ek=0dd(1)(3):

1+1dj=1dekj=1+1dj=1d(2(kj)d+1+i=1daiλikj)=2kd+1+i=1daiλikd[1d(1+λi++λid1)]=2kd+1+i=1daiλikdλid=2kd+1+i=1daiλik=ek.

Esta solução de formulário fechado nos fornece boas maneiras de aproximar a resposta e também avaliar com precisão. (Para valores pequenos a modestos de a aplicação direta da recorrência é uma técnica computacional eficaz.) Por exemplo, com , podemos calcular prontamentek,d=6

e1000000=285714.761905

Para aproximações, haverá uma maior raiz única assim, eventualmente (para suficientemente grande ), o termo dominará os termos emO erro diminuirá exponencialmente de acordo com a segunda menor norma das raízes. Continuando o exemplo com o coeficiente de é e a próxima menor norma é (Aliás, o outro tende a ser muito próximo de em tamanho.) Assim, podemos aproximar o valor anterior comoλ+=1kλ+kd(2).k = 6 , λ + a + = 0,4761905 0,7302500. a i 1k=6,λ+a+=0.47619050.7302500.ai1

e10000002×1066+1+0.4761905=285714.761905

com um erro da ordem de0.730250010610314368.


Para demonstrar como essa solução é prática, eis o Rcódigo que retorna uma função para avaliar para qualquer (dentro do escopo de cálculos de ponto flutuante de precisão dupla) e não muito grande (será atolado uma vez que ):ekkdd100

die <- function(d, mult=1, cnst=1, start=rep(0,d)) {
  # Create the companion matrix (its eigenvalues are the lambdas).
  X <- matrix(c(0,1,rep(0,d-1)),d,d+1)
  X[, d] <- mult/d
  lambda <- eigen(X[, 1:d], symmetric=FALSE, only.values=TRUE)$values

  # Find the coefficients that agree with the starting values.
  u <- 2*cnst/(d+1)
  a <- solve(t(outer(lambda, 1:d, `^`)), start - u*((1-d):0))

  # This function assumes the starting values are all real numbers.
  f <- Vectorize(function(i) Re(sum(a * lambda ^ (i+d))) + u*i)

  list(f=f, lambda=lambda, a=a, multiplier=mult, offset=cnst)
}

Como exemplo de seu uso, aqui calcula as expectativas parak=1,2,,16:

round(die(6)$f(1:10), 3)

1.000 1.167 1.361 1.588 1.853 2.161 2.522 2.775 3.043 3.324 3.613 3.906 4.197 4.476 4.760 5.046

O objeto retornado inclui as raízes e seus multiplicadores para análises adicionais. O primeiro componente da matriz de multiplicadores é o coeficiente útilλiaia+.

(Se você está curioso para que dieservem os outros parâmetros , execute die(2, 2, 0, c(1,0))$f(1:10)e veja se reconhece a saída ;-). Essa generalização ajudou no desenvolvimento e no teste da função.)

whuber
fonte
+1. A função diedá um erro para mim: object 'phi' not found.
COOLSerdash 13/09/19
11
@ COOL Obrigado por verificar. Uma mudança de última hora do nome da variável (de phipara a) para corresponder ao texto foi o culpado. Eu o corrigi (e verifiquei).
whuber
1

não há como obter o número exato exato de rolagens em geral, mas para um K.

Seja N o evento de rolagem esperada para obter soma => K.

para K = 1, E (N) = 1

para K = 2,E(N)=(56+21)/(56+1)=1711

e assim por diante.

Será difícil obter E (N) para K. grande, por exemplo, para K = 20 você precisará esperar (4 rolos, 20 rolos)

O Teorema do Limite Central será mais beneficiado com alguma% de confiança. como sabemos que a ocorrência é distribuída uniformemente, para grandes valores de K. (Distribuição Normal)

K(Sum) follows N(3.5N,35N12)

Agora você precisa de "N" para obter Sum pelo menos K .... nós o convertemos na distribuição normal padrão. onde % Você pode obter valores Z em "Tabelas normais padrão" ou daqui, por exemplo

K3.5N35N12=Zα
α=1confidenceZ0.01=2.31,Z0.001=2.98

Você conhece K, Z (com qualquer erro) ........, então você pode obter N = E (N) com alguma% de confiança resolvendo a equação.

Hemant Rupani
fonte
2
Como você calculou essas probabilidades? Como você chegou à equação E (N)?
Usual Suspect
@UsualSuspect P (Soma> = 2 em 1 rolo) = 5/6 (você sabe) P (Soma> = 2 em 2 rolos) = 1 (porque você deve obter a soma de pelo menos 2 de 2 rolos) e para E (N ) ......... é apenas uma média esperada
Hemant Rupani
Desculpe, eu não mencionei. Não é pelo menos, exatamente 2 rolos. Eu entendi a equação E (N) agora.
Usual Suspect
@UsualSuspect ohh! a propósito, se você precisar de E (N) para qualquer K em particular, então eu posso fazê-lo :).
amigos estão dizendo sobre hemant
preciso de k = 20 ek = 10000. É melhor se você me explicar, em vez de dar respostas diretas.
Usual Suspect
0

Vou dar um método para encontrar uma solução aproximada. Primeiro, seja a variável aleatória, "resultado do lançamento com os dados" e seja o número de jogadas necessárias para atingir uma soma pelo menos . Então temos que , para encontrar a distribuição de , precisamos encontrar as convoluções das distribuições do para , para todos os . Essas convulsões podem ser encontradas numericamente, mas para grandesXiiNk

P(Nn)=P(X1+X2++Xnk)
NXii=1,2,,nnnpode ser muito trabalhoso, então tentamos aproximar a função de distribuição cumulativa para as convoluções, usando métodos de ponto de sela. Para outro exemplo de métodos de ponto de sela, consulte minha resposta à soma genérica de variáveis ​​aleatórias gama

Usaremos a aproximação de Lugannini-Rice para o caso discreto e segue R Butler: "Aproximações do ponto de sela com aplicações", página 18 (segunda correção de continuidade). Primeiro, precisamos da função geradora de momento do , que é Então a função geradora cumulante para a soma de dados independentes se torna e também precisamos das primeiras derivadas de , mas as encontraremos simbolicamente usando R. O código é o seguinte:Xi

M(T)=EetXi=16(et+e2t+e3t+e4t+e5t+e6t)
n
Kn(t)=nlog(16i=16eit)
K

 DD <- function(expr, name, order = 1) {
        if(order < 1) stop("'order' must be >= 1")
        if(order == 1) D(expr, name)
        else DD(D(expr, name), name, order - 1)
     }

make_cumgenfun  <-  function() {
    fun0  <-  function(n, t) n*log(mean(exp((1:6)*t)))
    fun1  <-  function(n, t) {}
    fun2  <-  function(n, t) {}
    fun3  <-  function(n, t) {}
    d1  <-  DD(expression(n*log((1/6)*(exp(t)+exp(2*t)+exp(3*t)+exp(4*t)+exp(5*t)+exp(6*t)))),  "t", 1)
    d2  <-  DD(expression(n*log((1/6)*(exp(t)+exp(2*t)+exp(3*t)+exp(4*t)+exp(5*t)+exp(6*t)))),  "t", 2)
    d3  <-  DD(expression(n*log((1/6)*(exp(t)+exp(2*t)+exp(3*t)+exp(4*t)+exp(5*t)+exp(6*t)))),  "t", 3)
    body(fun1)  <-  d1
    body(fun2)  <-  d2
    body(fun3)  <-  d3
    return(list(fun0,  fun1,  fun2,  fun3))
}

Em seguida, devemos resolver a equação do ponto de sela.

Isso é feito pelo seguinte código:

funlist  <-  make_cumgenfun()

# To solve the saddlepoint equation for n,  k:
solve_speq  <-   function(n, k)  {# note that n+1 <= k <= 6n is needed
    Kd  <-  function(t) funlist[[2]](n, t)
    k  <-  k-0.5
    uniroot(function(s) Kd(s)-k,  lower=-100,  upper=1,  extendInt="upX")$root
}

Observe que o código acima não é muito robusto, pois valores de distantes em qualquer parte da distribuição não funcionarão. Então, algum código para o cálculo real da função de probabilidade da cauda, ​​aproximadamente, pela aproximação de Luganini-Rice, seguindo Butler, página 18, (segunda correção de continuidade):k

Função para retornar a probabilidade da cauda:

#

Ghelp  <-  function(n, k) {
    stilde  <-  solve_speq(n, k)
    K  <-  function(t) funlist[[1]](n, t)
    Kd <-  function(t) funlist[[2]](n, t)
    Kdd <- function(t) funlist[[3]](n, t)
    Kddd <- function(t) funlist[[4]](n, t)
    w2tilde  <-  sign(stilde)*sqrt(2*(stilde*(k-0.5)-K(stilde)))  
    u2tilde  <-  2*sinh(stilde/2)*sqrt(Kdd(stilde))
    mu  <-  Kd(0)
    result  <- if (abs(mu-(k-0.5)) <= 0.001) 0.5-Kddd(0)/(6*sqrt(2*pi)*Kdd(0)^(3/2))  else
    1-pnorm(w2tilde)-dnorm(w2tilde)*(1/w2tilde - 1/u2tilde)
    return(result)
}
G  <- function(n, k) {
      fun  <- function(k) Ghelp(n, k)
      Vectorize(fun)(k)
  }

Vamos tentar usar isso para calcular uma tabela da distribuição, com base na fórmula que é a função do código R acima.

P(Nn)=P(X1+X2++Xnk)=1P(X1++Xnk+1)=1G(n,k+1)
G

Agora, vamos responder à pergunta original com . Então o número mínimo de rolos é 4 e o número máximo de rolos é 20. A probabilidade de que sejam necessários 20 rolos é muito pequena e pode ser calculada exatamente a partir da fórmula binomial, deixo isso para o leitor. (a aproximação acima não funcionará para ).K=20n=20

Portanto, a probabilidade de ser aproximada porN19

> 1-G(20, 21)
[1] 2.220446e-16

A probabilidade de ser aproximada por:N10

> 1-G(10, 21)
[1] 0.002880649

E assim por diante. Usando tudo isso, você pode obter uma aproximação para a expectativa. Isso deve ser muito melhor do que as aproximações baseadas no teorema do limite central.

kjetil b halvorsen
fonte