bc1414 – Passeio Aleatório

— Ruína do jogador —

Em um jogo, um jogador {A} começa com {i} reais e outro, {B}, com {j} reais, com {i+j=n}. Em cada rodada {A} vence com probabilidade {p}, de modo independente a cada rodada, e {B} com probabilidade {q:= 1-p}. Em cada rodada o vencedor leva {1} real (e o perdedor perde um real). O jogo continua até que a fortuna de {A} seja {0} ou {n}, nesse momento ele para de jogar.

Denotamos a quantia do jogador {A} no instante {t} pela variável {X_t} e temos {X_0=i} e as probabilidades de transição

\displaystyle  \begin{array}{rcl}  && p(0,0) = p(n,n) = 1\\ && p(i,i+1) = p ~ \textrm{ e }~ p(i,i-1) = q, \end{array}

para {1\leq i \leq n} definem um processo estocásticos sobre o conjunto de estados {S=\{0,1,2,\dots,n\}}. As demais transições têm probabilidade 0.

Vamos determinar a probabilidade de {A} chegar ao estado {n} antes do estado {0}, esse é um problema clássico da probabilidade conhecido como o problema da ruína do jogador.

Seja {P_i} a probabilidade de o jogador chegar antes ao estado {n} dado que {X_0=i}. Então

\displaystyle  P_i = pP_{i+1}+ qP_{i-1}

para todo {i\in\{1,\dots,n\}}, que equivale a

\displaystyle  pP_{i}+ qP_{i} = pP_{i+1}+qP_{i-1}

para todo {i\in\{1,\dots,n\}}. Para facilitar usaremos {q=1-p.} Segue da igualdade acima que

\displaystyle  \begin{array}{rcl}  P_{i+1} - P_i &=& \frac qp (P_i-P_{i-1})\\ &=& \left(\frac qp\right)^2 (P_{i-1}-P_{i-2})\\ &=& \cdots\\ &=& \left(\frac qp\right)^i (P_1-P_0). \end{array}

donde concluímos, usando que {P_0=0}, que

\displaystyle  P_{i+1} = P_i + \left(\frac qp\right)^i P_1  \ \ \ \ \ (44)

para todo {i\in\{1,\dots,n\}}. Iterando

\displaystyle  \begin{array}{rcl}  P_{i+1} &=& P_i + \left(\frac qp\right)^i P_1\\ &=& P_{i-1} + \left( \left(\frac qp\right)^{i-1}+\left(\frac qp\right)^i \right)P_1\\ &=& P_{i-2} + \left( \left(\frac qp\right)^{i-2}+\left(\frac qp\right)^{i-1}+\left(\frac qp\right)^i \right)P_1\\ &=& \cdots \\ &=& \left( 1+\frac qp+\cdots+ \left(\frac qp\right)^{i-2}+\left(\frac qp\right)^{i-1}+\left(\frac qp\right)^i \right)P_1 \end{array}

e de {P_n=1} temos

\displaystyle  1 = \left( 1+\frac qp+\cdots+ \left(\frac qp\right)^{n-2}+\left(\frac qp\right)^{n-1} \right)P_1.

Se {p\neq q} então a soma acima é de uma progressão geométrica cuja valor é {{1-(q/p)}/{1-(q/p)^n}} logo

\displaystyle  P_1 = \begin{cases} \displaystyle\frac 1n & \textrm{ se } p=q\\ \vspace*{-.3cm} \\ \displaystyle \frac {1-(q/p)}{1-(q/p)^n} & \textrm{ se } p\neq q. \end{cases}

e substituindo em (44)

\displaystyle  P_i = \begin{cases} \displaystyle \frac in & \textrm{ se } p=q\\\vspace*{-.3cm} \\ \displaystyle \frac {1-(q/p)^i}{1-(q/p)^n} & \textrm{ se } p\neq q. \end{cases}

Notemos que se {j} é muito grande ({j\rightarrow \infty}) a probabilidade do jogador {A} ficar “infinitamente rico” é {0} se {p \leq 1/2} pois {\frac in ,} e { \frac {1-(q/p)^i}{1-(q/p)^n}} tendem a {0} ({n\rightarrow \infty}), ou seja, a ruína de {B} é praticamente impossível.

Por outro lado, se {A} joga melhor que {B}, ou seja, {p >1/2} então {(q/p)^n\rightarrow 0} (quando {n\rightarrow \infty}) logo {P_i \sim 1-(q/p)^i >0} é a probabilidade de ruína de {B} (a de {A} é {\sim (q/p)^i}), ou seja, mesmo com capital menor, a habilidade melhor garante lhe garante menor chance de ruína.

— Passeio aleatório —

Sejam {Y_n}, para {n\in{\mathbb N}}, v.a. independentes com mesma distribuição {\mathop{\mathbb P}(Y_n=+1)= \mathop{\mathbb P}(Y_n=-1)=1/2} e {X_n := Y_1+\cdots+Y_n} que assumem valores no conjunto de estados {S = {\mathbb Z}}. No instante inicial {X_0=0} e as probabilidades das transições não-nulas são {p_{i,i-1} = p_{i,i+1} = 1/2} (passeio aleatório simétrico). O processo estocástico {(X_n)_{n\in{\mathbb N}}} assim definido é chamado de passeio aleatório em uma dimensão.

O passeio aleatório é um processo homogêneo com respeito ao tempo, que significa que a probabilidade de ir do estado {i} ao estado {j} em {n} passos não depende do instante particular que o processo se encontra em {i}, ou seja,

\displaystyle \mathop{\mathbb P}(X_{m+n}= j~|~X_m=i)=\mathop{\mathbb P}(X_{k+n}= j~|~X_k=i)

para quaisquer {i,j,k,m,n}.

Um retorno à origem ocorre no instante {n} se {X_n=0}. O evento {X_n=0} só ocorre para {n} par, digamos {n=2m} para {m\geq 1}. A quantidade de caminhos de tamanho {2m} é {2^{2m}}, pois cada passo tem duas possibilidades, esquerda ou direita. Desses, os que retornam para a origem são os que metade dos passos são pra direita e metade pra esquerda, portanto se escolhemos quais instantes são passos para a direita, nos restantes os passos são para a esquerda, ou seja, a quantidade de tais caminhos são {\binom {2m}m} e

\displaystyle \mathop{\mathbb P}(X_{2m}=0)= \binom {2m}m2^{-2m}

e nos outros casos {\mathop{\mathbb P}(X_{n}=0)=0}.

Podemos escrever a função geradora de probabilidade do retorno {R(S)} tomando {r_n:=\mathop{\mathbb P}(X_n=0)}

\displaystyle  \begin{array}{rcl}  R(s) = \sum_{n\geq 0} r_n s^n &=& \sum_{m\geq 0} \binom {2m}m2^{-2m} s^{2m}\\ &=& \sum_{m\geq 0} \binom {2m}m \left(\frac{s^2}4\right)^{m}\\ =\frac 1{\sqrt{1-s^2}} \end{array}

para todo {s\in (-1,1)}.

Dentre os retornos à origem, destacamos especial atenção ao primeiro retorno, isto é, estamos interessados na probabilidade do passeio retornar a origem em algum momento futuro

\displaystyle T_0 := \min\{ n >0\colon X_n=0\}.

Denotemos por {p_k} a probabilidade de primeiro retorno a origem em {k} passos, {p_1=\mathop{\mathbb P}(X_1=0)} e para {k>1}

\displaystyle p_k = \mathop{\mathbb P}\big(X_1\neq 0,~X_2\neq 0,\dots,X_{k-1}\neq 0,X_k= 0\big) = \mathop{\mathbb P}(T_0=k).

As probabilidades de retorno {r_n} e {p_k} estão relacionadas da seguinte maneira, para todo {n\geq 1}

\displaystyle  r_n = \sum_{k=1}^n p_kr_{n-k}. \ \ \ \ \ (45)

De fato,

\displaystyle  \begin{array}{rcl}  r_n &=& \sum_{k=1}^n \mathop{\mathbb P}(X_n=0~|~X_1\neq 0,~X_2\neq 0,\dots,X_{k-1}\neq 0,X_k= 0)p_k\\ &=& \sum_{k=1}^n \mathop{\mathbb P}(X_n=0~|~X_k= 0)p_k \end{array}

usando a homogeneidade {\mathop{\mathbb P}(X_n=0~|~X_k= 0) = \mathop{\mathbb P}(X_{n-k}=0) = r_{n-k}}.

Vamos usar {R(s)} para determinar a função geradora de probabilidade do primeiro retorno {P(S)}

\displaystyle P(s)=\sum_{k\>1}p_ks^k.

Agora, a função geradora da probabilidade de retorno pode ser reescrita como

\displaystyle  \begin{array}{rcl}  R(s) &=& 1+ \sum_{n\geq 1} r_ns^n \\ &=& 1+ \sum_{n\geq 1}\left(\sum_{k=1}^n p_kr_{n-k}\right) s^n \\ &=& 1+ \sum_{n\geq 2}\left(\sum_{k=1}^{n-1} p_kr_{n-k}\right) s^n + \sum_{n\geq 1} p_nr_0 s^n \\ &=& 1+ \sum_{n\geq 2}\left(\sum_{k=1}^{n-1} p_kr_{n-k}\right) s^n + \sum_{n\geq 1} p_n s^n \\ &=& 1+ P(s)(R(s)-1) +P(s)\\ &=& 1+ P(s)R(s) \end{array}

portanto,

\displaystyle  P(s) = 1- \sqrt{1-s^2}.

O processo retorna a origem com probabilidade

\displaystyle  \sum_{n\geq 0}p_n = P(1) = 1

além disso o tempo esperado para o retorno é

\displaystyle  \sum_{n\geq 0}np_n = P'(1) = \infty.

Se {\mathop{\mathbb P}(T_0 < \infty) = \sum_{n\geq 0}p_n =1} então dizemos que o passeio é recorrente. Se {\mathop{\mathbb P}(T_0 < \infty) < 1} então dizemos que o passeio é transiente.

Exercício 17 Verifique que {P'(s) = 2sR(s)} e então conclua que

\displaystyle  p_{2m+2} = \frac 1{m+1}r_{2m} = \frac 1{m+1} r_{2m} = \frac 1{m+1}\binom{2m}m2^{-2m}.

Exercício 18 Deduza da aproximação de Stirling que

\displaystyle r_{2m} \approx \frac 1{\sqrt{\pi m}}.

Exercício 19 Considere transições

\displaystyle p_{i,i-1}=p \,\text{ e }\, p_{i,i+1}=q

com {p+q=1}. Mostre que também vale {P(s)= 1+P(s)R(s)} e ainda {R(s)= (1-4pqs^2)^{-1/2}} e {P(s)=1- (1-4pqs^2)^{1/2}}. Conclua que se {p\neq 1/2} então o passeio é transiente.

Exercício 20 Considere

\displaystyle p_k(r) = \mathop{\mathbb P}\big(X_1\neq r,~X_2\neq r,\dots,X_{k-1}\neq r,X_k= r\big)

a probabilidade da primeira visita ao estado {r} em {k} passo, e sua função geradora

\displaystyle P_r(s) = \sum_{k\geq 0} p_k(r)s^k.

Prove que {P_1(s) = (1/s)\left(1-\sqrt{1-s^2}\right)} e que {P_r(s) = (P_1(s))^r}.

Exercício 21 Sejam {e_1=(1,0)}, {-e_1=(-1,0)}, {e_2=(0,1)} e {-e_2=(0,-1)}. Consideremos o passeio aleatório em duas dimensões, em que o conjunto de estados é {S={\mathbb Z}\times{\mathbb Z}}, o estado inicial é {X_0= (0,0)} e {X_{i+1} = X_i \pm e_j} sendo que cada um dos quatro possíveis casos para {\pm e_j} têm a mesma probabilidade, a saber {1/4}. Essa descrição corresponde ao passeio aleatório em duas dimensões. Prove que o retorno a origem é certo, ou seja, o passeio aleatório é recorrente.

Exercício 22 Formalize o passeio aleatório em três dimensões e prove que é transiente.

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s