Solução a um problema de probabilidade

O problema é o seguinte:

Uma partícula se desloca sobre a reta real sempre em passos de comprimento unitário, para a direita ou para a esquerda. Estando inicialmente a partícula na origem, se ela vai dar 10 passos, cada um ao acaso para a direita ou para a esquerda, qual é a probabilidade da partícula passar pelo 3?

Este problema foi proposto durante a sessão de perguntas do último PAPMEM. Em princípio tentei algumas ideias simples, mas percebi que nenhuma delas levaria a uma solução correta. Então decidi seguir o caminho trabalhoso, mas seguro. Recomendo ao leitor interessado que tente resolver o problema por conta própria antes de clicar no link a seguir e ler minha solução. Adoraria receber comentários, correções ou soluções alternativas.

[acrescentado em 04/08/10: interpretei passar pelo 3 como ir além do 3, ou seja, atingir o 4]


Solução:

Como símbolos matemáticos mais sofisticados não são necessários, vou tentar escrever direto em texto. Espero que fique claro.

Cada um dos 1024 caminhos possíveis para a partícula tem mesma probabilidade de ocorrer, pois são 10 decisões consecutivas, com duas opções equiprováveis cada uma. Assim, vamos contar quantos desses caminhos passam pelo 3.

Cada caminho pode ser codificado como uma sequência de 10 letras, cada uma delas igual a D (direita) ou E (esquerda), representando cada a decisão correspondente a sua posição na sequência. Como a palavra passar está destacada no texto, vamos admitir que isto signifique não apenas chegar ao 3, mas ir mais além. Com esta interpretação, o problema equivale a determinar a probabilidade de se chegar ao 4.

O número total de caminhos que chegam ao 4 é a união de 4 conjuntos A_4, A_6, A_8 e A_10 definidos por

A_k: conjunto dos caminhos nos quais o 4 é atingido em k passos.

Para calcular o número de elementos dessa união, vamos utilizar o princípio de inclusão e exclusão (e, é claro, muita paciência). Representando por #A o número de elementos (cardinal) do conjunto A, temos:

1) Cardinal de cada conjunto:

#A_4 é igual ao número de sequências que começam por DDDD. Temos 2 opções para cada uma das demais letras, logo #A_4 = 2 x 2 x 2 x 2 x 2 x 2 = 64.

#A_6 é igual ao número de sequências cujas 6 primeiras letras são exatamente 5 D's e um E. Existem 6 maneiras de escolher essas 6 primeiras letras (basta escolher a posição do E), e depois 2 opções para cada uma das outras 4 letras, ou seja, #A_6 = 6 x 2 x 2 x 2 x 2 = 96.

#A_8 é igual ao número de sequências cujas 8 primeiras letras são exatamente 6 D's e 2 E's. Para determinar essas 8 primeiras letras basta escolher as posições das duas letras E, logo há 28 (combinação de 8 objetos tomados 2 a 2) maneiras de fazê-lo. A seguir, restam 2 opções para cada uma das 2 letras restantes, logo #A_8 = 28 x 2 x 2 = 112.

#A_10 é igual ao número de sequências formadas por exatamente 7 D's e 3 E's, logo #A_10 = 120 (combinação de 10 objetos tomados 3 a 3, pois, novamente, basta escolher as posições dos E's).

2) Cardinal de cada uma das 6 interseções dos conjuntos tomados dois a dois:

Interseção entre A_4 e A_6: A sequência deve começar com DDDDDE ou com DDDDED. As outras 4 letras podem ser escolhidas livremente. Logo o cardinal desta interseção é 2 x 2 x 2 x 2 x 2 = 32.

Interseção entre A_4 e A_8: após DDDD devemos ter 2 D's e 2 E's: 6 opções (combinação de 4 objetos tomados 2 a 2). As duas últimas letras são livros, logo o cardinal desta interseção é 6 x 2 x 2 = 24.

Interseção entre A_4 e A_10: após DDDD devemos ter 3 D's e 3 E's, logo o cardinal desta interseção é igual a 20 (combinação de 6 objetos tomados 3 a 3).

Interseção entre A_6 e A_8: 6 opções para as 6 primeiras letras (como no cálculo de #A_6), em seguida 2 opções para as próximas 2 letras (ED ou DE) e duas últimas letras livres. O cardinal é 6 x 2 x 2 x 2 = 48.

Interseção entre A_6 e A_10: 6 opções para as 6 primeiras letras e depois 6 opções para as 4 últimas (2 D's e 2 E's). O cardinal é 6 x 6 = 36.

Interseção entre A_8 e A_10: 28 opções para as 8 primeiras letras, e 2 opções para as duas últimas (DE ou ED). O cardinal é 28 x 2 = 56.

3) Cardinal de cada uma das 4 interseções dos conjuntos tomados 3 a 3:

Interseção entre A_4, A_6 e A_8: DDDD seguidos de ED ou DE, seguidos de ED ou DE, duas últimas letras livres. O cardinal é 2 x 2 x 2 x 2 = 16.

Interseção entre A_4, A_6 e A_10: DDDD seguidos de ED ou DE, seguidos de 2 D's e 2 E's. O cardinal é 2 x 6 = 12.

Interseção entre A_4, A_8 e A_10: DDDD seguidos de 2 D's e 2 E's, seguidos de ED ou DE. O cardinal é: 6 x 2 = 12.

Interseção entre A_6, A_8 e A_10. Como antes, agora temos 6 opções para as 6 primeiras letras, ED ou DE para as próximas duas e ED ou DE para as duas últimas. O cardinal é: 6 x 2 x 2 = 24.

4) Interseção entre os 4 conjuntos:

DDDD seguidos de ED ou DE, seguidos de ED ou DE, seguidos de ED ou DE. O cardinal é: 2 x 2 x 2 = 8.

Ufa! Agora é só aplicar o princípio de inclusão e exclusão. O cardinal da união é igual à soma dos cardinais calculados em 1), menos a soma dos cardinais calculados em 2), mais a soma dos cardinais calculados em 3), menos o cardinal calculado em 4), ou seja,

64 + 96 + 112 + 120 – 32 – 24 – 20 – 48 – 36 – 56 + 16 + 12 + 12 + 24 – 8 = 232.

Assim, a probabilidade pedida é igual a 232/1024 = 29/128, aproximadamente 23%.