Cinco times de igual força disputarão todo ano um torneio. Uma taça será ganha pelo primeiro time que vencer três vezes consecutivas. Qual a probabilidade de a taça não ser ganha nos n primeiros torneios?
Passo 1
Temos cinco times de força igual disputando anualmente um torneio. Cada torneio é vencido por um dos cinco times, todos com probabilidade 1/5, de forma independente. A taça é entregue assim que algum time vence três vezes consecutivas, isto é, no instante em que aparece uma sequência de três vitórias seguidas do mesmo time. Queremos a probabilidade de não ocorrer tal sequência de três vitórias iguais nos n primeiros torneios.
Conteúdo: cadeias de Markov simples ou contagem de sequências sem “runs” de comprimento \ge3. Vamos modelar como sequências de comprimentos n sobre um alfabeto de 5 símbolos, proibindo substrings iguais de tamanho 3.
Passo 2
Defina A(n) = número de sequências de comprimento n sobre o alfabeto \{1,2,3,4,5\} que não contêm três símbolos idênticos consecutivos. Qualquer sequência válida pode terminar com um “run” de comprimento 1 ou de comprimento 2.
Passo 3
Seja
A_1(n)=\text{quantas sequências válidas de tamanho \(n\) terminam com um run de comprimento 1},
A_2(n)=\text{quantas sequências válidas de tamanho \(n\) terminam com um run de comprimento 2}.
Então
A(n)=A_1(n)+A_2(n).
Passo 4
Para construir uma sequência válida de tamanho n:
Se ela termina com run de comprimento 1, o último símbolo é diferente do anterior. Portanto há A(n-1) sequências válidas de tamanho n-1 e, para cada uma, 4 escolhas de símbolo distinto do último. Logo
A_1(n)=4\,A(n-1).
Se ela termina com run de comprimento 2, os dois últimos símbolos são iguais, mas o anterior a eles deve ser diferente (para não formar run >=3). Logo só podemos estender sequências de tamanho n-1 que terminam com run de comprimento 1, repetindo o último símbolo. Assim
A_2(n)=1\cdot A_1(n-1)=4\,A(n-2).
Somando, para n\ge3 temos a recorrência
A(n)=A_1(n)+A_2(n)=4\,A(n-1)+4\,A(n-2).
Passo 5
As condições iniciais são fáceis:
A(1)=5, pois qualquer um dos 5 símbolos em sequência de tamanho 1 não forma run de 3.
A(2)=5^2=25, pois em sequência de tamanho 2 tampouco há run de 3.