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]

Dec 11 2020

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

  1. 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?

  2. 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

7 leonbloy Dec 11 2020 at 23:42

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.

6 saulspatz Dec 11 2020 at 23:23

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$.

2 BillyJoe Dec 12 2020 at 00:23

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$$

MatthewPilling Dec 12 2020 at 00:09

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