Arboles-planos-aleatorios-y-sus-aplicaciones-a-los-procesos-de-ramificacion

Vista previa del material en texto

UNAM – Dirección General de Bibliotecas 
Tesis Digitales 
Restricciones de uso 
 
DERECHOS RESERVADOS © 
PROHIBIDA SU REPRODUCCIÓN TOTAL O PARCIAL 
 
Todo el material contenido en esta tesis esta protegido por la Ley Federal 
del Derecho de Autor (LFDA) de los Estados Unidos Mexicanos (México). 
El uso de imágenes, fragmentos de videos, y demás material que sea 
objeto de protección de los derechos de autor, será exclusivamente para 
fines educativos e informativos y deberá citar la fuente donde la obtuvo 
mencionando el autor o autores. Cualquier uso distinto como el lucro, 
reproducción, edición o modificación, será perseguido y sancionado por el 
respectivo titular de los Derechos de Autor. 
 
 
 
Árboles Planos Aleatorios y sus
Aplicaciones a los Procesos de
Ramificación.
Serena Pérez Zanco.
Datos del Jurado
Datos del jurado
1. Datos del alumno
 Pérez
 Zanco 
 Serena
 55 54 64 39
 Universidad Nacional Autónoma de México
 Facultad de Ciencias
 Matemáticas
 40306570-5
2. Datos del tutor
 Dr.
 Gerónimo Francisco
 Uribe
 Bravo
3. Datos de sinodal 1
 Dra
 María Emilia
 Caballero
 Acosta
5. Datos de sinodal 3
 Dr 
 Ricardo 
 Gómez
4. Datos sinodal 2
 Dra.
 Ana
 Meda
 Guardiola
6. Datos de sinodal 4
 Mat
 José Luis Ángel
 Pérez 
 Garmendia
7. Datos del trabajo escrito
 Árboles Planos Aleatorios y sus Aplicaciones a los Procesos de Ramificación
 72 p.
 2008
Agradecimientos
Es d́ıficil saber que escribir en los agradecimientos. La verdad me he encontrado varios
d́ıas, con la vista en la computadora sin saber a quien agradecer. No creo que sea
porque no hay nadie a quien agradecer, mas bien, el problema reside en el como.
Creo que seŕıa poco correcto no agradecer a la Universidad Nacional Autónoma de
México por darme una educación completa, variada, PÚBLICA y GRATUITA; Por
darme la posibilidad de crecer intelectualmente junto y gracias a las personas que
son parte de la Facultad de Ciencias. Ya en términos más particulares, me gustaŕıa
agradecer al Instituto de Matemáticas por darme una beca para la realización de
mi tesis; darme un espacio para trabajar, la oportunidad de estar en contacto con
brillantes investigadores y poder acceder a material de investigación. En particular,
quisiera agradecer a la Dra. Maria Emilia Caballero por apoyarme y siempre darme
una mano cuando lo necesité.
También quisiera agradecer a mis Sinodales: Dra. Ana Meda por ser tan amable y
disponible; Dr. Ricardo Gómez, por las correcciones y las porras; José Luis Pérez, por
soportar mis frustraciones, durante y todav́ıa ahora, la realizacion de esta tesis.
No tengo palabras para describir el inmenso agradecimiento que le tengo a mi grandioso
Director de Tesis, Dr. Gerónimo Uribe. La verdad sin tu ayuda, tu paciencia y tu ded-
icación esta tesis todav́ıa seria un sueño. Muchas gracias por tenerme la confianza
de poder hacer un trabajo aśı y espero de todo corazón no haberte defraudado. Haz
sido un dedicado compañero de trabajo, un maestro inspirador y un amigo envidiable.
MUCHAS GRACIAS.
ii
iii
También, quisiera agrader a mis tios, tias primoa y primas de las dos partes. La familia
no se cambia por nada y ustedes son la familia perfecta. Por último quisiera agradecer
a mis papás y mi hermana. A mi hermana, que siempre me apoya en los momentos
dif́ıciles y que abŕıo el camino para que yo pudiera pasar, la mejor de las hermanas
mayores. A mis papás por el apoyo incondicional que siempre me han brindado, por
darme la posibilidad de conocer y descubrir, gracias a su trabajo duro que siempre
fue inspirador a no darnos por vencidos.
Contenido
Agradecimientos II
Notación y abreviaturas VI
Introducción VII
1. El Proceso de Galton y Watson 1
1.1. Descripción informal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. Modelo matemático . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3. El proceso de Galton y Watson como martingala . . . . . . . . . . . . . 3
1.4. Extinción y supervivencia del proceso Galton y Watson . . . . . . . . . 4
2. El árbol de Galton y Watson (sub)cŕıtico 9
2.1. Árboles planos finitos. . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1. Propiedades Básicas . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.2. Codificación de árboles planos finitos . . . . . . . . . . . . . . . 13
2.2. Construcción del árbol GW (sub)cŕıtico . . . . . . . . . . . . . . . . . . 19
2.2.1. Construcción del árbol aleatorio . . . . . . . . . . . . . . . . . . 19
2.2.2. Distribución del árbol de Galton y Watson . . . . . . . . . . . . 22
iv
CONTENIDO v
2.2.3. Codificación del árbol aleatorio y caminatas aleatorias . . . . . 25
3. El árbol GW general y cómo sesgarlo. 28
3.1. El árbol de Galton y Watson . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2. Construcción heuŕıstica del árbol sesgado. . . . . . . . . . . . . . . . . 33
3.3. Formalización a partir del teorema de Parthasarathy. . . . . . . . . . . 37
3.4. El teorema de Parthasarathy y de Kolmogorov. . . . . . . . . . . . . . 42
4. Árbol sesgado y el proceso de GW 46
4.1. Preliminares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2. Caso supercŕıtico: teorema de Kesten-Stigum . . . . . . . . . . . . . . . 50
4.3. Caso subcŕıtico: teorema de Heathcote . . . . . . . . . . . . . . . . . . 54
4.4. Caso cŕıtico: teorema de Kolmogorov-Yaglom . . . . . . . . . . . . . . . 60
A. Teoremas y definiciones de la teoŕıa de la probabilidad 67
Bibliograf́ıa 70
Notación y abreviaturas
N El conjunto de los números naturales.
Z El conjunto de los números enteros.
R El conjunto de los números reales.
σ(·) σ-álgebra generada.
µ ¿ ν La medida µ es absolutamente continua con respecto a ν.
µ ⊥ ν Las medidas µ y ν son mutuamente singulares.
dν
dµ
La derivada de Radon-Nikodým de ν con respecto a µ.
µ− c.s Casi seguramente con respecto a la medida µ.
d
= Igualdad en distribución.
vi
Introducción
Los árboles aleatorios se han vuelto una herramienta para el estudio de los procesos
estocásticos como el de Galton y Watson y el movimiento Browniano. El pionero para
estas aplicaciones fue J. Neveu [Nev86] donde el propósito de su art́ıculo fue introducir
la noción formal de árbol en el caso más simple de los procesos de Galton y Watson e
ilustrarla con un ejemplo. Ahora el estudio se ha extendido a árboles reales y procesos
continuos, como los procesos de Lévy.
El objetivo principal de esta tesis es presentar una paráfrasis del art́ıculo [LPP95],
donde se utilizan árboles aleatorios en el estudio de los procesos de ramificación dis-
cretos. Más espećıficamente, se construirán los árboles de Galton y Watson y sus
correspondientes árboles sesgados por tamaño para demostrar tres teoremas clásicos
de los procesos de Galton y Watson.
La estructura del trabajo es la siguiente:
En el caṕıtulo 1 se da la descripción informal del proceso de Galton y Watson para
plantearlo matemáticamente de la manera clásica. Quisiéramos conocer el compor-
tamiento del proceso a la larga; nos preocupa la probabilidad de extinción o de super-
vivencia. Para esto se demostrará que es una martingala no negativa y por consiguiente
convergente. Los procesos de Galton y Watson se clasificarán en subcŕıticos, cŕıticos
y supercŕıticos.
En el caṕıtulo 2 se introducirá la noción de árbol plano finito. A los árboles finitos
se les asociarán dos órdenes: lexicográfico y de descendencia que serán importantes
para las pruebas de sus propiedades combinatorias. Definiremos también, árboles
vii
viii INTRODUCCIÓN
aleatorios asociados a una distribución de descendencia (sub)cŕıtica. Los tamaños
de las generaciones sucesivas del árbol aleatorio conformarán un proceso de Galton
y Watson y la función de altura será relevante para el estudio de la relaciónentre
árboles de Galton y Watson y caminatas aleatorias. Para el desarrollo de este caṕıtulo
se utilizó el art́ıculo [LG06].
En el caṕıtulo 3 generalizaremos la definición de árbol aleatorio de Galton y Wat-
son en el espacio de árboles (no necesariamente finitos). En el art́ıculo [LPP95] se
describe informalmente el árbol sesgado por tamaño. En este caṕıtulo, construiremos
formalmente la medida del árbol sesgado por tamaño utilizando el teorema de ĺımite
inverso de Parthasarathy. Durante el estudio para la construcción formal de la medida
del árbol sesgado se obsevará que el teorema de Parthasarathy en verdad es un caso
particular del teorema de consistencia de Kolmogorov.
Finalmente, en el caṕıtulo 4, haremos una paŕafrasis de las demostraciones de
los tres teoremas clásicos del proceso de Galton y Watson del caso supercŕıtico, sub-
cŕıtico y cŕıtico; teorema de Kesten-Stigum, de Heathcote y de Kolmogorov-Yaglom,
utilizando la medida del árbol sesgado por tamaño que fue desarrollado en el articulo
[LPP95]. Estos tres teoremas responden a una pregunta: ¿podemos estimar o encon-
trar el orden asintótico de la probabilidad de supervivencia? Para el caso supercŕıtico
y subcŕıtico tenemos el criterio llamado Llog+L y para el caso cŕıtico, la estimación
de Kolmogorov y la ley ĺımite de Yaglom.
Caṕıtulo 1
El Proceso de Galton y Watson
A lo largo de este trabajo nuestro objetivo de estudio son los árboles planos con
ráız y sus aplicaciones a los procesos de ramificación. En este caṕıtulo recordaremos
resultados importantes de los procesos de ramificación que nos serán útiles durante
el camino. Los procesos de ramificación han sido extensamente estudiados por su
interés matemático como una base teórica para el estudio de poblaciones. En particular
los modelos se han ajustado durante los años a las dinámicas de genes, neutrones y
rayos cósmicos [Har02]. A los procesos de ramificación se les puede pensar como una
representación matemática de la evolución de una población donde sus miembros se
reproducen y mueren bajo las leyes del azar. El proceso de Galton y Watson fue
diseñado para explicar las investigaciones estad́ısticas de Galton sobre la extinción de
los apellidos de los aristócratas victorianos. Galton formuló una pregunta espećıfica,
a la cual Watson respondió. Juntos escribieron el art́ıculo [WG75].
1.1. Descripción informal del modelo de Galton y
Watson
Supongamos que tenemos un individuo que tiene una cantidad aleatoria de hijos
con una cierta distribución que llamaremos p. A su vez cada hijo tiene, independi-
entemente de los demás miembros de la población, una cantidad aleatoria de hijos
1
2 CAPÍTULO 1. EL PROCESO DE GALTON Y WATSON
con la misma distribución p. Nos interesa saber cuántos individuos pertenecen a la
generación n y cuál es la probabilidad de que la población se extinga. Nos enfocaremos
en el tamaño de la población en cada generación y no en los tiempos en los que los
individuos nacen y mueren, y por eso se considera por igual a todos los de la misme
generación.
Para exponer los resultados modernos sobre el proceso de Galton y Watson uti-
lizaremos la teoŕıa de martingalas siguiendo de cerca el texto [Dur96].
1.2. Modelo matemático
Construiremos una sucesión de variables aleatorias {Zn}n∈N donde Zn se interpreta
como la cantidad de individuos en la generación n. Aśı, Z0 será igual a 1 para comenzar
a la población con un individuo. Para la construcción de las variables Zn utilizaremos
otra colección de variables aleatorias {ξni }i,n∈Z+ , donde ξni corresponderá a la cantidad
de hijos del i-ésimo individuo en la generación n, si es que éste existe. De acuerdo a la
descripción informal las variables aleatorias {ξni }i,n∈Z+ serán no negativas, con valores
en Z+, independientes e idénticamente distribuidas, y su distribución común será p.
Definamos
Zn+1 =
{
ξn+11 + · · ·+ ξn+1Zn si Zn > 0
0 si Zn = 0
La expresión anterior nos dice que si el tamaño de la generación al tiempo n es cero,
los tamaños de las generaciones siguientes también son cero, es decir, se da la extinción
del proceso. En cambio si el tamaño de la generación n es distinta de cero, su i-ésimo
individuo aporta ξn+1i hijos a la siguiente generación. Alternativamente, Zn+1 se le
puede expresar de la siguiente manera:
Zn+1 =
∑
k∈N
1Zn=k
k∑
i=1
ξn+1i . (1.1)
A la dsitribución p la llamaremos distribución de la descendencia y definimos
pk = P(ξni = k).
1.3. EL PROCESO DE GALTON Y WATSON COMO MARTINGALA 3
Esta expresión alternativa la utilizaremos más adelante para demostrar que Zn/m
n es
una martingala. Notemos además que Zn toma valores en N = {0, 1, . . . }.
Como nos interesa la probabilidad de extinción, queremos entonces conocer, si es
que existe, el ĺımite de este proceso. Para ayudarnos en esta tarea, se demostrará que
el proceso de Galton y Watson es una martingala no negativa.
1.3. El proceso de Galton y Watson como martin-
gala
Si definimos a la filtración Fn = σ(ξki : i ≥ 1, 1 ≤ k ≤ n) y suponemos que la
media de la distribución de descendencia es finita, tenemos el siguiente lema:
Lema 1.1. Sea m = E(ξki ). Entonces
(
Zn
mn
, n ≥ 0
)
es una Fn-martingala.
Demostración. Como Zn es Fn-medible y mn > 0 es constante,
Zn
mn
es Fn-medible.
Falta calcular E
(
Zn+1
mn+1
|Fn
)
:
E
(
Zn+1
mn+1
|Fn
)
= E
(∑
k∈N 1Zn=k
∑k
i=1 ξ
n+1
i
mn+1
|Fn
)
de acuerdo a la representación alternativa (1.1).
Dado que Zn es medible y la variable ξ
n+1
i es independiente de Fn
E
(∑
k∈N 1Zn=k
∑k
i=1 ξ
n+1
i
mn+1
|Fn
)
=
∑
k∈N
1Zn=k
k∑
i=1
E(ξn+1i )
mn+1
Simplificando la expresión anterior, resulta que:
E
(
Zn+1
mn+1
|Fn
)
=
∑
k∈N 1Zn=k k
mn
=
Zn
mn
Por lo tanto, Zn/m
n es una Fn-martingala.
4 CAPÍTULO 1. EL PROCESO DE GALTON Y WATSON
1.4. Extinción y supervivencia del proceso Galton
y Watson
Para toda i ∈ N, ξn+1i ≥ 0, y m > 0, tenemos que Znmn ≥ 0. Además para toda
n ∈ N, E( Zn
mn
) = E(Z0) = 1 < ∞ entonces E(Zn) < ∞ y supn∈N E(Zn) < ∞.
Por el teorema de convergencia para submartingalas (ver apéndice), Zn/m
n es una
submartingala que converge a Z∞, donde la convergencia es casi segura.
Para este tipo de procesos no sólo podemos afirmar que ese converge casi seguramente,
podemos incluso conocer el ĺımite. Los siguientes tres teoremas nos ayudan a conocer
el ĺımite del mismo.
Teorema 1.2. Si m < 1 entonces Zn = 0 para n suficientemente grande. En particular
se tiene que Zn
mn
→ 0 casi seguramente.
Demostración. Sabemos que Zn/m
n es una martingala. Ocurre que E( Zn
mn
) = E(Z0) =
1. En consecuencia E(Zn) = mn. Además m < 1 y
∑
n∈N P(Zn 6= 0) ≤
∑
n∈Nm
n por
desigualdad de Chebyshev (ver apéndice). Utilizando el lema de Borel-Cantelli (ver
apéndice), tenemos que P(ĺım inf{Zn = 0}) = 1. La igualdad anterior nos dice que
casi seguramente existe N ∈ N tal que para toda n > N , Zn = 0.
Teorema 1.3. Si m = 1 y P(ξmi = 1) < 1 entonces Zn = 0 casi seguramente para n
suficientemente grande.
Demostración. Lo primero que se mostrará es que P(Z2 = k|Z1 = k) < 1. Supongamos
que P(Z2 = k|Z1 = k) = 1.
Por definición de Z2 y la independencia de ξ
2
i con la σ-álgebra generada por Z1 tenemos
que
P(Z2 = k|Z1 = k) = P(
k∑
i=1
ξ2i = k|Z1 = k) = 1
Ahora utilizando la independencia de las ξ2i se sigue que para toda λ ∈ R,
(E(eλ(ξ2i−1)))k = 1.
1.4. EXTINCIÓN Y SUPERVIVENCIA DEL PROCESO GALTON Y WATSON 5
Finalmente, como ξ2i son positivas y la esperanza de la exponencial de una variable
positiva es menor o igual a 1, entonces E(eλ(ξ2i−1)) = 1 Por lo tanto,
P(ξ2i = 1) = 1.
Contradiciendo la hipótesis. Se concluye que P(Z2 = k|Z1 = k) < 1.
Ahora demostraremos que P(Zn = k, ∀n ≥ N) = 0 para toda k > 0. Si probamos lo
anterior y usamos el hecho que Zn/m
n converge a Z∞ en los enteros, podemos concluir
que Zn = 0 para n suficientemente grande.
Sea k > 0. Por continuidad de la medida de probabilidad,la propiedad de Markov y
la definición de probabilidad condicional se deduce que
P(Zn = k, ∀n ≥ N) = ĺım
m→∞
(
m−1∏
i=0
P(ZN+m−i = k|ZN+m−i−1 = k))P(ZN = k).
Como Zn es una cadena de Markov homogénea, podemos recorrer el tiempo y nos
queda que
P(Zn = k, ∀n ≥ N) = ĺım
m→∞
P(Z2 = k|Z1 = k)m P(ZN = k)
Como demostramos que P(Z2 = k|Z1 = k) < 1 el ĺımite anterior es igual a cero. Por
lo tanto, P(Zn = k, ∀n ≥ N) = 0 para k > 0.
Teorema 1.4. Si m > 1 entonces P(Zn > 0,∀n ∈ N) > 0.
Demostración. Para demostrar el teorema utilizaremos funciones generadoras. Sea
s ∈ [0, 1], definamos φ(s) = ∑k≥0 pksk. Entonces φ es la función generadora de la
distribución de la descendencia. Lo que nos interesa es calcular su derivada.
Debido a que la suma sobre k ≥ 0 es una integral de Lebesgue respecto a la
medida de conteo en los naturales y cumple que la derivada existe y está acotada por
una función integrable, podemos intercambiar la derivada con la suma en los siguientes
cálculos (ver apéndice). Aśı, tenemos que para s ∈ [0, 1):
φ′(s) =
∑
k≥1
d
ds
pks
k =
∑
k≥1
k pks
k−1 ≥ 0
6 CAPÍTULO 1. EL PROCESO DE GALTON Y WATSON
entonces φ es creciente y siendo:
φ′′(s) =
∑
k≥0
k(k − 1)pksk−2 ≥ 0
además es convexa.
Ahora, para k ≥ 1 tenemos que kpksk−1 > 0 y creciente, entonces utilizando el teorema
de convergencia monótona se deduce que:
ĺım
s↑1
φ′(s) = ĺım
s↑1
∑
k≥0
k pks
k−1 = E(ξni )
Para concluir el teorema, haremos uso del siguiente lema. El lema se demuestra al
final de esta prueba.
Lema 1.5. Sea φ la función generadora de la distribución de la descendencia. En-
tonces
1. Si definimos a θr como θr = P(Zr = 0) entonces θr =
∑
k≥0 pk(θr−1)
k.
2. Si φ′(1) = m > 1 entonces existe 0 < ρ < 1 tal que φ(ρ) = ρ, es decir, existe un
único punto fijo de φ distinto de cero en (0, 1).
3. Bajo la hipótesis del inciso anterior, θr−−−→r→∞ ρ.
Queremos demostrar que la probabilidad de que Zn > 0 para toda n ∈ N es
positiva. Sabemos que si el tamaño de la generación al tiempo n es cero entonces
para las generaciones posteriores el tamaño de la generación tamb́ıen es cero, en otras
palabras, {Zn = 0} ⊂ {Zn+1 = 0}. Se deduce que:
P(Zn > 0, ∀n ∈ N) = 1− ĺım
n→∞
P(Zn = 0)
Por la parte (2) y (3) del lema anterior, tenemos que:
1− ĺım
n→∞
P(Zn = 0) = 1− ρ > 0.
Por lo tanto, la probabilidad de la no extinción es positiva.
1.4. EXTINCIÓN Y SUPERVIVENCIA DEL PROCESO GALTON Y WATSON 7
Demostración lema 1.5. Probaremos los tres incisos de lema por separado
1. Para que Zr sea igual a cero necesitamos que los individuos en la primera gen-
eración no tengan descendientes después de la generación r, es decir,que sus
descendencias se extingan en las r − 1 unidades de tiempo. Como cada indi-
viduo tiene descendencia independientemente de los demás, la probabilidad de
extinción al momento r se puede ver como la suma de las probabilidades de que
cada individuo en la generación 1 no tenga descendencia al momento r, es decir,
P(Zr = 0) =
∑
k≥0
pk(θr−1)k.
2. Como φ′(1) = m > 1 , φ(0) ≥ 0 y φ(1) = 1 tenemos que φ es convexa e intersecta
a la recta identidad en un punto entonces existe un punto fijo. Llamémosle ρ.
En la figura 1.1 se ilustra con un ejemplo que existe un punto fijo entre 0 y 1
para las funciones convexas que cumplen con la hipótesis de lema. Formalicemos;
como la derivada de la función es mayor a 1 y en 1 toma el valor 1 tiene que
cruzar a la recta identidad. Como la función es convexa no puede volverla a
cruzar en consecuencia el punto fijo es único. Falta demostrar que es único.
Como m > 1 tenemos que pk > 0 para alguna k > 1. Entonces φ
′′(θ) > 0 para
1 > θ > 0. Como φ es estrictamente convexa, ocurre que si ρ < 1 entonces
φ(x) < x para toda x ∈ (ρ, 1). Se puede concluir que φ(x) > x para toda
x ∈ [0, ρ) y por lo tanto ρ es único.
3. Tenemos que θ0 = 0, φ(ρ) = ρ y φ es creciente. Como θr ≤ θr+1 podemos calcular
el ĺımite:
θ∞ = ĺım
r→∞
θr
Por el inciso 1 de este lema y por teorema de convergencia monótona tenemos
que
ĺım
r→∞
θr =
∑
k≥0
pkθ
k−1
∞ = φ(θ∞).
8 CAPÍTULO 1. EL PROCESO DE GALTON Y WATSON
Por lo tanto, θ∞ = φ(θ∞). Sabemos que θ∞ > 0 y en la parte 2 de este lema
demostramos que es único, se concluye que θ∞ = ρ.
Concluimos aśı la prueba de este lema.
Figura 1.1: Ejemplo del punto fijo distinto de 1 de una función convexa
Estos tres teoremas nos han dado una clasificación de los procesos de Galton y
Watson en subcŕıticos (m < 1), cŕıticos (m = 1) y supercŕıticos (m > 1). En el
caṕıtulo 4 ahondaremos en las tasas de decaimiento o crecimiento, utilizando a las
leyes del árbol de Galton y Watson y del árbol sesgado por tamaño que estudiaremos
en los caṕıtulos 2 y 3.
Caṕıtulo 2
El árbol de Galton y Watson
(sub)cŕıtico
En el primer caṕıtulo vimos el modelo de Galton y Watson como el número de
individuos en cada generación. Solo nos interesaba la evolución global de cada ge-
neración pero no la de cada individuo. Si representamos gráficamente a las genera-
ciones como un árbol, este último nos da toda la información genealógica. En este
caṕıtulo se desarrolla la parte combinatoria de los árboles discretos y finitos; nos con-
centraremos en establecer las nociones básicas y propiedades de los árboles planos con
ráız y sus codificaciones. Con estas propiedades en mente, se definirá el árbol de
Galton y Watson y se verá una aplicación a las caminatas aleatorias. El material de
este caṕıtulo es tomado del art́ıculo [LG06].
2.1. Árboles planos finitos.
2.1.1. Propiedades Básicas
En esta sección nos interesan los árboles finitos con ráız, en combinatoria, se les
llaman árboles planos. Primero, introducimos el conjunto de etiquetas
U =
∞⋃
i=1
Nn
9
10 CAPÍTULO 2. EL ÁRBOL DE GALTON Y WATSON (SUB)CRÍTICO
donde N = {0, 1, 2, 3, . . . } y por convención N0 = {∅}. Cada elemento u de U es una
sucesión u = (u1, . . . , un) de elementos de N.
La función longitud de u se define por |·| : U → N tal que |u| = |(u1, . . . , un)| = n.
Sean u = (u1, . . . , un), v = (v1, . . . , vm) ∈ U . La concatenación de u y v se define
como uv = (u1, . . . , un, v1, . . . , vm). En particular, u∅ = ∅u = u.
La función κ : U \ {∅} → U se define por κ(u1, . . . , un) = (u1, . . . , un−1).
Nota: Diremos que |u| es la generación de u y κ(u) el padre de u de forma que u
es un hijo de κ(u).
Ahora entramos en materia.
Definición 2.1. Un árbol ordenado (finito) y con ráız es un subconjunto finito t de
U tal que:
(i) ∅ ∈ t.
(ii) Para todo u ∈ t�{∅} → κ(u) ∈ t.
(iii) Para cada u ∈ t existe un entero no negativo ku(t) tal que para toda j ∈ N,
uj ∈ t si y sólo si 1 ≤ j ≤ ku(t).
El número ku(t) se interpreta como el número de hijos que tiene u en el árbol t.
Denotaremos a A como el conjunto de los árboles ordenados (finitos, en este caṕıtu-
lo) y con ráız. A los árboles les asociamos un orden lexicográfico y genealógico que
definiremos a continuación. Se define un orden lexicográfico sobre el conjunto de las
etiquetas U , de la siguiente manera.
Definición 2.2. Sean u = (u1, . . . , un), v = (v1, . . . , vm) ∈ U , diremos que u ≤ v si
cumple alguna de las dos condiciones:
1. Existe 1 ≤ j ≤ mı́n(n,m) tal que uj < vj y ui = vi para todo 1 ≤ i < j.
ó
2. n ≤ m y para toda 1 ≤ j ≤ mı́n(n,m), uj = vj.
2.1. ÁRBOLES PLANOS FINITOS. 11
En la figura (2.1) tenemos un ejemplo de un árbol. El orden lexicográfico de
izquierda a derecha del árbol es: {∅ < 1 < (1, 1) < (1, 1, 1) < (1, 1, 2) < (1, 2) <
(1, 2, 1) < (1, 2, 1, 1) < (1, 2, 1, 2) < (1, 3) < 2}.
Figura 2.1: Ejemplo de un árbol ordenado lexicográficamente
Utilizamos además un orden parcial en U , lo llamaremos orden genealógico sobre
el conjunto de las etiquetas.
Definición 2.3. Sean u, v ∈ U se dice que v es descendiente de u, se denota por
u ≺ v, si existe w ∈ U tal que v es la concatenación de u con w, es decir, v = uw.
Vemos que cada vértice del árbol t es un individuo de unapoblación donde t es
el árbol genealógico. La cardinalidad de t es la descendencia total del árbol.
Proposición 2.4. (U ,≤) es un orden total.
Demostración. Sean u = (u1, . . . , un), v = (v1, . . . , vm), w = (w1, . . . , wp).
Reflexividad: Como |u| ≤ |u| y u− i = ui para toda i ∈ {1, . . . , n} entonces u ≤ u.
Simetŕıa: Supongamos que u ≤ v v ≤ u tenemos que |u| ≤ |v| y |v| ≤ |u| entonces
|u| = |v| y por la condición 2 de la definición de orden lexicográfico, ui = vi si
1 ≤ i ≤ mı́n(n,m). Por lo tanto, u = v.
12 CAPÍTULO 2. EL ÁRBOL DE GALTON Y WATSON (SUB)CRÍTICO
Transitividad: Supongamos que u ≤ v y v ≤ w. Tenemos 4 casos:
1. Si uj = vj para 1 ≤ j ≤ n y vj = wj para 1 ≤ j ≤ m entonces uj = wj
para 1 ≤ j ≤ n y n ≤ m ≤ p. Por lo tanto, u ≤ w.
2. Existen i, j ∈ N tal que ui < vi y vj < wj. Como i ≤ j, sea k = i entonces
uk < wk. Por lo tanto, u ≤ w.
3. Existe i ∈ N tal que ui < vi pero vj = wj para 1 ≤ j ≤ m y n ≤ m ≤ p
entonces ui < wi. Por lo tanto, u ≤ w.
4. Existe i ∈ N tal que vi < wi y uj = vj para 1 ≤ j ≤ n entonces u ≤ w.
Carácter total: Falta demostrar que todo par de elementos de U puede compararse
con ≤. Si u, v ∈ U , tenemos dos casos:
(i) Si |u| ≤ |v| basta comparar cada entrada de u con la correspondiente de v.
Si existe una j ∈ {1, . . . , m} tal que uj < vj entonces u ≤ v. Si no, ui = vi
para toda i ∈ {1, . . . , n} resulta que u ≤ v.
(ii) Análogamente, si |v| ≤ |u| y existe una j ∈ {1, . . . , m} tal que vj < uj
entonces v ≤ u. Si no, vi = ui para toda i ∈ {1, . . . , m} resulta que v ≤ u.
Por consiguiente ≤ es un orden total sobre U .
Proposición 2.5. (U ,≺) es un orden parcial.
Demostración. Sean u, , v, w ∈ U .
Reflexividad: Sea x = ∅ por definición de orden de descendencia ux = u∅ = u. Por
lo tanto, u ≺ u. Todo individuo es descendiente de śı mismo.
Simetŕıa: Supongamos que u ≺ v y v ≺ u entonces existen x, y ∈ U tal que v = ux
y u = vy tenemos que v = vyx entonces yx = ∅. Por lo tanto v = u. Si un
individuo es descendiente de otro y ese otro es descendiente de él entonces son
el mismo individuo.
2.1. ÁRBOLES PLANOS FINITOS. 13
Transitividad: Si u ≺ v y v ≺ w entonces existen x, y ∈ U tal que v = ux y w = vy.
Sea z = xy entonces w = zu. Tenemos que u ≺ w. Por lo tanto, la relación ≺ es
transitiva.
Por lo tanto, el orden de descendencia es un orden parcial.
Los dos órdenes en el conjunto de etiquetas están relacionados de la siguiente
manera: Si v ≺ u entonces v ≤ u.
Como los árboles son subconjuntos finitos de U , las restricciones de ≤, ≺ a cada árbol
representan un orden total y parcial respectivamente.
2.1.2. Codificación de árboles planos finitos
Ahora introduciremos una función que caracteriza a todo árbol plano finito. Dicha
función será relevante cuando estudiemos la relación entre árboles y caminatas aleato-
rias.
Definición 2.6. Sea t un árbol. La función de altura se define de la siguiente man-
era: sean u0 = ∅, u1, u2, . . . , u#(t)−1 los elementos de t ordenados lexicográficamente.
Se define
ht(n) : N→ N
como
ht(n) = |un| con 0 ≤ n < #(t).
En la figura 2.2 tenemos un ejemplo de cómo se codifica un árbol a través de la
función de altura. Si el árbol está ordenado lexicográficamente, entonces la función
de altura es la sucesión de las generaciones de los individuos de t (en la figura 2.2
utilizamos el mismo árbol ordenado lexicográficamente de la figura 2.1).
La altura de un árbol t es máx{ht(n); 0 ≤ n ≤ #(t)− 1}
En la definición de árbol, a cada vértice del árbol, se le asocia un entero no negativo
kut. Codificaremos a los árboles mediante la sucesión de hijos que tiene cada individuo.
14 CAPÍTULO 2. EL ÁRBOL DE GALTON Y WATSON (SUB)CRÍTICO
Figura 2.2: Ejemplo de un árbol y la gráfica de su función de altura.
Sea S el conjunto de todas las sucesiones finitas de enteros no negativos
m1,m2, . . . ,mp con p ≥ 1 que cumplen:
m1 + · · ·+ mi ≥ i para toda i ∈ {1, . . . , p− 1}
m1 + · · ·+ mp = p− 1.
Ahora, para todo árbol t y para todo vértice v en el árbol le asociamos un entero
no negativo kv(t) que denota el número de hijos que tiene v en el árbol kv. Veremos
que, para árboles distintos, las sucesiones de los números de hijos ordenada respecto
al orden lexicográfico de sus sub́ındices, también son distintas. En otras palabras:
Proposición 2.7. La función
Φ : t 7→ (ku0(t), . . . , ku#(t)−1(t))
es una biyección de A en S.
Para poder demostrar esta proposición es preciso probar el siguiente lema.
Lema 2.8. Sea t = {∅, u1, . . . , up−1} un árbol ordenado lexicográficamente, donde
p = #(t).
2.1. ÁRBOLES PLANOS FINITOS. 15
(1) Sea uk ∈ t entonces existe k ≤ j ≤ p− 1 tal que uj es hijo de uk.
(2) Sean uj ∈ t y uj+1, . . . , us los hijos de uj entonces para k 6= j, uj+1, . . . , us no
son hijos de uk.
Demostración. Sea uj = (u
j
1, . . . , u
j
n) ∈ t. Como t es un árbol, el padre de uj, que hab́ıa
sido denotado por κ(uj), también es un vértice del árbol, digamos que κ(uj) = uk.
Como κ(uj) = (u
j
1, . . . , u
j
n−1) entonces |κ(uj)| < |uj| o equivalentemente κ(uj) = uk <
uj por lo que k < j y aśı, uj es el hijo de uk para algún k < j. Ahora supongamos que
para alguna j+1 ≤ l ≤ s, ul es hijo de uk y de us con k 6= s. Sea ul = (ul1, . . . , uln). Por
una parte, κ(ul) = us, entonces (u
l
1, . . . , u
l
n−1) = us y por otra, κ(ul) = uk entonces
uk = (u
l
1, . . . , u
l
n−1). Resulta que, uk = us.
Demostración de la Proposición 2.7. La demostración se dividirá en dos partes; la
primera será demostrar que la función Φ tiene como contradominio a S y la segunda
parte será probar que es una biyección.
Sea #(t) = p y sean u0, . . . , up−1 los vértices del árbol ordenados lexicográfica-
mente. La suma ku0 + · · · + kup−1 cuenta el número total de hijos de todos los indi-
viduos del árbol, por lo tanto la suma es igual a p− 1 pues no se incluye a ∅. Ahora,
si i ∈ {0, 1, . . . , p − 2}, ku0 + . . . , kui es el número de hijos de u0, . . . , ui. Como en el
orden lexicográfico ui es visitado antes que sus hijos, ellos mismos están contados en
la suma y la suma es mayor que i. Por lo tanto, Φ mapea a A en S.
Supondremos que para los árboles de tamaño menor que p, Φ es un mapeo biyec-
tivo. Sean t1 = {u0 < u2 < · · · < up−1} y t2 = {v0 < v2 < · · · < vp−1} dos árboles
planos, distintos, ordenados lexicográficamente de tamaño p. Tomemos a up−1 ∈ t1
y a vp−1 ∈ t2 el último vértice de cada árboles en el orden lexicográfico. Por ser los
últimos vértices kup−1 = kvp−1 = 0. Por el lema anterior (2.8) up−1 es hijo de algún uj
con j < p−1 y vp−1 es hijo de algún vi con i < p−1. Sea t1,1 = t1−{up−1}. Como solo
quitamos el último vértice, uj tiene un hijo menos y los demás vértices de t1,1 tienen
el mismo número de hijos que en el árbol t1. Análogamente, sea t2,2 = t2 − {vp−1}
tenemos que kvj(t2,2) = kvj(t2)−1 y para todo r 6= s se observa que kur(t2) = kus(t2,2).
16 CAPÍTULO 2. EL ÁRBOL DE GALTON Y WATSON (SUB)CRÍTICO
Ahora tenemos 2 casos:
Caso 1: Si t1,1 6= t2,2 por hipótesis de inducción Φ es una biyección para árboles de
tamaño menor que p, entonces Φ(t2,2) 6= Φ(t1,1), en otras palabras,
(ku1 , ku2 , . . . , kup−2) 6= (kv1 , kv2 , . . . , kvp−2) Por lo tanto, Φ(t1) 6= Φ(t2).
Φ es una biyección de A a S.
Caso 2:Si t1,1 = t2,2 como up−1 es hijo de uj, vp−1 es hijo de vi y t1 6= t2 entonces
j 6= i. Por lo tanto, Φ(t1) 6= Φ(t2).
Resulta que Φ es una biyección.
En vista de la relación entre árboles y caminatas aleatorias que se presentará,
construiremos, a partir de una sucesión (m1, . . . ,mp) ∈ S, otra sucesión (x0, . . . , xp)
dada por:
xn =
n∑
i=1
(mi − 1) con mi ∈ S y 0 ≤ n ≤ p. (2.1)
La sucesión (x0, . . . , xp) satisface:
x0 = 0 y xp = −1.
xn ≥ 0 para todo 1 ≤ n ≤ p− 1.
xi − xi−1 ≥ −1 para todo 1 ≤ i ≤ p.
A las sucesiones que satisfacen las propiedades anteriores, se les llama caminos de
Lukasiewicz (CL). Hemos construido un camino de Lukasiewicz al tomarlas diferencias
de las entradas sucesivas de un elemento de S. Dicha asociación es claramente una
biyección. Si definimos a m1 = ku0(t),m2 = ku1(t) . . . , mp = ku#(t)−1(t) entonces
(x0, . . . , xp) es el camino de Lukasiewcz asociado a t. Como φ es una biyección entre el
conjunto de árboles A y de las sucesiones en S, los árboles también están en biyección
con los caminos de Lukasiewicz. Hemos probado la siguiente proposición
Proposición 2.9. La función
Ψ : A −→ CL
2.1. ÁRBOLES PLANOS FINITOS. 17
t 7→ (0, ku0(t)− 1, . . . ,
p−1∑
i=1
(kui(t)− 1),−1)
es una biyección.
La última parte de esta sección es ver qué relación hay entre la función de altura
y los caminos de Lukasiewcs que nos permitirá relacionar los árboles y las caminatas
aleatorias.
Para poder demostrar qué relación hay entre los dos, primero demostraremos var-
ios resultados: un árbol plano trasladado a alguno de sus vértices es otra vez un árbol
plano; individuos distintos tienen descendencia distinta; y árboles traslados respetan
el orden lexicográfico.
Lema 2.10. Sea t un árbol plano. Para cada u ∈ t se define a tu = {v ∈ U ; uv ∈ t},
entonces tu es un árbol plano.
Demostración. Supongamos t un árbol plano y u un vértice de t. Demostraremos las
tres propiedades de árbol plano.
1. Como ∅ ∈ t y u = u∅ ∈ tu, resulta que ∅ ∈ tu.
2. Supongamos w ∈ tu \{∅} y sea κ(w) el padre de v. Por definición de tu tenemos
que uw ∈ t y κ(uw) = uκ(w) ∈ t por ser t árbol plano. Por lo tanto κ(w) ∈ tu.
3. Cada vértice del árbol t tiene kv(t) hijos. Si traslado el árbol al vértice u ∈ t
tengo que los elementos del árbol trasladado tu tienen el mismo número de hijos
que el árbol t, es decir, kv(tu) = kuv(t).
Por lo tanto, tu es un árbol plano con ráız.
Lema 2.11. Sea t un árbol plano ordenado lexicográficamente, uj ∈ t y k = mı́n{s ∈
N; uj ⊀ us}, entonces uj+1, . . . , uk−1 son los únicos descendientes de uj.
Demostración. Por definición de k, uj+1, . . . , uk−1 son descendientes de uj. Necesita-
mos demostrar que para r > k, uj ⊀ ur.
18 CAPÍTULO 2. EL ÁRBOL DE GALTON Y WATSON (SUB)CRÍTICO
Supongamos que existe r > k uj ≺ ur. Como el árbol está ordenado lexicográfi-
camente y r > k entonces ur > uk > uj. Tenemos que |ur| ≥ |uk| ≥ |uj| yuj ≺ ur
ocurre que uir = u
i
j si 1 ≤ i ≤ |uj|. Ahora como uj ⊀ uk, existe 1 ≤ s ≤ |uj| tal que
usj 6= usk, de hecho usk > usj . Como k < r entonces usk > usj = usk lo que implica que
uk > ur, aśı llegamos a una contradicción. Por lo tanto, los únicos descendientes de
uj son uj+1, . . . , uk−1.
Lema 2.12. Sean uj, un ∈ t tal que uj ≺ un. Si tuj = {uj0 < uj1 < · · · < ujk−1}
entonces un = uju
j
n−j.
Demostración. Supongamos uj, un ∈ t tal que uj ≺ un, tenemos que un = ujv con
v ∈ U , de hecho v ∈ tu. Los descendientes de uj son, por el lema anterior, uj+1, . . . , us
donde uj ≺ us pero uj ⊀ us+1. Como el árbol t está ordenado lexicográficamente
puedo renombrar a los descendientes de uj como
ujv0 = uj∅, uj+1 = ujv1 = ujvj1, . . . , us = ujvs−j = uju
j
s−j
entonces para todo descendiente un de uj tenemos que un = uju
j
n−j.
Teorema 2.13. La función de altura ht de un árbol t está relacionada con los caminos
de Lukasiewicz por la siguiente igualdad:
ht(n) = #{j ∈ {0, 1, . . . , n− 1} : xj = ı́nf
j≤l≤n
xl}.
Demostración. Si t es un árbol ordenado lexicográficamente entonces ht(n) es la gen-
eración donde se encuentra el vértice vn. Supongamos que vn está en la generación
l, esto quiere decir que el vértice vn tiene l ancestros. Es claro que ht(n) = #{j ∈
{0, 1, . . . , n−1}; uj ≺ un}. Necesitamos demostrar que para j ∈ {0, 1, . . . , n−1}, uj ≺
un si y sólo si xj = ı́nfj≤l≤n xl. Si uj ≺ un por definición existe w ∈ U tal que
un = ujw tenemos que |un| = |uj| + |w|. Ahora definamos el árbol trasladado,
tuj = {v ∈ U ; ujv ∈ t} y r = mı́n{s, us ⊀ uj}, por el lema (2.11), tenemos que
uj+1, . . . , ur−1 son descendientes de uj. Si tuj = {uj0 < uj1 < · · · < ujk−1} por el lema
(2.12) resulta que un = uju
j
n−j para todo descendiente un de uj. Además, para todo
2.2. CONSTRUCCIÓN DEL ÁRBOL GW (SUB)CRÍTICO 19
elemento del árbol trasladado tuj se tiene que si i < l entonces uju
j
i < uju
j
l . En otras
palabras, el árbol trasladado tuj respeta el orden lexicográfico del árbol t. Por lo tanto,
podemos concluir que
ht(n) = ht(j) + htuj (n− j).
Como htuj (n − j) > 0 entonces tenemos que uj ≺ un si y sólo si xj = ı́nfj≤l≤n xl.
Terminamos aśı la demostración.
2.2. Construcción del árbol de Galton y Watson
(sub)cŕıtico
Esta sección explora las aplicaciones de los árboles planos al proceso de Galton
y Watson y a las caminatas aleatorias. Para poder aplicar los conceptos que se de-
sarrollaron en la sección anterior, primero definiremos lo que es un árbol aleatorio
asociado a una distribución de descendencia subcŕıtica. Los tamaños de las genera-
ciones sucesivas conforman un proceso de Galton y Watson; en la descripción informal
de este proceso, dada en el caṕıtulo 1, sólo nos interesaba conocer el tamaño de cada
generación. Ahora codificaremos la genealoǵıa de la población en un árbol aleatorio.
Los tamaños de sus generaciones sucesivas serán naturalmente un proceso de Galton
y Watson. Finalmente, veremos que el camino de Lukasiewicz asociado al árbol de
Galton y Watson es una caminata aleatoria.
2.2.1. Construcción del árbol aleatorio
Sea p una distribución de descendencia subcŕıtica, p es una medida de probabili-
dad sobre Z+ tal que
∞∑
k=0
kL(k) ≤ 1.
Sea (Ku, u ∈ U) una colección de variables aleatorias independientes e idénticamente
distribuidas, con distribución p definidas en un espacio de probabilidad (Ω,F ,P).
20 CAPÍTULO 2. EL ÁRBOL DE GALTON Y WATSON (SUB)CRÍTICO
Definimos θ un subconjunto aleatorio de U de la siguiente manera:
θ = {u = (u1, . . . , un) ∈ U : uj ≤ Ku1,...,uj−1 para cada 1 ≤ j ≤ n} ∪ {∅}.
Teorema 2.14. Si Zn = #{u ∈ θ : |u| = n} entonces
(Zn, n ≥ 0)
es una cadena de Markov homogénea.
Demostración. Demostraremos la propiedad de Markov i.e., si x0, x1, x2, . . . , xn−1, x, y ∈
Z, entonces
P(Zn+1 = y|Zn = x) = P(Zn+1 = y|Zn = x, Zn−1 = xn−1, . . . , Z0 = x0).
Esto se reduce a demostrar que si
P(Zn+1 = y|Zn = x) = f(x, y)
donde f es una función que sólo depende de x y y entonces tenemos la propiedad de
Markov.
Sea para cada entero positivo k el subconjunto Ik = {1, 2, 3, . . . , k} y I0 = {∅}.
Definimos uIk, la concatenación de u con cada elemento de Ik y para cada r ∈ N el
conjunto de vértices U = {v1, v2, . . . , vr} ⊂ U . Queremos escribir al conjunto {Zn = x}
como una unión de eventos independientes y medibles con respecto a σ(Ku; |u| < k).
Primero notemos que
{θ ∩ Nm = U} =
{ ∅ si U 6= ⋃u∈κ(U) uIku⋃
u∈κ(U){ku(θ) = Ku} si U =
⋃
u∈κ(U) uIku
Como ∅ y ⋃u∈κ(u){ku(θ) = Ku} son conjuntos medibles con respecto a σ(Ku; |u| < m)
ocurre que {θ ∩ Nm = U} ∈ σ(Ku; |u| < m). Por lo tanto,
{Zn = x} =
⋃
U⊂Nn,#(U)=x
{θ ∩ Nn = U}.
Por definición de U y por la σ-aditividad de P resulta que
2.2. CONSTRUCCIÓN DEL ÁRBOL GW (SUB)CRÍTICO 21
P(Zn+1 = y, Zn = x) =
∑
U⊂Nn,#(U)=x
P(Zn+1 = y, θ ∩ Nn = {v1, v2, . . . , vx}).
En la generación n tengo x individuos, para que en la generación n + 1 tenga y
individuos necesito que la suma de la cantidad de hijos que tiene cada individuo en la
generación n sea igual a y. Además cada individuo, independientemente de los demás,
tiene una cantidad aleatoria de hijos. En otras palabras,
P(Zn+1 = y, Zn = x) = P(Kv1 + · · ·+Kvx = y)
∑
U⊂Nn,#(U)=x
P(θ∩Nn = {v1, v2, . . . , vx})
entonces
P(Zn+1 = y, Zn = x) = P(Kv1 + · · ·+ Kvx = y)P(Zn = x).
Utilizando la definición de probabilidad condicional tenemos que P(Zn+1 = y|Zn =
x) = P(Kv1 + · · · + Kvx = y). Por lo tanto, demostramos que la probabilidad de que
Zn+1 = y dado que Zn = x es una función que sólo depende de x y de y. Concluimos
que Zn es una cadena de Markov homogénea.
De la demostración del teorema anteriorresulta un corolario muy importante.
Corolario 2.15. (Zn, n ≥ 0) es un proceso de Galton y Watson con distribución de
descendencia p y valor inicial Z0 = 1.
Demostración. Por el teorema anterior tenemos que Zn es una cadena de Markov con
probabilidad de transición, px,y = p(Kv1 +· · ·+Kvx = y) para toda x, y ∈ Z+, entonces
Zn es un proceso de Galton-Watson donde Z0 = #{u ∈ θ; |u| = 0} = #{∅} = 1.
Hasta ahora hemos visto que el conjunto aleatorio definido en el conjunto de
árboles A tiene asociado un proceso de Galton y Watson subcŕıtico. Probamos en el
primer caṕıtulo que el proceso se extingue casi seguramente para distribuciones con
media menor o igual a 1. El siguiente corolario utiliza este último hecho.
Corolario 2.16. θ es casi seguramente un árbol con ráız.
22 CAPÍTULO 2. EL ÁRBOL DE GALTON Y WATSON (SUB)CRÍTICO
Demostración. Como Zn es un proceso de Galton y Watson con distribución de de-
scendencia p con media m ≤ 1, entonces para n suficientemente grande Zn = 0 casi
seguramente. Sea N0 ∈ N tal que para toda n ≥ N0, Zn = 0. Como N0 es finito c.s
tenemos que θ es un subconjunto finito casi seguramente. Ahora falta demostrar que
θ cumple las 3 propiedades de un árbol plano con ráız:
(a) Por definición de θ, ∅ ∈ θ.
(b) Sea u = (u1, . . . , un) ∈ θ�{∅} entonces uj ≤ K(u1,...,uj−1) para todo j ∈
{1, . . . , n} como κ(u) = (u1, . . . , un−1) cumple que uj ≤ K(u1,...,uj−1) para to-
da j ∈ {1, . . . , n− 1}. Por lo tanto, κ(u) ∈ θ.
(c) Sea u = (u1, . . . , un) ∈ θ por definición de θ se tiene que uj ≤ K(u1,...,uj−1) para
toda j ∈ {1, . . . , n}. Sea ku(θ) = Ku entonces uj ∈ θ si y sólo si 1 ≤ j ≤ ku(θ).
Por lo tanto, θ es un árbol plano con ráız casi seguramente.
El árbol θ, o cualquier árbol aleatorio con la misma distribución, se llamará el
árbol GW con distribución de descendencia p, o en corto se le llamará un p-árbol de
Galton y Watson.
2.2.2. Distribución del árbol de Galton y Watson
A la distribución de θ en el conjunto A de árboles, se le denotará por Πp. En esta
sección veremos dos propiedades de la distribución del árbol Galton y Watson.
Proposición 2.17. Para todo t ∈ A
Πp(t) =
∏
u∈t
p(ku(t)).
Demostración. Lo primero que vamos a demostrar es:
{ω′ ∈ Ω; θ(ω′) = t} =
⋂
u∈t
{ω′ ∈ Ω; Ku = ku(t)} (2.2)
2.2. CONSTRUCCIÓN DEL ÁRBOL GW (SUB)CRÍTICO 23
Sea ω ∈ {ω′ ∈ Ω; θ(ω) = t} como t es árbol para cada u ∈ t existe ku(t) ≥ 0 además
θ(ω) = t entonces Ku = ku(t). Por lo tanto, ω ∈
⋂
u∈t{ω′ ∈ Ω; Ku = ku(t)} y tenemos
que
{ω′ ∈ Ω; θ(ω′) = t} ⊂
⋂
u∈t
{ω′ ∈ Ω; Ku = ku(t)}.
Ahora sea ω ∈ ⋂u∈t{ω′ ∈ Ω; Ku = ku(t)}. Tenemos que demostrar que θ(ω) = t, lo
haremos de la siguiente manera:
1. Si u ∈ t entonces u ∈ θ(ω).
2. Si u /∈ t entonces u /∈ θ(ω).
∅ ∈ t y ∅ ∈ θ(ω) nos fijamos en los elementos de t distintos de la ráız. Sea u =
(u1, . . . , un) ∈ t \ {∅} Por definición del árbol y como ω ∈
⋂
u∈t{ω′ ∈ Ω; Ku = ku(t)}
tenemos que uj+1 ≤ k(u1,...,uj) = K(u1,...,uj)(ω). Entonces u ∈ θ(ω).
Supongamos ahora que u = (u1, . . . , un) /∈ t. Nos fijamos en el último ancestro
de u que está en t. Sea ese ancestro (u1, . . . , uk) con k < n tenemos que K(u1,...,uk) =
k(u1,...,uk). Como es el último ancestro en en árbol, se tiene que uk+1 > k(u1,...,uk)
entonces (u1, . . . , uk+1) 6= θ(ω). Por lo tanto, u /∈ θ(ω). Ahora utilizando la igualdad
(2.2) y la independencia de la sucesión {Ku; u ∈ U} tenemos que :
Πp(t) = P(
⋂
u∈t
{Ku = ku(t)})
=
∏
u∈t
P(Ku = ku(t))
=
∏
u∈t
p(ku(t)).
Dos ejemplos sencillos de la utilidad de esta fórmula:
Si la distribución de descendencia es binaria, i.e.,
p(k) =
1
2
si k = 0, 2,
24 CAPÍTULO 2. EL ÁRBOL DE GALTON Y WATSON (SUB)CRÍTICO
tenemos que la distribucion del árbol es:
Πp(t) =
∏
u∈t
P(Ku = ku(t)) = (
1
2
)#(t).
Si la distribución de descendia es Poisson i.e.,
p(k) = e−λ
λk
k!
,
la distribución del árbol de Galton y Watson es:
Πp(t) =
∏
u∈t
P(Ku = ku(t)) =
∏
u∈t
e−λ
λku(t)
ku(t)!
= e−λ
∏
u∈t
λku(t)
ku(t)!
.
En el caṕıtulo 1 describimos al modelo de Galton y Watson como el número de
individuos en cada generación. Los individuos de cada generación se reproducen de
manera independiente, con la misma ley. Probaremos que esta misma idea se traslada
al modelo del árbol de Galton y Watson. Sea t un árbol y 1 ≤ j ≤ k∅(t) los hijos de
la ráız de t y definimos a Tjt = {u ∈ U ; ju ∈ t} como el árbol t trasladado a j. En el
lema (2.10), demostramos que Tjt es un árbol plano con ráız.
Proposición 2.18. La distribución Πp cumple las siguientes dos propiedades:
(i) Πp(k∅ = j) = p(j) j ∈ Z+.
(ii) Para cada j ≥ 1 con p(j) > 0, los árboles trasladados T1, T2, . . . , Tj son inde-
pendientes bajo la probabilidad condicional Πp(dt|k∅ = j) y su distribución
condicional es Πp
.
Demostración. Sea t un árbol plano con ráız. En la demostración de la proposición
anterior probamos que {ω′ ∈ Ω; θ(ω′) = t} = ⋂u∈t{ω′ ∈ Ω; Ku = ku(t)}. Ahora
supongamos que la ráız de t tiene k∅ = j hijos entonces Πp(k∅ = j) = P(K∅ = j) =
p(j). Como p(j) > 0 sean T1, . . . , Tj los árboles trasladados en j. Probaremos que
2.2. CONSTRUCCIÓN DEL ÁRBOL GW (SUB)CRÍTICO 25
Πp(T1 = t1, . . . , Tj = tj|k∅ = j) =
∏j
i=1 Πp(Ti = ti|k∅ = j).
Sean t1, t2, . . . , tj los árboles trasladados a los hijos de la ráız. Tenemos que en el árbol
t
{θ = t} = {K∅ = k∅(t)}
k∅(t)⋂
i=1
{Ti = Tit}.
Por definición de probabilidad condicional y utilizando la igualdad de conjuntos que
acabamos de mencionar, nos queda que
Πp(T1 = t1, . . . , Tj = tj|k∅ = j) =
j∏
i=1
P(Ti = Ti(t)|k∅ = j).
Utilizando la proposición anterior demostramos que T1, . . . , Tj son independientes bajo
la ley condicional Πp(dt|k∅ = j) y su distribución condicional es Πp.
2.2.3. Codificación del árbol aleatorio y caminatas aleatorias
En esta última sección veremos la relación entre los árboles de Galton y Watson
y las caminatas aleatorias.
Recordemos la definición del mapeo Φ.
Proposición 2.19. Sea θ un p árbol de Galton-Watson y M1,M2, . . . variables aleato-
rias independientes con distribución p entonces
Φ(θ) =(d) (M1,M2, . . . ,MT )
donde
T = ı́nf{n ≥ 1; M1 + · · ·+ Mn < n}.
Demostración. Sean U0 = ∅, U1, . . . , U#(θ)−1 los elementos de θ ordenados lexicográfi-
camente tal que Φ(θ) = (KU0 , KU1 , . . . , KU#(θ)−1). Sabemos que KU0+KU1+· · ·+KUn ≥
n + 1 para toda n ∈ {0, 1, . . . , #(θ) − 2}, y KU0 + KU1 + · · · + KU#(θ)−1 = #(θ) − 1.
El problema que tenemos es que los ı́ndices Uj son variables aleatorias, entonces no
podemos usar el hecho que la colección de Ku con u ∈ U son variables aleatorias in-
dependientes con distribución p. Para resolver el problema, definimos para p ≥ #(θ)
26 CAPÍTULO 2. EL ÁRBOL DE GALTON Y WATSON (SUB)CRÍTICO
a Up como Up = U#(θ)−11 . . . 1 donde en el lado derecho de la igualdad agregamos
p−#(θ) + 1 unos. Con esta definicioón la demostración se reduce a probar que para
toda p ≥ 0, KU0 , . . . , KUp son independientes con distribución p. La demostración se
hará por inducción. Para p = 0, 1 el resultado es cierto ya que U0 = ∅ y U1 = 1 son
deterministas. Sea p ≥ 2 y supongamos que la independencia se cumple para p − 1.
Definimos los conjuntos:
θ ∩ {v ∈ U ; v ≤ u}
{Up = u} = ({Up = u} ∩ {#(θ > p)}) ∪ ({Up = u} ∩ {#(θ ≤ p)}).
Afirmación : El primer conjunto es medible con respecto a σ(Kv : v < u).
El conjunto θ ∩ {v ∈ U ; v ≤ u} es medible con respecto a σ(Kv : v < u) ya que estoy
tomando todos lo elementos v ∈ U que cumplen que v ≤ u y que vi ≤ K(v1,...,vi−1).
Como consecuencia de la afirmación anterior, el segundo conjunto es medible con
respecto a la misma σ-álgebra. Sean g0, g1, . . . , gp funciones no negativas sobre {0, 1, . . . }
(¡se utilizan en general, funciones no negativas para simplificar la notación!)
E(g0(KU0)g1(KU1) . . . gp(KUp))
=
∑
u0<u1<···<up E(1{U0=u0,...,Up=up}go(KU0)g1(KU1) . . . gp(KUp))
=
∑
u0<u1<···<up E(1{U0=u0,...,Up=up}go(Ku0)g1(Ku1) . . . gp−1(Kup−1))E(gp(Kup).
la última igualdad se debe aque Kup es independiente de σ(Kv; v < up) y además
que el conjunto {Up = up} es medible con respecto a la misma σ-álgebra. Sea p(gp) :=
E(gp(Kup)) entonces no depende de up. Finalmente nos queda que
E(g0(KU0)g1(KU1) . . . gp(KUp)) = E(g0(KU0)g1(KU1) . . . gp−1(KUp−1))p(gp).
Aplicando la hipótesis de inducción nos queda que las variables aleatorias KUp son
independientes y su distribución común es p.
Sean M1 = K0, . . . ,Mn = Kn−1, . . . , sabemos que KU0 , KU1 , . . . , KUn ≥ n+1 para
toda n ∈ {0, 1, . . . , #(θ) − 2}, y KU0 , KU1 , . . . , KU#(θ)−1 = #(θ) − 1 entonces T =
ı́nf{n ≥ 1; M1 + · · ·+ Mn < n} = #(θ). Por lo tanto, Φ(θ) d= (M1,M2, . . . , MT ).
Corolario 2.20. Sea (Sn, n ≥ 0) una caminata aleatoria sobre Z con valor inicial S0
2.2. CONSTRUCCIÓN DEL ÁRBOL GW (SUB)CRÍTICO 27
y distribución de salto ν(k) = p(k + 1) para cada k ≥ −1. Sea
T = ı́nf{n ≥ 1; Sn = −1}
entonces
Ψ(θ)
d
= (S0, S1, . . . , ST ).
En particular, #(θ) y T tienen la misma distribución.
Demostración. Por definición de T tenemos que T = ı́nf{n ≥ 1; Sn = −1} = #(θ) ya
que #(θ) = ı́nf{n ≥ 1; M1 + · · ·+Mn < n} Por lo tanto, Ψ(θ)stackreld=(S0, . . . , ST ).
En el próximo caṕıtulo generalizaremos la definición de árbol de Galton y Watson
a la definición de árbol infinito de Galton y Watson y construiremos el árbol sesgado
por tamaño. El último nos servirá, en el caṕıtulo 4 para demostrar tres teoremas
clásicos de los procesos de Galton y Watson.
Caṕıtulo 3
El árbol de Galton y Watson
general y cómo sesgarlo por
tamaño.
En este caṕıtulo extenderemos la teoŕıa de árboles finitos a árboles de altura infini-
ta. Construiremos los árboles sesgados por tamaño de Galton y Watson y mostraremos
la existencia de la ley del árbol sesgado en el conjunto de árboles planos infinitos En
el art́ıculo [LPP95] se da una costrucción heuŕıstica de la medida ĜW . El objetivo
de este caṕıtulo es desarrollar de manera formal la construcción y la existencia de
la medida del árbol sesgado a través del teorema de existencia de Parthasarathy. El
teorema de Parthasarathy es un resultado para la existencia de una medida sobre el
ĺımite inverso de espacios de Borel.
Durante el estudio de la extensión de ĜW se pensó que el teorema de Parthasarathy
era más general que el teorema de consistencia de medidas de Kolmogorov. Pero en
realidad, como se verá al final del caṕıtulo, el primero es un caso particular del segun-
do.
Nota: Para la comprensión de las aplicaciones del árbol sesgado por tamaño a los
procesos de Galton y Watson es suficiente con leer las primeras dos secciones de este
caṕıtulo. Las demás secciones son un tanto más teóricas; sirven para tener un desar-
rollo formal de la teoŕıa pero no aportan intuición adicional para las aplicaciones.
28
3.1. EL ÁRBOL DE GALTON Y WATSON 29
3.1. El árbol de Galton y Watson
Ahora utilizaremos los árboles planos enraizados infinitos etiquetados de izquierda
a derecha. La definición formal es:
Definición 3.1. Un árbol plano y con ráız es un subconjunto finito, t, de U tal que:
(i) ∅ ∈ t.
(ii) Para todo u ∈ t�{∅} entonces κ(u) ∈ t.
(iii) Para cada u ∈ t existe un entero no negativo ku(t) tal que para toda j ∈ N,
uj ∈ t si y sólo si 1 ≤ j ≤ ku(t).
Se pide al lector recordar la definición de concatenación, función de longitud de
un vértice, altura de un árbol y definición de padre.
Denotaremos a A como el conjunto de árboles infinitos planos enraizados y An
como el conjunto de árboles planos con ráız de altura menor o igual a n.
Definición 3.2. Sean πn : An+1 → An tal que para todo t ∈ An+1
πn(t) = {u ∈ t; |u| ≤ n}
y la sucesión de funciones πn : A → An tal que para todo t ∈ A
πn(t) = {u ∈ t : |u| ≤ n}.
Las funciones πn “podan” a los árboles planos a la altura n y las funciones πn
“podan” a los árboles de altura menor o igual a n+1 en su n-ésima generación. En el
caṕıtulo 2 se utilizó para definir un árbol aleatorio a una colección de variables aleato-
rias independientes con distribución subcŕıtica. Con ésto se demostró que el árbol
aleatorio era un árbol plano enraizado casi seguramente finito. Ahora utilizamos una
definición similar, pero ahora las variables aleatorias tienen distribución p cualquiera.
30 CAPÍTULO 3. EL ÁRBOL GW GENERAL Y CÓMO SESGARLO.
A θ, que definimos a continuación, se verá que es una variable aleatoria con respecto
a la σ-álgebra F = σ(∪πn):
θ = {u = (u1, . . . , un) ∈ U : uj ≤ Ku1,...,uj−1 para cada 1 ≤ j ≤ n} ∪ {∅}
donde (Ku, u ∈ U) es una colección de variables aleatorias independientes e idéntica-
mente distribuidas, con distribución p, no necesariamente subcŕıtica, definidas en un
espacio de probabilidad (Ω, F ,P).
Lema 3.3. Para toda n ∈ N, sean Fn = σ(πk; k ≤ n) = σ(πn) σ-álgebras en el espacio
de árboles A. Entonces θ es una variable aleatoria con respecto a F = σ(Fn; n ∈ N).
Demostración. Es suficiente con verificar que πn(θ) es un árbol plano y con ráız de
altura menor o igual a n. Por definición de πn,
πn(θ) = {u ∈ θ; |u| ≤ n}
= {u = (u1, . . . , uk); uj ≤ Ku1,...,uj−1 para cada 1 ≤ j ≤ k y k ≤ n}.
De lo anterior, podemos concluir que πn(θ) es un conjunto finito. Ahora demostraremos
que πn(θ) cumple las tres propiedades de árbol plano con ráız:
(i) Como |∅| = 0 ≤ n y n ≥ 1 entonces ∅ ∈ πn(θ).
(ii) Sea u = (u1, . . . , uk) ∈ πn(θ)/{∅} por definición de θ sabemos que uj ≤
K(u1,...,uj−1) para toda j ∈ {1, . . . , k} como π(u) = (u1, . . . , un−1) cumple que
uj ≤ K(u1,...,uj−1) para toda j ∈ {1, . . . , k − 1}. Por lo tanto, π(u) ∈ πn(θ).
(iii) Sea u = (u1, . . . , uk) ∈ πn(θ) sabemos que uj ≤ K(u1,...,uj−1) para toda j ∈
{1, . . . , k} y k ≤ n. Sea ku(θ) = Ku entonces uj ∈ πn(θ) si y sólo si 1 ≤ j ≤ ku(θ).
Por consiguiente, θ es una variable aleatoria con respecto a F .
Denotaremos a la ley del árbol de Galton y Watson, GW . Sea t un árbol plano
con ráız. Se define [t]n como el conjunto de los árboles planos con ráız que coinciden
3.1. EL ÁRBOL DE GALTON Y WATSON 31
con t en las primeras n generaciones. En otras palabras,
[t]n = {t′ ∈ A; πn(t′) = πn(t)}.
Si el árbol, t es de altura menor que n, entonces [t]n = {t}.
A continuación daremos una caracterización de la medida del árbol de Galton y Wat-
son general. Esta caracterización se parece a la caracterización de la medida del árbol
finito visto en el caṕıtulo 2, lema 2.17. Aunque, es importante notar que estamos
tomando árboles infinitos y “rebanándolos” a la altura n.
Lema 3.4. Sea t un árbol plano con ráız y sea [t]n = {t′ ∈ A; πn(t′) = πn(t)} entonces
GW [t]n =
∏
v∈t;|v|<n
pkv(t)
donde p es la distribución de descendencia.
Demostración. Sea t un árbol plano con ráız. Ahora si t′ ∈ [t]n, para todo v vértice
de t′ tal que |v| ≤ n, v ∈ t. Como los árboles t′ en el conjunto [t]n coinciden con t
hasta la generación n, tienen el mismo número de hijos que en el árbol t, en otras
palabras, si |v| < n y v ∈ t′ tenemos que kv(t) = kv(t′). Podemos concluir que,
[t]n = {t′ ∈ A; kv(t) = kv(t′) para todo v ∈ t, |v| < n}.
En consecuencia,
GW [t]n = GW ({t′ ∈ A; kv(t′) = kv(t) para todo v ∈ t, tal que |v| < n})
=
∏
u∈t,|u|<n
P(Ku = ku(t))
=
∏
u∈t,|u|<n
pku(t)
las últimas igualdades se deben a que las (Ku, u ∈ U) son variables aleatorias inde-
pendientes e idénticamente distribuidas, con distribución p.
Como en los caṕıtulos 1 y 2 asociaremos una martingala al proceso de Galton y
Watson por medio del árbol θ. La diferencia con aquellos resultados se encuentra al
nivel de la filtración.
32 CAPÍTULO 3. EL ÁRBOL GW GENERAL Y CÓMO SESGARLO.
Teorema 3.5. Sean Zn = #{u ∈ θ; |u| = n} y la filtración {Fn = σ(πn)}n>0 entonces
Zn
mn
es una Fn martingala.
Demostración. Basta mostrar que la ley condicional de Zn+1 dado Fn bajo la ley GW
es igual a la convolución p∗Zn ; en efecto:
E(Zn+1/mn+1|Fn) =
∞∑
k=0
L∗Zn(k)
k
mn+1
=
mZn
mn + 1
= Zn/m
n.
Como todo elemento A ∈ Fn es una unión finitay disjunta de conjuntos de la forma
[t]n, pues Fn es la σ-álgebra generada por una función cuya imagen es un conjunto
finito, basta con verificar que
GW ([t]n, Zn+1 = k) = GW ([t]n)p ∗Zn(t) .
Para todo τ ∈ [t]n, Zn(τ) = Zn(t). Supongamos que Zn(t) = p y sean {u1, u2, . . . , up}
los vértices de la generación n. Como Zn+1 = k definimos a t
k1,...,kp como un árbol que
coincide con t hasta la generación n, que para toda sucesión (k1, . . . , kp) tengamos que∑p
i=1 ki = k y
kui(t
k1,...,Kp) = ki.
Si tk1,...,kp 6= tk′1,...,k′p los conjuntos [tk1,...,kp ]n+1, [tk′1,...,k′p ]n+1 son ajenos. Esto quiere decir
que para particiones distintas de k las imágenes inversas de conjuntos de árboles son
ajenas. Podemos escribir al conjunto {τ ∈ A; Zn+1(τ) = k} ∩ [t]n como una unión
disjunta de imágenes inversas, es decir,
{τ ∈ A; Zn+1(τ) = k} ∩ [t]n =
⋃
(k1,...,kp);
∑p
i=1 ki=k
[tk1,...,kp ]n+1 (3.1)
Por el lema 3.4 y la igualdad (3.1), expresamos a GW ([t]n, Zn+1 = k) como
GW ([t]n, Zn+1 = k) =
∑
(k1,...,kp);
∑
ki=k
∏
|v|<n+1
Kv(t
k1,...,kp)
3.2. CONSTRUCCIÓN HEURÍSTICA DEL ÁRBOL SESGADO. 33
Utilizando de nuevo el lema 3.4 y el hecho que las variables aleatorias Ku son inde-
pendientes, ocurre que
GW ([t]n, Zn+1 = k) =
∏
|v|<n
Kv(t)
∑
(k1,...,kp);
∑
ki=k
∏
|v|=n
Kui = ki
= GW ([t]n)P(K1 + K2 + · · ·+ Kp = k)
= GW ([t]n)p
∗p(k)
donde p es la distribución de descendencia. Por lo tanto,
GW ([t]n, Zn+1 = k) = GW ([t]n)p
∗Zn(t)(k).
Resulta que la ley condicional de Zn+1 dado Fn bajo la ley GW es igual a p∗Zn .
Concluyendo que Zn es una Fn martingala.
3.2. Construcción heuŕıstica del árbol sesgado por
tamaño
Para poder definir el árbol sesgado por tamño primero daremos la definición de
una variable aleatoria sesgada por tamaño.
Definición 3.6. Sea X una variable aleatoria no negativa de media finita y positiva.
Se dice que X̂ tiene la distribución sesgada por tamaño de X si
E(g(X̂)) =
E(Xg(X))
E(X)
para toda función de Borel positiva, g.
p es la distribución de descendencia, es decir P(L = k) = pk. Por definición, la
distribución sesgada por tamaño L̂ de L es tal que P(L̂ = k) = kpk
m
. Para mostrar que
L̂, definida de la forma anterior es la distribución sesgada por tamaño basta observar
que por una parte
E(Lg(L))
E(L)
=
∑∞
k=0 kg(k)pk
m
34 CAPÍTULO 3. EL ÁRBOL GW GENERAL Y CÓMO SESGARLO.
y por otra,
E(g(L̂)) =
∑∞
k=0 g(k)kpk
m
.
para toda g función medible positiva.
Ahora construiremos el árbol sesgado por tamaño; Sean L̂1, L̂2, . . . variables aleato-
rias independientes e idénticamente distribuidas con distribución sesgada por tamaño
de p. Empezamos con un vértice llamémoslo v0. A v0 le damos L̂1 número de hijos.
Se escoge aleatoriamente un hijo de v0, llamémoslo v1. A los demás hijos de v0 les
asignamos árboles independientes de Galton y Watson. Pero v1 tendrá L̂2 números de
hijos. Se escoge al azar a un hijo de v1, se le llama v2. A los demás hijos se les asocia
un árbol de Galton y Watson independiente de los demás. Pero v2 tiene L̂3 hijos.
Aśı sucesivamente, se repite el proceso para cada generación. Es importante notar que
P(L̂ = 0) = 0, lo que nos dice que en cada generación siempre se puede escoger un
vértice, por lo tanto este árbol siempre será infinito. A partir de esta construcción,
podemos describir, de manera heuŕıstica, la ditribución conjunta del árbol sesgado por
tamaño y de las trayectorias de los vértices distinguidos (v0, v1, . . . ). Una trayectoria
es una sucesión de vértices (v0, v1, . . . ) donde cada vértice está en una generación y
el vértice que sigue en la sucesión está en la siguiente generación sin poder regresar a
las generaciones anteriores. A la distribución conjunta la denotaremos por ĜW∗.
En la figura 3.1 se da una representación gŕafica de la construcción del árbol
sesgado por tamaño.
Sea t un árbol plano con ráız y v un vértice en la n-ésima generación. Se definen
[t; v]n
como el conjunto de parejas de árboles y trayectorias en ellos tal que el árbol es un
elemento de [t]n y la trayectoria pasa por v. Ahora supongamos que t tiene altura
mayor o igual a n + 1 (n ≥ 0) y la ráız tiene k hijos. Sean t1, t2, . . . , tk, los árboles
trasladados a los hijos de la ráız. Cualquier vértice v de la generación n + 1 está en
algún árbol trasladado, supongamos que v ∈ ti. La ráız tiene k hijos con probabilidad
kpk
m
. De esos k hijos escojo uno uniformemente con probabilidad 1
k
. Como v está en
3.2. CONSTRUCCIÓN HEURÍSTICA DEL ÁRBOL SESGADO. 35
el árbol ti entonces puedo separar la distribución conjunta ĜW∗ en dos partes; una
parte, es la distribución conjunta del árbol ti y las trayectorias que pasan por v; y la
otra parte, es la distribución de los demás árboles tj los cuales no tienen trayectorias
distinguidas. Por lo tanto, la medida ĜW∗ cumple:
ĜW∗[t; v]n+1 =
kpk
m
1
k
ĜW∗[ti; v]n
∏
j 6=i
GW [tj]n. (3.2)
Si escogemos el vértice v uniformemente en cada generación, no hacemos ninguna
distinción entre ellos. Resulta que la medida ĜW∗ en el conjunto [t; v]n+1 no depende
del vértice v.
Figura 3.1: Representación gráfica del árbol sesgado por tamaño.
Lema 3.7. Para toda n ∈ N y para todo [t; v]n la medida ĜW∗ cumple que
ĜW∗[t; v]n =
1
mn
GW [t]n (3.3)
Demostración. Utilizando el lema 3.4, la prueba es por inducción.
Para n = 1 ĜW∗[t; v]1 =
pk
m
= 1
m
GW ([t]1).
Supongamos que para s < n se cumple. Sea t un árbol de altura mayor o igual a n
36 CAPÍTULO 3. EL ÁRBOL GW GENERAL Y CÓMO SESGARLO.
y v un vértice en la generaćıon n tal que v es un elemento del árbol ti trasladado
al i-ésimo hijo de la ráız. Por construcción de la medida tenemos que ĜW∗[t; v]n =
kpk
m
1
k
ĜW∗[ti; v]n−1
∏
j 6=i GW [tj]n−1. Como ti es de altura menor o igual a n − 1, por
hipótesis de inducción, tenemos que
ĜW∗[t; v]n =
1
mn
pk
k∏
i=1
GW ([ti]n−1)
=
1
mn
GW ([t]n).
Definimos a Wn(t) = Zn(t)/m
n. Hasta ahora tenemos la distribución conjunta
ĜW∗ del árbol sesgado T̂ y las trayectorias distinguidas (v0, v1, . . . ), pero nos interesa
solamente la distribución del árbol sesgado. Si sumamos sobre todas las trayectorias
posibles, como la distribución conjunta no depende de las trayectorias tenemos que la
distribución marginal de T̂ se puede escribir como
ĜW [t]n = Wn(t)GW [t]n (3.4)
para toda n ∈ N y para todo árbol t con ráız.
De (3.3) podemos ver que dados los primeros n niveles del árbol T̂ , la medida ĜW∗
hace que el vértice vn del camino aleatorio (v0, v1, . . . ) se distribuya uniformemente
en el nivel n del árbol T̂ .
De (3.4), podemos decir que para toda A ∈ σ(πn),
ĜW (A) = GW (1AWn)
pues A ∈ σ(πn) se puede escribir como una unión finita y ajena de imágenes inversas
de árboles en An. Dicha definición tiene sentido pues como Wn es martingala con
respecto a Fn, si n ≥ m y A ∈ Fm, GW (1AWn) = GW (1AWm).
Para formalizar la construcción de la medida del árbol sesgado por tamaño, quer-
emos una medida ĜW definida en F que satisfaga que: para toda A ∈ σ(πn)
ĜW (A) = GW (1AWn).
3.3. FORMALIZACIÓN A PARTIR DEL TEOREMA DE PARTHASARATHY. 37
Como F = σ(∪n∈NFn) y hemos argumentado como definirla en Fn se trata sim-
plemente de un teorema de extensión. Dicha extensión se puede hacer mediante el
teorema de Carathéodory-Hahn (ver apéndice) para el cual es necesario verificar una
cierta σ-aditividad. No haremos ésto pues dicha σ-aditividad y por lo tanto la posi-
bilidad de una extensión se pueden obtener de un teorema general parecido al de
Kolmogorov.
3.3. Formalización a partir del teorema de ĺımite
inverso de Parthasarathy.
La idea principal de esta sección es demostrar la existencia de la medida del árbol
sesgado por tamaño en el conjunto de árboles planos. Utilizaremos el teorema de
Parthasarathy. El teorema de Parthasarathy es un teorema de extensión de medida
de una sucesión de espacios de Borel al espacioĺımite inverso de estos mismos. El
ĺımite inverso [Par67] (Y, C ) de una sucesión de espacios de Borel (Yn,Cn) relativo a
los mapeos medibles (πn) de Yn+1 en Yn cumple lo siguiente:
(i) Y = {(y1, y2, . . . ); yn ∈ Yn y yn = πn(yn+1) para toda n ∈ N}
(ii) C es la σ-álgebra más pequeña donde las funciones π̃n; (y1, y2, . . . ) 7→ yn de Y
en Yn son medibles para toda n ∈ N. A las función π̃n se le llama el mapeo
canónico de Y en Yn.
Enunciamos a continuación el Teorema de Parthasarathy. El teorema original se puede
consultar en [Par67]. También se puede encontrar una versión en el libro [Kal02].
Teorema 3.8 (Teorema de Parthasarathy). Para toda n = 1, 2, . . . sean (Yn,Cn)
espacios de Borel y πn un mapeo medible de Yn+1 a Yn. Sea (Y, C ) el ĺımite inverso de
los espacios de Borel (Yn,Cn) relativo a los mapeos πn. Si µ1, µ2, . . . es una sucesión
de medidas tal que
(i) µn es una medida definida sobre Cn.
38 CAPÍTULO 3. EL ÁRBOL GW GENERAL Y CÓMO SESGARLO.
(ii) µn(A) = µn+1(π
−1
n (A)) para todo A ∈ Cn.
Entonces existe una única medida µ sobre C tal que µ((π̃n)−1(A)) = µn(A) para todo
A ∈ Cn donde π̃n es el mapeo canónico de Y en Yn.
Nota: Para la definición de espacio de Borel ver el apéndice.
Interpretaremos al espacio de árboles A como un ĺımite inverso; para ésto recorde-
mos, de las secciones anteriores, la definición de An como el conjunto de árboles de
altura menor o igual a n. En estos conjuntos discretos definimos ahora la σ-álgebra
potencia y la denotamos por P (An). Los espacios (An, P (An)) son en consecuencia,
de Borel. Ya hemos definido una proyección natural de An+1 en An, a saber, la fun-
ción πn con ley de correspondencia πn(tn+1) = {u ∈ tn+1; |u| ≤ n}. En el lema 3.9
demostraremos que el espacio de árboles A y el ĺımite inverso de los espacios An
son σ-isomorfos (esto es, existe una biyección bimedible entre ellos); un elemento del
ĺımite inverso es una sucesión creciente de árboles finitos por lo que el ĺımite de éste,
es naturalmente su unión. El σ-isomorfismo asigna a cada sucesión del ĺımite inverso
(y1, y2, . . . ) su unión
⋃
i∈N yi. En consecuencia, es equivalente demostrar la existencia
de la medida del árbol sesgado por tamaño en el ĺımite inverso de los An. Recordemos
la definición 3.2, las sucesiones de funciones πn:
πn : A → An como πn(t) = tn = {u ∈ t; |u| ≤ n}.
Definimos para toda n ∈ N las σ-álgebras Fn = σ(πk; k ≤ n) = σ(πn) y F =
σ(πn; n ∈ N) = σ(∪n∈NFn).
Tenemos los espacios de Borel (A,Fn) donde definimos la medida µ̃n como
µ̃n(A) = GW (1AWn)
para todo A ∈ Fn y los espacios de Borel (An, P (An)) donde definimos las medidas
µn como
µn = µ̃n ◦ (πn)−1.
3.3. FORMALIZACIÓN A PARTIR DEL TEOREMA DE PARTHASARATHY. 39
Ahora, veamos que {µn}n satisface las hipótesis del teorema de Parthasarathy. Sea
C ⊂ An. Queremos demostrar que
µn+1 ◦ (πn)−1(C) = µn(C).
Sabemos que para toda A ∈ Fn, µ̃n+1(A) = µ̃n(A) y notemos que πn ◦ πn+1 = πn. En
consecuencia, tenemos que
µn+1 ◦ (πn)−1(C) = µ̃n+1((πn)−1)(C).
Como (πn)−1(C) es un conjunto medible con respecto a Fn podemos concluir que
µ̃n+1((π
n)−1(C)) = µ̃n((πn)−1(C))
= µn(C).
Por lo tanto, {µn} satisface la hipótesis de consistencia del teorema de Parthasarathy.
Denotaremos al ĺımite inverso de los espacios de árboles de altura finita con respecto
a la sucesión de funciones {πn; n ∈ N} por (An←−,C ). Existe una única medida
µ : C → [0, 1]
en el ĺımite inverso (An←−,C ) tal que µ((π)
n−1(A)) = µn(A) para todo A ∈ P (An).
Como (An←−,C ) y (A, F ) son σ-isomorfos (llamémosle Γ : (An←−,C ) → (A, F ) al iso-
morfismo), podemos trasladar la medida µ al espacio de árboles puesto que Γ es
medible, definiendo ĜW = µ ◦ (Γ)−1. Falta verificar que ĜW cumple que para toda
A ∈ Fn, ĜW (A) = GW (1AWn).
Como C es la σ-álgebra más pequeña donde {πn}n son medibles podemos concluir
que para toda A ∈ Fn
ĜW (A) = µ ◦ (Γ)−1(A) = µ̃n(A)
= GW (1AWn).
Solamente falta demostrar el σ-isomorfismo entre el espacio de árboles A y el ĺımite
inverso.
40 CAPÍTULO 3. EL ÁRBOL GW GENERAL Y CÓMO SESGARLO.
Teorema 3.9. Sea (An←−, σ(∪n∈Nπ
n)) el ĺımite inverso de los espacios de Borel (An, P (An)),
los árboles planos de altura menor o igual a n. Sea
Γ : (An←−, σ(π
n, n ∈ N)) → (A, σ(πn, n ∈ N) tal que
Γ(y1, y2, . . . , yn, . . . ) =
⋃
n∈N
yn.
Entonces Γ es un isomorfismo bimedible.
Para poder demostrar el isomorfismo necesitamos el uso del siguiente lema que
enunciamos ahora y probamos por último en esta sección.
Lema 3.10. Sean (Y, C ) un ĺımite inverso de los espacios de Borel (Yn,Cn) con
respecto a las funciones medibles πn y sea (E, Ξ) un espacio de Borel.
Para toda función f : (E, Ξ) → (Y, C ), se tiene que:
f es medible si y sólo si πn ◦ f es medible para toda n ∈ N donde πn es la proyección
canónica de Y en Yn.
Demostración del teorema 3.9. Primero demostraremos que
∞⋃
m=1
ym = γ(y1, y2, . . . )
es un árbol plano con ráız.
∅ ∈ ⋃m∈N ym ya que ym es un árbol de altura n y ∅ ∈ ym para toda m ∈ N.
Sea v ∈ ⋃m∈N ym \ {∅} existe n0 ∈ N tal que v ∈ yn0/{∅}. De hecho se cumple,
por definición de ĺımite inverso que el vértice v es un elemento de cualquier yn
para n > n0. Como yn0 es un árbol finito, el padre de v también es un elemnto
de yn0 , es decir, κ(v) ∈ yn0 . Por lo tanto, κ(v) ∈
⋃
m∈N ym.
Sea v ∈ ⋃m∈N ym. Como mencionamos anteriormente, v ∈
⋃
m∈N ym si y sólo si
v ∈ ym para todo m ≥ |v|. Esto es cierto si y sólo si v ∈ (π|v|+1 · · · ◦ πm−1 ◦
πm)(ym) = y|v| si y sólo si v ∈ y|v|. Entonces podemos suponer que v ∈ y|v|+1. El
árbol y|v|+1 es finito, existe kv ≤ 0 tal que vj ∈ y|v|+1 si y sólo si 1 ≤ j ≤ kv. Por
lo tanto, vj ∈ ⋃n∈N ym si y sólo si vj ∈ y|v|+1 si y sólo si 1 ≤ j ≤ kv.
3.3. FORMALIZACIÓN A PARTIR DEL TEOREMA DE PARTHASARATHY. 41
Por consiguiente,
⋃
m∈N ym es un árbol plano con ráız.
Sea Ψ : (A, σ(πn, n ∈ N) → (An←−, σ(π
n, n ∈ N)) tal que
Ψ(t) = (π1(t), π2(t), . . . , πn(t), . . . ).
Necesitamos demostrar que Ψ es la función inversa de Γ, i.e. Ψ ◦ Γ = I y Γ ◦Ψ = I.
Sea t ∈ A entonces Ψ(t) = (π(t), . . . , πn(t), . . . ) y Γ(Ψ(t)) = ⋃∞n=1 πn(t). Falta
demostrar que
∞⋃
n=1
πn(t) = t.
Sea v ∈ t. Supongamos que |v| = n por definición de πn tenemos que v ∈ πn(t)
y nos queda que v ∈ ⋂∞n=1 yn. Ahora sea v ∈
⋃∞
n=1 π
n(t) existe n0 ∈ N tal que
v ∈ πn0(t) ⊂ t. Por lo tanto, ⋃∞n=1 πn(t) = t. Tenemos que Γ(Ψ) = I.
Falta verificar que Ψ ◦ Γ = I. Es decir, necesitamos demostrar que
πn(
⋃
n∈N
ym) = yn.
Por definición de πn obtenemos que πn(
⋃
n∈N ym) = {v ∈
⋃
n∈N ym; |v| ≤ n}. Para todo
v ∈ πn(⋃n∈N ym) podemos decir que v ∈ y|v| ⊂ ym para toda m ≥ |v|. En particular,
n ≥ |v| y v ∈ yn. Como v ∈ yn y |v| ≤ n entonces v ∈ πn(
⋃
n∈N ym). Por lo tanto, Γ es
una biyección.
Falta demostrar que Γ es bimedible, Para esto utilizamos el lema anterior.
Sea (E, Ξ) = (A,F ). Basta notar que πn ◦ Ψ = πn para toda n ∈ N. Como
F = σ(πn; n ∈ N), entonces πn son medibles y Ψ es medible.
Γ es medible ya que πn ◦ Γ = πn y C es la σ-álgebra mas pequeña que hace que
πn sea medible para toda n ∈ N.
Entonces Γ es un σ-isomorfismo entre el ĺımite inverso de los árboles planos finitos y
los árboles planos A.
42 CAPÍTULO 3. EL ÁRBOL GW GENERAL Y CÓMO SESGARLO.
Demostración lema 3.10. Primero supongamos que f es medible. Sea B ∈ C entonces
(πn◦f)−1(B) = (f)−1◦(πn)−1(B). Como cada πn es medible nos queda que πn−1(B) ∈
C . Entonces (π̃n ◦ f)−1(B) ∈ Ξ. Por lo tanto π̃n ◦ f es medible para toda n ∈ N.
Suponemos que π̃n ◦ f es medible. Por hipótesis para toda C = (πn)−1(A) con
A ∈ Cn la imagen inversa de C es medible, es decir, f−1(C) ∈ Ξ.
Sea B = {f−1(C); C = (πn)−1(A), A ∈ Cn} Tenemos que σ(f−1(B)) = f−1(σ(B)).
Ahora f−1(C ) = f−1(σ(B)) = σ(f−1(B)) además σ(f (B)) ⊂ Ξ. Por lo tanto, f es
una función medible.
3.4. El teorema de Parthasarathy y el de consis-
tencia de Kolmogorov.
Se demostró la existencia de la medida del árbol sesgado en el espacio de árboles
utilizando el teoremade Parthasarathy. Inicialmente, podŕıamos pensar que el teorema
de existencia de Parthasarathy es un teorema más general que el teorema usual de
existencia de Kolmogorov ya que al producto cartesiano lo podemos ver como un ĺımite
inverso; definiendo a la sucesión de espacio como X1 = (Y1), X2 = (Y1, Y2), . . . , Xn =
(Y1, Y2, . . . , Yn), . . . y el limite inverso es X =
∏
i∈N(Y1, . . . , Yi) =
∏∞
i=1 Xi.
Sin embargo, en esta sección demostraremos que el teorema de Parthasarathy
está implicado por el teorema de Kolmogorov. La prueba se dividirá en 4 pasos:
1. Construir las medidas de probabilidad νn en los productos finitos de espacios
de Borel en términos de la sucesión de medidas µn definidas por el teorema de
Parthasarathy.
2. Demostrar que {νn} cumplen la hipótesis de consistencia del teorema de Kol-
mogorov, utilizando que son consistentes bajo el teorema de Parthasarathy.
3. Probar que el ĺımite inverso, es un conjunto medible con respecto a la σ-álgebra
producto.
3.4. EL TEOREMA DE PARTHASARATHY Y DE KOLMOGOROV. 43
4. Ver que la medida construida en el producto cartesiano a través del teorema de
Kolmogorov esté concentrada en el ĺımite inverso.
Primero recordemos el teorema de Kolmogorov, que se puede consultar en [Kal02].
Teorema 3.11 (Teorema de Kolmogorov.). Sean (Ei, Ξi) espacios de Borel, para toda
n ∈ N y ν1, ν2, . . . medidas de probabilidad que satisfacen:
(a) νi está definida en la σ-álgebra producto Ξ1 ⊗ · · · ⊗ Ξi.
(b) Sea ρi : E1×· · ·×Ei+1 → E1×· · ·×Ei como ρi(x1, x2, . . . , xi+1) = (x1, x2, . . . , xi)
entonces νi+1 ◦ (ρi)−1 = νi para toda i ∈ N.
Entonces existe una medida de probabilidad ν en
∏
i∈NEi tal que ν ◦(ρi)−1 = νi. donde
ρi(x1, x2, . . . ) = (x1, . . . , xi).
Recodemos la función πn : En+1 → En como πn(xn+1) = xn para cada n ∈ N
y una sucesión de medidas de probabilidad {µn}n∈N que satisfacen las hipótesis del
teorema de Parthasarathy, i.e.,
1. µn : Ξn → [0, 1].
2. Para toda A ∈ Ξn µn+1(πn)−1(A) = µn(A).
Recordemos, adicionalmente, la definición de ĺımite inverso:
E = {(x1, x2, . . . ); xi ∈ Ei, πi(xi+1) = xi} con la σ-álgebra generada por los mapeos
canónicos πn de E en En. Definimos en el espacio producto de los espacios (En, Ξn)
las mismas proyecciones canónicas que en el ĺımite inverso E como πn :
∏
i∈NEi →
En, π
n(x1, x2, . . . ) = xn, entonces la σ-álgebra del producto es Ξ = σ(π
n, n ∈ N).
Además, definimos otra sucesión de funciones π1,n : En → E1 × E2 × · · · × En como
π1,n(x) = ((π1 ◦ π2 · · · ◦ πn−1)(x), (π2 ◦ · · · ◦ πn−1)(x), . . . , (πn−1)(x), x).
44 CAPÍTULO 3. EL ÁRBOL GW GENERAL Y CÓMO SESGARLO.
Ya que tenemos el marco teórico necesario para definir la nueva sucesión de me-
didas de probabilidad {νn}n∈N:
νn = µn ◦ π−11,n. (3.5)
Nota: En particular, si A = A1 × A2 × · · · × An con Ai ∈ Ξi, tenemos que
π1,n(A) = An ∩ π−1n−1(An−1) ∩ · · · ∩ (π1 ◦ · · · ◦ πn−1)−1(A1), entonces
νn(A1 × · · · × An) = µn(An ∩ π−1n−1(An−1) ∩ · · · ∩ (π1 ◦ · · · ◦ π−1n−1)(A1)). (3.6)
Esta expresión para los generadores nos servirá para demostrar la consistencia requeri-
da en el teorema de Kolmogorov.
Veamos que las medidas definidas en (3.5) son consistentes.
Si para toda n ∈ N definimos ρn : E1 × · · · × En × En+1 → E1 × · · · × En como
ρn(x1, x2, . . . , xn, xn+1) = (x1, x2, . . . , xn). Probaremos que νi+1 ◦ ρ−1i = νi. Sean A1 ∈
Ξ1, . . . , An ∈ Ξn. Las medidas νn cumplen en los conjuntos generadores de la σ-
álgebra producto la ecuación (3.6) y utilizando la definición de νn y la consistencia de
las medidas µn tenemos que
νn+1(ρn)
−1(A1 × · · · × An) = µn+1(π−1n ((An ∩ · · · ∩ (π1 ◦ π2 ◦ · · · ◦ πn−1)−1(A1))
= νn(A1 × · · · × An).
Como las medidas son consistentes en los generadores de la σ-álgebra producto, son
consistentes en toda la σ-álgebra producto. Las medidas cumplen las hipótesis del
teorema de Kolmogorov.
Por el teorema de Kolmogorov existe una única medida de probabilidad ν :
σ(πn; n ∈ N) → [0, 1] tal que ν ◦ (ρn)−1 = νn donde ρn :
∏
n∈NEn → E1 × · · · × En es
una función definida como ρn(x1, . . . ) = (x1, . . . , xn).
Es claro que E está contenido en el producto de los Ei. Podemos escribir al ĺımite
inverso como
E =
⋂
i≥1
{x ∈
∏
n∈N
En; πi(π
i+1(x)) = πi(x)} (3.7)
3.4. EL TEOREMA DE PARTHASARATHY Y DE KOLMOGOROV. 45
Sabemos que πi, πi son funciones medibles para toda i ∈ N, por lo tanto, en el conjunto
donde son iguales también es medible. Por consiguiente, E ∈ σ(πn; n ∈ N). Como E
cumple la ecuación (3.7) definimos a los conjuntos Bi = {x ∈
∏
n∈NEn; πi(π
i+1(x)) =
πi(x)}. Probaremos, por último, que
ν(B1 ∩ · · · ∩Bn) = 1
para toda n ∈ N. Utilizando la propiedad de ν heredada de la sucesión de medidas νn
y la definición de los conjuntos Bi y las definiciones de las funciones ρ
n y π1,n podemos
concluir que
ν(B1 ∩ · · · ∩ Bn) = µn(π−11,n({x ∈ E1 × · · · × En; πi(xi+1 = xi)}))
= µn(En) = 1
Concluimos definiendo la medida en el ĺımite inverso (E, C ) como ν̃ : C → [0, 1] tal
que para toda A en la σ-álgebra producto, ν̃(A) = ν(A ∩ E).
El teorema de Parthasarathy es un caso particular del teorema de Kolmogorov.
Recapitulando, podemos decir que el árbol sesgado por tamaño existe en el con-
junto de árboles y su distribución cumple que para toda n ∈ N, para todo árbol
t ∈ A,
ĜW [t]n = Wn(t)GW [t]n
donde Wn es una martingala con respecto a GW .
Caṕıtulo 4
Aplicaciones del árbol sesgado a los
procesos de Galton y Watson
En el árticulo [LPP95], se demuestran tres teoremas clásicos. La pregunta que
estos tres teoremas resuelven es, si podemos estimar o encontrar el orden asimptótico
de P(Zn > 0). La respuesta fue dada para el caso supercŕıtico, subcŕıtico y cŕıtico, por
Kesten-Stigum [KS66], Heathcote [Hea65] y Yaglom-Kolmogorov [KNS66] respectiva-
mente. Los teoremas son:
Teorema 4.1 (Caso supercŕıtico: Kesten-Stigum.). Supongamos que 1 < m < ∞ y
sea W el ĺımite de la martingala Zn
mn
. Las siguientes afirmaciones son equivalentes:
(i) P(W = 0) = q donde q = ĺımn→∞ P(Zn = 0).
(ii) E(W ) = 1
(iii) E(Llog+L) < ∞.
Teorema 4.2 (Caso subcŕıtico: Heathcote.). La sucesión
{
P(Zn>0)
mn
}
n∈N
es decreciente.
Si m < 1 entonces las siguientes afirmaciones son equivalentes:
(i) ĺımn→∞
P(Zn>0)
mn
> 0.
(ii) supE(Zn|Zn > 0) < ∞.
46
4.1. PRELIMINARES 47
(iii) E(Llog+L) < ∞.
Teorema 4.3 (Caso cŕıtico: Estimación de Kolmogorov y ley ĺımte de Yaglom.).
Supongamos que m = 1 y σ2 := V ar(L) = E(L2)− 1 < ∞ entonces tenemos:
(i) Estimación de Kolmogorov:
ĺım
n→∞
nP(Zn > 0) =
2
σ2
.
(ii) La ley ĺımite de Yaglom: La distribución condicional de Zn/n dado Zn > 0
converge cuando n →∞ a una ley exponencial con media σ2/2.
En este caṕıtulo se demuestra que bajo la ley ĜW, los vértices fuera de la trayecto-
ria distinguida (v0, v1, . . . ) son un proceso de ramificación con inmigración. Utilizando
este hecho es que se demuestran los tres teoremas.
4.1. Preliminares
Recordemos la construcción del árbol sesgado por tamaño vista en el caṕıtulo 3,
sección 3.2: empezamos con un vértice v0. El vértice v0 tiene una cantidad aleatoria
de hijos con ley sesgada por tamaño de la distribución de descendecia. Como la ley
sesgada por tamaño toma el valor cero con probabilidad cero, entonces en la siguiente
generación podemos escojer al azar un hijo de v0, llamémoslo v1. A los demás hijos de
v0 les asociamos árboles independientes de Galton y Watson con la ley de descendecia.
El vértice v1 con ley sesgada por tamaño independiente de v0 tiene una cantidad
aleatoria de hijos. Repito el procedimiento con los hijos de v1. Es decir, escojo un hijo
de v1 al azar y a los demás hijos les asociamos árboles normales de Galton y Watson
independientes. Aśı sucesivamente para cada generación.
Regresando a la pregunta formulada al inicio de este caṕıtulo, mencionamos que
los vértices fuera de la trayectoria (v0, v1, . . . ) del árbol sesgado por tamaño forman
48 CAPÍTULO 4. ÁRBOL SESGADO