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$ $\forall i=1,\cdots ,n$ é dada por ${\frac {b}{n}}$, em outras palavras:

${\mathcal {P}}(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)={n \choose {\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)={n-1 \choose {\frac {n+b-2}{2}}}-{n-1 \choose {\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}\neq 0$. Como todo caminho tem a mesma probabilidade de ocorrer, vale:

${\mathcal {P}}(S_{i}\neq S_{n}\forall i<n|S_{n}=b)={\mathcal {P}}(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:

${\mathcal {P}}(S_{i}\neq S_{n}\forall i<n|S_{n}=b)={\frac {|b|}{n}}{\mathcal {P}}(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.