Teorema da Eleição

Em probabilidade, o Teorema da Eleição é um resultado clássico sobre passeios aleatórios que afirma:

Em uma eleição com dois candidatos A e B com $\alpha$ e $\beta$ votos respectivamente, se $\alpha >\beta$ então a probabilidade de que durante a apuração da eleição o candidato A esteja sempre à frente é dada por $\frac{\alpha -\beta }{\alpha +\beta }$.

O resultado foi descoberto por A. De Moivre em 1708 ao estudar jogos de azar e redescoberto por Joseph Louis François Bertrand em 1887.

Na linguagem de Passeios aleatórios

Se entendermos cada voto para o ganhador como um passo de valor 1 e cada voto para o perdedor como um passo de valor -1 podemos interpretar como segue:

Seja $S_0=0,S_1,S_2,S_3,...,S_n$ um passeio aleatório com passos $X_i$ com $P(X_i=1)=P(X_i=-1)=\frac{1}{2}$ i.i.d., se $S_n=b>0$ então a probabilidade de que $S_i>0$ $\mathrm{\forall }i=1,\cdots ,n$ é dada por $\frac{b}{n}$, em outras palavras:

$𝒫(S_1\times S_2\times \cdots \times S_n>0|S_n=b)=\frac{b}{n}$

Para demonstrar faremos uso do princípio da reflexão.

O princípio da reflexão

A figura apresenta um caminho aleatório e desenha o reflexo por x do trecho do caminho que é positivo até o primeiro encontro com o eixo x.

Seja $N_n^0(a,b)$ o número de caminhos entre os pontos $(0,a)$ e $(n,b)$ que tocam o eixo $x$, tome também $N_n(a,b)$ o número de caminhos entre $(0,a)$ e $(n,b)$.

Se $a,b>0$ o princípio da reflexão diz que $N_n^0(a,b)=N_n(-a,b)$. Para demonstrar vamos criar uma bijeção entre os caminhos de $(0,a)$ até $(n,b)$ que passam por algum $(k,0)$, $1<k<n$ e os caminhos entre $(0,-a)$ até $(n,b)$.

É claro que todo caminho que parte de $(0,-a)$ até $(n,b)$ corta o eixo $x$ em algum ponto, seja $(k,0)$ o primeiro ponto em que isso ocorre. Podemos refletir todos os pontos antes de $(k,0)$ e emendar com o caminho depois de $(k,0)$ e vamos obter um caminho entre $(0,a)$ e $(n,b)$ que corta o eixo $x$. A operação inversa é feita de forma análoga, acompanhe na figura ao lado. Temos então a bijeção desejada.

Calcular $N_n^0(a,b)$ pode ser custoso, mas o princípio da reflexão facilita esse cálculo. Se um caminho vai de $(0,a)$ até $(n,b)$ então ele tem $n$ passos, separamos $n=u+d$ com $u$ o número de passos para cima e $d$ para baixo. Vale também $u-d=b-a$, logo: $u=\frac{n+b-a}{2}\text{ e }d=\frac{n-b+a}{2}$ Para formar um caminho precisamos apenas saber quantas vezes andamos para cima, logo:

$N_n(a,b)=(\genfrac{}{}{0ex}{}{n}{\frac{n+b-a}{2}})$

Demonstração

Para mostrar basta reparar que estamos contando apenas os caminhos que obrigatoriamente passam por $(1,1)$, logo:

$N_n^x(0,b)=N_{n-1}(1,b)-N_{n-1}^0(1,b)=N_{n-1}(1,b)-N_{n-1}(-1,b)$

De onde obtemos:

$N_n^x(a,b)=(\genfrac{}{}{0ex}{}{n-1}{\frac{n+b-2}{2}})-(\genfrac{}{}{0ex}{}{n-1}{\frac{n+b}{2}})=\frac{b}{n}{N}_n(0,b)$

Como o total de caminhos é dado por $N_n(0,b)$ obtemos a probabilidade dividindo o número de casos de interesse pelo tamanho do espaço amostral.

Relação com o Hitting Time

Exemplo de caminho aleatório reverso.

Dado um caminho $S=\{0,X_1,X_1+X_2\cdots ,\sum _{i=1}^{i=n}{X}_i\}$ podemos construir o caminho reverso tomando $T=\{0,X_n,X_n+X_{n-1}\cdots ,\sum _{i=1}^{i=n}{X}_i\}$. Note que $T_n=S_n$ e $T_n-T_{n-i}=X_1+\cdots +X_i=S_i$ para todo $i>0$. Assim se $S$ é um caminho que atende as restrições do Teorema da Eleição com $S_n=b>0$ vale que $T_n-T_{n-i}=S_i>0$ para todo $i>0$. Ou seja, o caminho reverso alcança $b$ pela primeira vez no passo $n$.

Agora tomando um caminho $T$ tal que $T_n=b$ e $T_n-T_{n-i}=X_1+\cdots +X_i=S_i$ para todo $i>0$, é fácil ver que o seu reverso $S$ cumpre as condições do Teorema da Eleição. Assim estabelecemos uma bijeção entre os caminhos tais que $T_n=b$ e atingem $b$ pela primeira vez no passo $n$ e os caminhos tais que $S_n=b$ e $S_1\cdots S_n\ne 0$. Como todo caminho tem a mesma probabilidade de ocorrer, vale:

$𝒫(S_i\ne S_n\mathrm{\forall }i<n|S_n=b)=𝒫(S_1\cdots S_n>0|S_n=b)$

Observando que o caso $b<0$ é simétrico obtemos o Teorema do Hitting Time: a probabilidade de um caminho aleatório simples $S$ alcançar o ponto $b$ pela primeira vez no passo $n$ é dada por:

$𝒫(S_i\ne S_n\mathrm{\forall }i<n|S_n=b)=\frac{|b|}{n}𝒫(S_n=b)$

Essa relação segue sendo verdadeira contanto que os passos $X_i$ sejam i.i.d., como demonstrado por Hofstad e Keane .

Generalizações

Existem estudos, principalmente devido a Takacs, que generalizam o teorema para o caso contínuo que podem ser encontrados em , por exemplo. Predefinição:Referências