Page 32 - flip-procesos

✐ ✐

“ProcesosMathBookFC” — 2012/2/2 — 10:58 — page 24 — #30
✐ ✐

24 2. Caminatas aleatorias

caminata visita el estado n 1. Usando an´alisis del primer paso (es
decir, condicionando sobre si el primer paso se efect´ua a la izquierda
oaladerecha) demuestre que

p q n si p 1 2,
P τ n (2.18)
1 si p 1 2.
En particular, la probabilidad de que la caminata se mantengasiempre
en el conjunto ... , 1, 0, 1,... ,n 1 es 1 p q n en el caso p 1 2, y
con probabilidad uno llegar´a al estado n en el caso p 1 2. Generalice
la f´ormula (2.18) en el caso cuando el estado inicial es m,menor o
mayor a n.

12. Un algoritmo aleatorio de b´usqueda del estado cero operadel siguiente
modo: si se encuentra en el estado k en alg´un momento, entonces el
estado del algoritmo al siguiente paso es aleatorio con distribuci´on
uniforme en el conjunto 0, 1,... ,k 1 .Encuentre eln´umero esperado
de pasos en los que el algoritmo alcanza el estado cero cuando inicia
en el estado k.

13. Recurrencia. Sea X n : n 0 una caminata aleatoria simple sobre Z
0. Sea f ij la probabilidad de que eventualmente la
que inicia en X 0
caminata visite el estado j apartir del estado i,es decir,

f ij P X n j para alguna n 1 X 0 i .

Lleve a cabo cada uno de los siguientes pasos para encontrar nueva-
mente la probabilidad de un eventual retorno a la posici´on deorigen
f 00 .

2
f .
a) Demuestre que f 1,1 f 1,0 f 01 01
b) Condicionando sobre el primer paso de la caminada, demuestre
que f 00 pf 10 qf 1,0 pf 10 qf 01 .
c) Usando la misma t´ecnica que en el inciso anterior demuestre que
2
f 01 p qf .
01
d) Resuelva la ecuaci´on cuadr´atica del inciso anterior y obtenga las
dos ra´ıces f 01 1,p q.

✐ ✐

✐ ✐