Jogue 100 moedas justas e tire as caudas; jogue as moedas restantes e tire as caudas. Continue até que não haja mais moedas. [duplicado]
100 participantes recebem uma moeda justa cada, em uma dada rodada, os participantes ainda não descartados lançam suas moedas, os que lançam o rabo são descartados do jogo, os restantes continuam jogando até que não haja mais ninguém (todos foram descartados).
Qual seria o número médio de tentativas (onde cada tentativa consiste em jogar e remover as caudas) que se esperaria de fazer esta experiência?
A expectativa condicional funciona para algo assim?
Eu sei que cada moeda individual segue uma distribuição geométrica, mas estou tentando descobrir a soma delas para determinar o número médio de tentativas para um jogo como este.
Minha Lógica / Processo de Pensamento: Comecei tentando pensar na probabilidade de uma moeda em particular girar $r$ qual é $\frac{1}{2^m}$. Então percebi que cada resultado de moeda pode ser modelado por variáveis aleatórias geométricas com$p = 0.5$. Só agora não tenho certeza de como saltar desta caixa única para uma caixa com 100 moedas. Presumo que tenha a ver com a soma das variáveis aleatórias geométricas, mas não tenho certeza.
Respostas
Isso é essencialmente equivalente a calcular o valor esperado do máximo de$n=100$iid variáveis aleatórias geométricas , para$p=\frac12$
(BTW: A questão vinculada inclui a recursão dada pela resposta de @saulspatz)
Não há solução de forma fechada, mas esta aproximação para grandes $n$ (com limites) é fornecido:
$$E_n \approx \frac{1}{2} + \frac{1}{\lambda} H_n$$
Onde $\lambda = - \log(1-p)=0.69314718\cdots$ e $H_n$ é o número harmônico.
Por exemplo, para $n=3$ isto dá $E_3 \approx 3.14494$ , muito perto do exato $E_3=22/7=3.14285$
Para $n=100$ isto dá $E_{100} \approx 7.98380382$.
Mais em "Mais uma aplicação de estatísticas de ordem de recorrência binomial", W. Szpankowski; V. Rego, Computing, 1990, 43, 4, 401-410.
Duvido que haja uma expressão simples para a expectativa. Deixei$E_n$ ser o número esperado de tentativas quando $n$ moedas permanecem, de modo que somos solicitados a computar $E_{100}$. Nós sabemos isso$E_0=0$ e essa $E_1=2$. Agora$$E_2=1+\frac14E_2+\frac12E_1+\frac14E_0$$ porque temos que fazer uma tentativa, e com probabilidade $\frac14$ jogamos duas caras e ainda temos duas moedas, com probabilidade $\frac12$ jogamos uma cabeça e um rabo, e com probabilidade $\frac14$, lançamos duas caudas e o experimento termina. Isto dá$E_2=\frac83$.
Podemos continuar desta maneira: $$E_3=1+\frac18E_3+\frac38E_2+\frac38E_1+\frac18E_0$$ que dá $E_3=\frac{22}7$ se não estou errado.
Pode-se facilmente escrever um programa de computador para trabalhar $E_{100}$, mas seria mais fácil proceder por simulação.
EDITAR
Eu escrevi o roteiro que sugeri. O valor exato se uma fração cujo numerador tem$894$ dígitos decimais e cujo denominador tem $893$. O valor aproximado é$7.98380153515692$.
Pesquisando OEIS com os primeiros valores @saulspatz, podemos descobrir que:
$$E_n = \frac{a(n)}{b(n)}$$
Onde $a(n)$é OEIS A158466 e$b(n)$é OEIS A158467 . No OEIS A158466 você também pode encontrar as seguintes fórmulas:
$$E_n = -\sum_{k=1}^n (-1)^k \frac{{n \choose k}}{1-\frac{1}{2^k}}$$
$$E_n = \sum_{k=1}^{\infty} k \left(\left(1-\frac{1}{2^k}\right)^n - \left(1-\frac{1}{2^{k-1}}\right)^n\right)$$
e assim (veja aqui ):
$$E_{100} \approx 7.983801535$$
Conjunto $N_0=100$ e pegue $N_k$ para ser o número de moedas que permanecem após o $k^\text{th}$julgamento neste processo. Então podemos dizer algo como$$P(N_1=81|N_0=100)={100 \choose 19}\Big(\frac{1}{2}\Big)^{100}$$
Para agora $i\in \{0,1,\ldots, 100\}$ e $j\in \{0,1,\ldots ,i\}$ temos $$P(N_{k+1}=j|N_{k}=i)={i \choose j-i}\Big(\frac{1}{2}\Big)^i$$ Aviso prévio $\{N_k\}_{k=0}^{\infty}$ é uma cadeia de Markov absorvente com $0$como um estado absorvente. Você está tentando calcular o número esperado de tentativas neste processo aleatório antes de ser absorvido no estado$0$ começando do estado $100$. Existem muitas maneiras de calcular este valor esperado, a mais eficiente é provavelmente usando a matriz fundamental que você pode aprender aqui