Enunciado

O Problema da Eleição. Em uma eleição, o candidato A recebe n votos e o candidato B recebe m votos, onde n > m. Assumindo que todas as

n + m ! n ! m !

ordens de votos sejam igualmente prováveis, suponha que P n , m represente a probabilidade de que A sempre esteja a frente na contagem dos votos.

(a) Calcule P 2,1 ,   P 3 , 1 ,   P 3 , 2 , P 4 , 1 ,   P 4 , 2 ,   P 4 , 3 .

(b) Determine P n , 1 ,   P n , 2 .

(c) Com base nos resultados que você obteve nas letras (a) e (b), faça conjecturas a respeito do valor de P n , m .

(d) Deduza uma fórmula recursiva para P n , m em termos de P n - 1 , m e P n , m - 1 condicionando em quem recebe o último voto.

(e) Use a letra (d) para verificar sua conjectura da letra (c) usando uma prova de indução em n + m.

Passo 1

Salve galera estudiosa, tudo certin??

Vamos para mais um problema de Probabilidade.

Para este problema, nos é dito que o candidato A recebe n votos e o candidato B recebe m votos onde assumimos que n > m. Vamos representar cada voto sequencial por uma sequência de A's e B's. O número de sequências AB é dado por

n + m ! n ! m !

Vamos supor que todas as sequências são igualmente prováveis. Seja E(n,m) o evento A está sempre à frente na contagem de votos e P n , m a probabilidade dos eventos.

(a)

Para calcular P 2 , 1 temos que a única sequência de votos em que A sempre lidera é AAB, assim:

P 2 , 1 = 1 2 + 1 ! 2 ! 1 ! = 1 3

Para calcular P 3 , 1 temos que apenas em duas sequências de votos A sempre lidera {AAAB, AABA} assim:

P 3 , 1 = 2 3 + 1 ! 3 ! 1 ! = 2 4 = 1 2

Para calcular P 3 , 2 temos que apenas em duas sequências de votos A sempre lidera {AAABB, AABAB} assim:

P 3 , 2 = 2 3 + 2 ! 3 ! 2 ! = 2 10 = 1 5

Para calcular P 4 , 1 temos que apenas em três sequências de votos A sempre lidera {AAAAB, AABAA, AAABA} assim:

P 4 , 1 = 3 4 + 1 ! 4 ! 1 ! = 3 5

Para calcular P 4 , 2 temos que apenas em cinco sequências de votos A sempre lidera {AAAABB, AAABAB, AAABBA, AABAAB, AABABA} assim:

P 4 , 2 = 5 4 + 2 ! 4 ! 2 ! = 5 15 = 1 3

Para calcular P 4 , 3 temos que apenas em cinco sequências de votos A sempre lidera {AAAABBB, AAABABB, AAABBAB, AABAABB, AABABAB} assim:

P 4 , 3 = 5 4 + 3 ! 4 ! 3 ! = 5 3 5 = 1 7

Passo 2

(b) Para P n , 1 , note que da equação n + 1 ! n ! 1 ! existem n + 1 sequências. Cada sequência tem um voto para B. Cada uma dessas sequências começa com os caracteres AA, AB ou B. Observe que as sequências que começam com B ou AB não terão A liderando em votos o tempo todo, enquanto para as sequências que começam com AA o número de votos A será sempre maior do que o número de votos para B em pelo menos 1. O número de sequências começando com AA (já que especificamos que os dois primeiros votos são para A temos n + 1 - 2 votos ainda colocar) é

n + 1 - 2 ! ( n - 2 ) ! 1 ! = n - 1

Então

P n , 1 = n - 1 n + 1

Para P n , 2 , observe que existem n + 2 ! n ! 2 ! = ( n + 2 ) ( n + 1 ) 2 sequências de A e B's e cada sequência terá dois B's. Todas as nossas sequências começam com AAA, AABA, AABB, AB ou B. As únicas dessas sequências em que A lidera para todas as contagens são AAA e AABA. Assim precisamos contar o número de sequências começando com cada um desses prefixos.

O número de sequências começando com AAA (já que agora temos n + 2 - 3 votos para distribuir) é:

n + 2 - 3 ! n - 3 ! 2 ! = ( n - 1 ) ( n - 2 ) 2  

O número de sequências começando com AABA (já que agora temos n + 2 - 4 votos para distribuir) é:

n + 2 - 4 ! n - 3 ! 1 ! = n - 2  

Assim, o total de sequências com A liderando é dado pela soma dessas duas possibilidades, ou seja:

( n - 1 ) ( n - 2 ) 2 + n - 2 =   ( n + 1 ) ( n - 2 ) 2

Então

P n , 2 = ( n + 1 ) ( n - 2 ) 2 ( n + 1 ) ( n + 2 ) 2 = n - 2 n + 2

(c) Observando o padrão entre P n , 1   e   P n , 2 temos que, generalizando para m:

P n , m = n - m n + m

Passo 3

(d) Para escrever P n , m em termos de P n - 1 , m   e   P n , m - 1 devemos condicionar o resultado do último voto, que pode ser de A ou B.

Teremos que

P n , m   =   n n + m P n - 1 , m +   m n + m P n , m - 1

Passo 4

(e) Considerando o resultado obtido em (c)

P n , m = n - m n + m

E definindo para P n - 1 , m   e   P n , m - 1 , temos:

P n - 1 , m = ( n - 1 ) - m ( n - 1 ) + m = n - m - 1 n + m - 1

P n , m - 1 = n - ( m - 1 ) n + ( m - 1 ) = n - m + 1 n + m - 1

Aplicando tal expressão no resultado de (d) temos que:

P n , m   =   n n + m n - m - 1 n + m - 1 +   m n + m n - m + 1 n + m - 1

Desenvolvendo tal expressão, temos que:

P n , m   =   n n - m - 1 + m ( n - m + 1 ) ( n + m ) ( n + m - 1 )

P n , m   =   n ² - m n - n + ( m n - m ² + m ) ( n + m ) ( n + m - 1 )

P n , m   =   n 2 - n -   m ² + m ( n + m ) ( n + m - 1 )

P n , m   =   ( n - m ) ( n +   m - 1 ) ( n + m ) ( n + m - 1 ) = n - m n + m

Que é justamente a mesma fórmula proposta em (c), como queríamos demonstrar.

Resposta

(a)

P 2,1 = 1 3 ,   P 3,1 = 1 2 ,   P 3,2 = 1 5 ,   P 4,1 = 3 5 ,   P 4,2 = 1 3 ,   P 4,3 = 1 7

(b) P n , 1 = n - 1 n + 1 ,     P n , 2 = n - 2 n + 2

(c) P n , m = n - m n + m

(d) P n , m   =   n n + m P n - 1 , m +   m n + m P n , m - 1

(e) Veja a demonstração.