notas-passeios-aleatórios (Renato Jacob Gava)

Prévia do material em texto

UMA PITADA DE PASSEIOS ALEATÓRIOS
RENATO JACOB GAVA
1. Introdução
Suponha que um jogador entre num cassino com 20 reais em dinheiro
para apostar. Assuma que ele participe de um jogo que consiste de
apostas independentes e que em cada aposta de 1 real ou ele ganhe um
real com probabilidade p ou perca um real com probabilidade 1−p. Se a
fortuna do cassino for de 100 reais e o jogador apostar indefinidamente,
isto é, apostar até ficar sem dinheiro ou até obter 120 reais, pergunta-
se: qual é probabilidade de que o jogador vença a disputa. Conhecido
como a rúına do jogador, este problema pode ser visto como um passeio
aleatório. Outra questão interessante a seu respeito tem a ver com o
tempo de duração do jogo. Teria ele probabilidade positiva de durar
para sempre?
Agora pensemos em outro problema. Imagine uma eleição para re-
presentante discente de uma turma e suponha os votos válidos sejam
100. Suponha que o candidato A obtenha 60 votos e que o candidato
B obtenha 40 votos. Dada a diferença significativa de votos entre A
e B, pergunta-se qual é a probabilidade de que A lidere a apuração
do ińıcio ao fim. Considerando todas as trajetórias de apuração equi-
prováveis, podemos responder a esta questão usando coeficientes bi-
nomiais e o pŕıncipio da reflexão, ferramenta importante no estudo de
passeios aleatórios.
Estes são dois exemplos de processos estocásticos que podem ser es-
tudados a partir da teoria de passeios aleatórios. Em geral, podemos
ver um passeio aleatório como a posição de uma part́ıcula ao longo
do tempo. A cada instante de tempo n ∈ {0, 1, . . .} a part́ıcula rea-
liza um salto aleatório de acordo com uma determinada distribuição.
Portanto, a posição Sn da part́ıcula no instante n será uma soma de
variáveis aleatórias (v.a.’s); na maior parte de nossos exemplos as v.a.’s
serão independentes e identicamente distribúıdas (i.i.d.). Podemos en-
contrar aplicações da teoria de passeios aleatórios em diversas áreas do
conhecimento tais como estat́ıstica, f́ısica, economia, computação e bi-
ologia. Nestas notas limartar-nos-emos aos passeios aleatórios simples,
ou seja, aos passeios cujos saltos tem tamanho um. Estas curtas notas
estão baseadas nas obras [1, 2, 3]. Nelas o leitor interessado encontrará
2 RENATO JACOB GAVA
muitos mais exemplos e aplicações de passeios aletários, além do de-
senvolvimento bastante mais amplo da teoria acerca do assunto. Vale
salientar, por fim, que o tema passeios aleatórios é atualmente objeto
de pesquisas acadêmicas mundo afora, tanto em matemática como em
f́ısica.
2. Definição e resultados elementares
Definição 2.1. Seja {Xn}n≥1 uma de v.a.’s i.i.d. com P(Xn = 1) = p
e P(Xn = −1) = q para todo n ≥ 1, com p+ q = 1. Sejam S0 = c e
Sn = c+
n∑
i=1
Xi, n ≥ 1.
A sequência de v.a.’s {Sn, n ≥ 0} é chamada de passeio aleatório sim-
ples (PAS).
Quando p = 1/2 na definição 2.1 dizemos que o PAS é simétrico
(PASS). Quando p 6= 1/2, chamamo-lo de assimétrico (PASA).
É fácil ver que na dinâmica da rúına do jogador o capital acumulado
pelo jogador ao longo das apostas pode ser visto como um passeio
aleatório simples. Nesse caso, a variável aleatóriaXi representa o ganho
do jogador na i-ésima jogada.
Exemplo 2.2. Defina S0 = i, i > 0 e
Sn+1 =
{
0, se Sn = 0
Sn +Xn+1, se Sn > 0
,
onde {Xn}n≥1 é uma sequência de v.a.’s i.i.d. com P(Xn = 1) = p e
P(Xn = −1) = q para todo n ≥ 1. Aqui temos um passeio aleatório
com barreira absorvente na origem.
Exemplo 2.3. Considere o espaço de estados {0, 1, · · · , d} e variáveis
aleatórias independentes entre si tais que
P(Xn+1 = 1) = p e P(Xn+1 = −1) = q; se Sn ∈ {1, 2, . . . , d− 1}
P(Xn+1 = 1) = p e P(Xn+1 = 0) = q; se Sn = 0
P(Xn+1 = 0) = p e P(Xn+1 = −1) = q; se Sn = d.
Temos neste caso um passeio aleatório com barreiras de retenção.
Exemplo 2.4. Seja (Xn, n ≥ 1) uma coleção de variáveis aleatórias
independentes tais que
P(Xn+1 = 1) = λn P(Xn+1 = −1) = µn,
onde λn + µn = 1. Temos um passeio aleatório não homogêneo.
Exemplo 2.5. Considere uma part́ıcula realizando um passeio aleató-
rio sobre os vértices do quadrado {(0, 0), (0, 1), (1, 0), (1, 1)}. Ponha
UMA PITADA DE PASSEIOS ALEATÓRIOS 3
a = (xa, ya), b = (xb, yb) e considere {Sn}n≥0 o seguinte PAS sobre os
vértices do quadrado
P(Sn+1 = b|Sn = a) =
1
2
, se |xa − xb|+ |ya − yb| = 1
P(Sn+1 = b|Sn = a) = 0, caso contrário.
Aqui a cada passo a part́ıcula escolhe saltar para um dos vértices vizi-
nhos com a mesma probabilidade.
Exerćıcio 2.6. Nas condições do exemplo anterior, calcule o tempo
médio que o PAS leva para atingir o vértice (1, 1) saindo de (0, 0).
Definição 2.7. Sejam n ≤ m dois inteiros positivos. Sejam r e s dois
inteiros. Um caminho de (n, s) a (m, t) é uma sequência de pontos
{(i, si)}n≤i≤m tal que sn = s. sm = t e |si − si+1| = 1 para n ≤ i ≤ m.
Teorema 2.8. Sejam k e n ≥ 0 inteiros. Se n+ k for par, então
P(Sn = k) =
(
n
n+s
2
)
p
n+k
2 (1− p)
n−k
2
Demonstração. Considere uma realização do passeio aleatório de (0, 0)
a (n, s). Sejam r o número de passos positivos e s o número de passos
negativos. Observe que r + s = n e r − s = k. Resolvendo esse
sistema linear, temos r = n+k
2
e s = n−k
2
, ou seja, há
(
n
n+s
2
)
caminhos
que conectam (0, 0) a (n, k). Como cada caminho possui a mesma
probabilidade de ocorrer, obtemos
P(Sn = k) =
(
n
n+s
2
)
p
n+k
2 (1− p)
n−k
2 .
�
Proposição 2.9 (Prinćıpio da reflexão). Sejam r e s inteiros posi-
tivos. Então o número de caminhos que vão de (0, r) a (n, s) e tocam
o eixo x é igual ao número de caminhos de (0,−r) a (n, s).
Demonstração. Omitida. �
Proposição 2.10. Sejam 0 < s < n inteiros com n+s par. O número
de caminhos de (0, 0) a (n, s) com s0 = 0, s1 >, s2 > 0, . . . , sn−1 > 0 e
sn = s é (
n− 1
n+s
2
− 1
)
−
(
n− 1
n+s
2
)
=
s
n
(
n
n+s
2
)
Demonstração. Estamos interessados apenas nos caminhos que perma-
necem no primeiro quadrante. Para tanto, observe que o primeiro passo
tem de ser para cima.
Assim, contemos o número de caminhos de (1, 1) a (n, s). Conside-
rando r o número de passos positivos e t o número de passos negativos,
4 RENATO JACOB GAVA
temos que r + t = n− 1 e r − t = s− 1. A resolução do sistema linear
nos dá r =
n+ s
2
− 1 e s = n− s
2
, ou seja, há
(
n− 1
n+s
2
− 1
)
caminhos
que conectam (1, 1) a (n, s).
Agora temos de subtrair desse número os caminhos que vão de (1, 1)
a (n, s) e tocam o eixo x. Observemos que para todo caminho que
vai de (1, 1) a (n, s) e toca o eixo x, pelo prinćıpio da reflexão, há
um caminho que vai de (1,−1) a (n, s), isto é, temos de subtrair os
caminhos que vão de (1,−1) a (n, s), que são(
n− 1
n+s
2
)
.
Portanto, o número de caminhos que vão de (0, 0) a (n, s) e permane-
cem no primeiro quadrante é dado por(
n− 1
n+s
2
− 1
)
−
(
n− 1
n+s
2
)
.
�
Exerćıcio 2.11. Mostre que(
n− 1
n+s
2
− 1
)
−
(
n− 1
n+s
2
)
=
s
n
(
n
n+s
2
)
Exemplo 2.12. Considere a hipotética eleição discente da introdução.
Se o candidato A obteve 60 e o candidato B 40 votos, para obter a
probabilidade de que A lidere a apuração eleitoral do ińıcio ao fim temos
de contar o número de caminhos que vão de (0, 0) a (100, 20) e não
tocam o eixo x e dividir pelo número de caminhos que vão (0, 0) a
(100, 20), ou seja, (
99
59
)
−
(
99
60
)(
100
60
) = 20
100
=
1
5
.
Exemplo 2.13. Suponha que numa eleição após a contagem dos votos
o candidato A tenha obtido a votos e o candidato B, b votos, com
a > b. Qual é a probabilidade de que o candidato A tenha liderado a
contagem de votos do ińıcio ao fim? O teorema anterior nos diz que
esta probabilidade é
a− b
a+ b
.
Exerćıcio 2.14. Calcule o número de caminhos que vão de a = (xa, ya)
a b = (xb, yb) e não tocam o eixo y = c, ou seja, s0 = ya, sn = yb e
si > c para i = 1, . . . , n− 1, para
i) a = (0, 0), b = (12, 6) e c = 0;
ii) a = (0, 0), b = (11, 5) e c = −1;
iii) a = (0, 1), b = (16, 7) e c = 0;UMA PITADA DE PASSEIOS ALEATÓRIOS 5
iv) a = (0, 1), b = (16, 9) e c = −2;
v) a = (0, 1), b = (16, 10) e c = −2;
Considerando todos os caminhos de a a b equiprováveis, calcule a pro-
babilidade de que um caminho que parte de a e toca b não toque a reta
y = c.
3. O problema da rúına do jogador
Agora voltamos nossa atenção para o problema da rúına do jogador
descrito na introdução. Podemos identificar o a dinâmica da rúına do
jogador com um passeio aleatório simples com dois pontos absorventes.
De modo geral, suponha que a fortuna inicial do jogador seja i e que
ele joga até atingir a fortuna de N ou 0 reais, 0 < i < N . A cada
aposta ele ganha um real com probabilidade p ou perde um real com
probabilidade q. Assim, seja Sn a fortuna do jogador após n rodadas.
Temos que S0 = i e que
Sn = i+
n∑
j=1
Xj,
onde {Xj}j≥1 são v.a.’s i.i.d. com P(Xj = 1) = p, P(Xj = −1) = q e
p+ q = 1.
Para encontrar a probabilidade de que o jogador quebre a banca,
seja Pi a probabilidade de que o jogador eventualmente atinja N . Con-
dicionando no valor do primeiro passo, obtemos
Pi = Pi+1p+ Pi−1q para i ∈ {1, . . . N − 1}.
Em seguida, observe que
pPi + qPi = Pi+1p+ Pi−1q,
o que implica que
Pi+1 − Pi =
q
p
(Pi − Pi−1).
Fazendo a indução em i e aplicando a condição inicial P0 = 0, temos
Pi+1 − Pi =
(q
p
)i
(P1 − P0) =
(q
p
)i
P1.
Usemos esse resultado para obter uma expressão para a seguinte soma
telescópica
Pi − P1 =
i−1∑
j=1
(Pj+1 − Pj) = P1
(q
p
+
(q
p
)2
. . .+
(q
p
)i−1)
.
Isto é,
Pi =
 P1
1− (q/p)i
1− q/p
, se p 6= q
P1i, se p = q
6 RENATO JACOB GAVA
Usando a condição inicial PN = 1, obtemos
P1 =

1− (q/p)
1− (q/p)N
, se p 6= q
1
N
, se p = q
Assim, conclúımos que
Pi =

1− (q/p)i
1− (q/p)N
, se p 6= q
i
N
, se p = q
.(1)
Exemplo 3.1. Suponha que a fortuna do jogador seja de 5 reais, que
p = 0, 6, q = 0, 4 e que ele deseje obter um lucro de 10 reais. Assim,
N = 15 e a fórmula (1) nos dá
P5 =
1− (2/3)5
1− (2/3)15
≈ 0, 866.
Suponha agora que nosso jogador é ambicioso e quer ganhar muito
dinheiro com suas apostas. O que ocorre com sua probabilidade de
vitória quando N →∞? Tomando o limite em (1) temos
lim
N→∞
Pi =
{
1− (q/p)i, se p > q
0, se p ≤ q .
Ou seja, se sua chance de sucesso p a cada rodada for p ≤ 1/2, então
perderá a disputa com probabilidade 1. Se p > 1/2, ele tem probabili-
dade positiva de enriquecer ilimitadamente.
Exemplo 3.2. Usando os parâmetros do Exemplo 3.1, isto é, p = 0, 6,
q = 0, 4 e i = 5, obtemos
lim
N→∞
P5 = 1− (2/3)5 ≈ 0, 868.
A fim de encontrar o tempo médio de duração do jogo precisamos
da definição e do teorema que seguem.
Definição 3.3 (Tempo de parada). Seja {Xn}n≥1 uma seqüência de
v.a. independentes. Uma v.a. τ é chamada de tempo de parada para
esta seqüência se o evento {τ = n} é independente de Xi para todo
i ≥ n+ 1.
No caso de um passeio aleatório o tempo de primeira passagem é um
exemplo de tempo de parada. Intuitivamente, observando a realização
de X1, . . . , Xn sabemos se o evento {τ = n} ocorre ou não, ou seja, a
ocorrência de {τ = n} não depende de Xn+1, Xn+2, . . .
Exemplo 3.4. Considere {Sn}n≥0 o PAS definido na seção anterior.
Defina
T = max{n ≥ 1;Sn = 0}
UMA PITADA DE PASSEIOS ALEATÓRIOS 7
T é o tempo de última passagem do passeio pelo śıtio 0. T não é tempo
de parada, já que o evento {τ = 5} dependente de Xi para todo i ≥ 6.
Teorema 3.5 (Equação de Wald). Seja {Xn}n≥1 uma sequência de
v.a.’s i.i.d. inteiras com E(|Xi|) < ∞ e seja τ um tempo de parada
para {Xn}n≥1 com E(τ) <∞, então
E(
τ∑
i=1
Xi) = E(τ)E(X1).
Agora usemos a equação de Wald para obter uma fórmula para o
tempo médio de duração do jogo. Seja
τ = min{n ≥ 1;Sn = 0 ou Sn = N}
Observe que τ é um tempo de parada e assuma que E(τ) < ∞ (ver
Exerćıcio 3.6). Analisemos o caso em que p 6= q. Temos que
Sτ = i+
τ∑
j=1
Xj =

0, com prob.
(q/p)i − (q/p)N
1− (q/p)N
N, com prob.
1− (q/p)i
1− (q/p)N
.
Pela equação de Wald,
E(Sτ ) = N
1− (q/p)i
1− (q/p)N
= i+ (2p− 1)E(τ),
o que implica que
E(τ) =
i
1− 2p
− N
1− 2p
1− (q/p)i
1− (q/p)N
.(2)
Exerćıcio 3.6. Para obter a expressão 2 assumimos que E(τ) <∞. A
partir da definição do problema da rúına do jogador, prove que E(τ) <
∞ para todo p ∈ (0, 1).
Exerćıcio 3.7. Considere p = q = 1/2. Seja Di o tempo médio de
duração do jogo dado que a fortuna inicial do jogador é i ∈ {1, 2, . . .
N − 1}.
i) Mostre que
Di =
1
2
Di−1 +
1
2
Di+1 + 1(3)
ii) Quais são as condições iniciais D0 e DN?
iii) Mostre que i(N − i) é solução de (3).
Exerćıcio 3.8. Um jogador faz uma série de apostas de um real. Ele
decide parar de apostar assim que ganhar R$40 ou quer perder R$10.
Calcule a probabilidade de rúına do jogador e o número de apostas até
que o jogo acabe se i) p = q = 1/2 e e ii) se p = 9/19 e q = 10/19.
8 RENATO JACOB GAVA
4. Recorrência e trasiência
Nesta seção voltamos a lidar com o PAS {Sn}n≥0, definido no ińıcio
da Seção 2, e assumiremos sem perda de generalidade que S0 = 0.
Estudaremos brevemente a recorrência e a transiência do PAS em Z e
sua dependência em relação ao parâmetro p. Considere a seguinte v.a
definida por
Ti = min{n ≥ 1;Sn = i}.
Observe que Ti é um tempo de parada.
Definição 4.1. Dizemos que o PAS é recorrente se P(Ti < ∞) = 1.
Se P(Ti <∞) < 1, dizemos que o PAS é transiente.
Intuitivamente, recorrência significa que o passeio visitará o śıtio i
em algum momento, o que por sua vez implica que o śıtio i será visitado
infinitas vezes. Transiência significa que há probabilidade positiva de
o passeio nunca visitar o śıtio i, o que por sua vez implica que o śıtio i
será visitado um número finito de vezes ao longo do tempo.
Teorema 4.2. Para o PAS em Z, as seguintes afirmações são equiva-
lentes:
i) P(T0 <∞) = 1
ii)
∑∞
n=0 P(Sn = 0) =∞
Demonstração. Omitida. �
Introduza agora o número de visitas V0 ao śıtio 0 ao longo do tempo.
Note que
V0 =
∞∑
n=0
1{Sn=0}(4)
Então
E(V0) = E(
∞∑
n=0
I{Sn=0}) =
∞∑
n=0
E(I{Sn=0}) =
∞∑
n=0
P(Sn = 0),
onde I{Sn=0} é uma variável indicadora, isto é,
I{Sn=0} =
{
1, se Sn = 0
0, se Sn 6= 0
.
Se
∑∞
n=0 P(Sn = 0) < ∞, podemos afirmar diretamente de (4) que
P(V0 < ∞) = 1, justicando a intuição de que a transiência do śıtio 0
significa que ele é visitado finitas vezes ao longo do processo.
Exerćıcio 4.3. Seja X uma v.a. inteira não-negativa. Mostre que
E(X) =
∑
i≥1 P(X ≥ i) e que E(X) <∞ implica P(X <∞) = 1.
Teorema 4.4. O PAS em Z é recorrente se e somente se p = q = 1/2.
UMA PITADA DE PASSEIOS ALEATÓRIOS 9
Demonstração. Basta analisar o śıtio 0, já que o modelo é invariante
por translação. Usemos o Teorema 4.2 e mostremos que
∞∑
n=0
P(Sn = 0) =∞ se e só se p = q = 1/2.
É fácil ver que o retorno ao śıtio 0 ocorre apenas num número par de
passos. Usando os resultados da Seção 2 obtemos
P(S2n = 0) =
(
2n
n
)
pnqn.
O próximo passo da prova requer o uso da fórmula de Stirling. A
fórmula de Stirling nos garante que
n! ∼
√
2πnnne−n
onde o śımbolo ∼ significa que
lim
n→∞
n!√
2πnnne−n
= 1.
Aplicando a fórmula de Stirling ao coeficiente
(
2n
n
)
obtemos que(
2n
n
)
∼ 2
2n
√
πn
,
o que implica que
P(S2n = 0) ∼
(4pq)n√
πn
.(5)
Agora analisemos (5) em função de p. Se p 6= q, temos 4pq < 1. Logo
existe n0 inteiro tal que se n ≥ n0
P(S2n = 0) ≤
(4pq)n√
π
,
o que implica que
∞∑
n=0
P(S2n = 0) <∞,
ou seja, chegamos à conclusão de que o śıtio 0 é transiente se p 6= q.
Por outro lado, se p = q = 1/2, temos 4pq = 1. Então
P(S2n = 0) ∼
1√
πn
,
mas disso resulta que
∞∑
n=0
P(S2n = 0) =∞,
e a recorrência do śıtio 0 está provada. �
10 RENATO JACOB GAVA
Apresentamos abaixo mais uma aplicação da equação de Wald para
o PASS.
Exemplo 4.5. Considere um PASS com p > 1
2
. O número esperado
de passos até o passeio alcançar a posição k, k > 0 é
E(τ) =
k
2p− 1
Observe que E|X1| = 1 <∞ e que, no instante τ ,
∑τ
j=1Xj = kcom
probabilidade 1, o que implica
E(
τ∑
j=1
Xj) = k
Como E(X1) = 2p−1, obtemos o resultado através da equação de Wald.
Exerćıcio 4.6. Use a fórmula de Stirling para demonstrar que(
2n
n
)
∼ 2
2n
√
πn
.
Exerćıcio 4.7. Demonstre passo a passo que se p = q = 1/2, então
∞∑
n=0
P(S2n = 0) =∞.
Referências
[1] W. Feller, An Introduction to Probability Theory and its Applications, Wiley,
New York,1966.
[2] S.H. Ross, Introduction to Probability Models, Academic Press, New York,
2010.
[3] R. Schinazi, Classical and Spatial Stochastic Processes with Applications to
Biology, Birkhauser, New York, 2010.
UFSCAR - Departamento de Estat́ıstica.
Rodovia Washington Luiz, Km 235, CEP 13565-905, São Carlos, Brasil
e-mail: gava@ufscar.br