Hidra Condicional
A Hidra na Mitologia Grega era um monstro com corpo de dragão e várias cabeças de serpente que habitava um pântano perto do lago de Lerna. Em algumas versões da lenda, a Hidra tem uma cabeça verdadeira que caso destruída, a Hidra morreria e outras falsas cabeças, que quando destruídas gerariam duas novas cabeças. Para a construção do nosso problema, assumiremos esta versão como a verdadeira.
Assim, suponha que exista um herói cego, incansável e invulnerável, capaz de atacar a Hidra por quanto tempo quiser. Mas por definição (de acordo com a lenda), cada cabeça falsa que é cortada gera duas novas cabeças falsas. Então, cada vez que a cabeça errada for cortada, sua chance de acertar a cabeça certa será menor.
Para ilustrar este problema vamos supor que a Hidra comece com duas cabeças (mas ela poderia começar com qualquer N cabeças, sendo N maior ou igual a 2).
Nosso herói cego esta diante a Hidra de duas cabeças. A chance de acertar a cabeça verdadeira é 50% e a chance de acertar a cabeça falsa é 50%.
Ele ataca uma cabeça.
A cabeça é arrancada.
Mas por azar, era a cabeça falsa. Então nascem duas novas cabeças. Agora sua chance de acertar a cabeça verdadeira é aproximadamente 33% e a chance de acertar uma cabeça falsa é aproximadamente 67%.
Ele ataca uma cabeça.
A cabeça é arrancada.
Mas por azar, era a cabeça falsa. Então nascem duas novas cabeças. Agora sua chance de acertar a cabeça verdadeira é 25% e a chance de acertar uma cabeça falsa é 75%.
Ele ataca uma cabeça.
A cabeça é arrancada.
Mas por azar, era a cabeça falsa. Então nascem duas novas cabeças. Agora sua chance de acertar a cabeça verdadeira é 20% e a chance de acertar uma cabeça falsa é 80%. Vamos parar com apenas 5 cabeças, mas neste problema, aparentemente quanto mais o nosso herói demora para matar a Hidra, mais improvável parece a chance dele acertar a cabeça verdadeira (dado que o número de cabeças falsas aumenta). Você pode até pensar que matá-la é uma questão de sorte, mas infelizmente (para a Hidra) a probabilidade condicional nos diz outra coisa.
Se observarmos a chance do nosso herói derrotar a Hidra a cada novo golpe, esta probabilidade será 1/(número-total-de-cabeças), assim por exemplo, uma Hidra com 100 cabeças, a chance do herói acertar a cabeça verdadeira será de 1%.
Por outro lado (usando probabilidade condicional), vamos observar a chance da Hidra sobreviver a cada golpe. Pois no caso de uma Hidra que comece com duas cabeças, ela somente chegará a ter 100 cabeças, se o herói acertar a cabeça errada 98 vezes.
Pois para a Hidra alcançar n+2 cabeças, o herói deve ter errado todos os primeiros n golpes.
Analisando então desde o primeiro dos erros do nosso herói, a chance desta Hidra sobreviver ao primeiro golpe e alcançar 3 cabeças é de 50%.
Contudo a chance desta Hidra sobreviver a dois golpes do herói, será a probabilidade dela sobreviver ao segundo golpe dado que ela sobreviveu ao primeiro golpe. Ou seja (50%).(67%), que dá 33%.
Analogamente, a chance desta Hidra sobreviver a três golpes do herói, será a probabilidade dela sobreviver ao terceiro golpe dado que ela sobreviveu ao primeiro e ao segundo golpe. Ou seja (50%).(67%).(75%), que dá 25%.
Sobreviver a quatro golpes: probabilidade de sobreviver ao quarto golpe dado que sobreviveu aos 3 primeiros golpes: (50%).(67%).(75%).(80%), que dá 20%.
Seguiremos apenas com os resultados para os casos seguintes:
Sobreviver a cinco golpes: 16%.
Sobreviver a seis golpes: 14%.
Sobreviver a sete golpes: 12%.
Sobreviver a oito golpes: 11%.
Sobreviver a nove golpes: 10%.
Sobreviver a dez golpes: 9%.
…
Sobreviver a 98 golpes: 1%.
…
Sobreviver a 998 golpes: 0,1%.
Assim, a chance de uma Hidra nestas condições chegar a 100 cabeças (sobreviver a 98 golpes) é de aproximadamente 1%. A chance desta mesma Hidra chegar a 1000 cabeças é de aproximadamente 0,1%. Dessa forma, podemos perceber que a medida que o número de ataques aumenta, a chance da Hidra continuar viva diminui apesar do número de cabeças aumentar.
Apesar das chances da Hidra sobreviver sempre aumentarem (do ponto de vista dos ataques de herói), a probabilidade de atingir um número muito grande de cabeças vai se aproximando cada vez mais de 0%. Ou seja, certamente (mais cedo ou mais tarde ) o herói acertará um golpe na cabeça verdadeira e a luta terminará.
Você pode estar pensando que isto só funcionou pois a nossa Hidra era muito fraquinha, se fosse uma “Super-Hidra” as coisas poderiam ser diferentes. Vamos supor então que nosso herói esteja enfrentando uma “Super-Hidra” com N cabeças e a cada cabeça falsa destruída, surjam M cabeças. Sendo N e M números Naturais quaisquer.
Da mesma forma, sua chance de sobreviver aos primeiros n ataques de nosso herói será:
(N-1/N).(N-2+M/N-1+M).(N-3+2M/N-2+2M).(N-4+3M/N-3+3M) … (N-n+(n-1)M/N-(n-1)+(n-1).M).
Agora fica difícil perceber para um valor qualquer de M e N, que conforme o número de ataques (n) aumenta, a chance de sobreviver da “Super-Hidra” vai diminuir. Mas observe que o denominador é sempre maior que o quociente, então para cada ataque do herói, a chance da “Super-Hidra” sobreviver é menor que 1. Então quando multiplicamos todos esses números menores que 1, este produto estará sempre em redução, então a chance de a “Super-Hidra” sobreviver a cada novo ataque, sempre diminuirá, não importa o tamanho de M e N.
Por exemplo, com M = 100 e N = 100.
Após 10 ataques, a chance da “Super-Hidra” continuar viva é de 97%;
Após 100 ataques a chance da “Super-Hidra” continuar viva é de 95%.
Esta chance esta diminuindo lentamente, mas para um n suficientemente grande, a chance da “Super-Hidra” continuar viva será muito próximo de 0%.