Los seguidores de Manolo

Archive for the ‘Probabilidad y Estadística’ Category

Recurrencia de grafos con crecimiento cuadrático

In Probabilidad y Estadística on Jueves 16, noviembre, 2017 at 8:05 am

por Pablo Lessa

Consideremos un grafo conexo con aristas no orientadas y un número finito de aristas saliendo de cada vértice. Fijemos un vértice o en el grafo y consideremos una caminata simple, es decir una sucesión de vértices al azar x_0,x_1,\ldots con x_0 = o y donde en cada paso x_{n+1} se elige al azar entre los vecinos de x_n (cada vecino tiene la misma probabilidad y todas las elecciones son independientes entre sí).

Una caminata de este tipo es recurrente, si casi seguramente (i.e. con probabilidad 1) pasará por cada vértice del grafo infinitas veces.

Definamos un conjunto de corte como un conjunto finito de aristas tales que cualquier camino partiendo de o y que recorre un número infinito de vértices diferentes debe contener alguna arista del conjunto.

El siguiente criterio da una condición suficiente para la recurrencia de un grafo.

Teorema [Criterio de Nash-Williams]:
Si un grafo admite una familia de conjuntos de corte disjuntos A_1,A_2,\ldots tal que
\sum\limits_{k = 1}^{+\infty}|A_k|^{-1} = +\infty
entonces la caminata simple en el grafo es recurrente.

Un ejemplo consiste en considerar como grafo \mathbb{Z}^2 donde cada vértice tiene 4 vecinos como es usual (dos en horizontal y dos en vertical). Es fácil construir una sucesión de conjuntos de corte donde |A_k| es de orden k y por lo tanto el criterio Nash-Williams implica que la caminata simple es recurrente. Lee el resto de esta entrada »

Anuncios

Convergencia de funciones y medidas.

In Análisis Real y Complejo, Probabilidad y Estadística on Lunes 19, julio, 2010 at 7:03 pm

por Pablo Lessa

Quiero escribir un poco sobre la relación entre convergencia puntual de funciones medibles y convergencia débil de medidas de probabilidad en el contexto de espacios métricos completos y separables.

Para simplificar la discusión voy a tomar como espacio de probabilidad \mathbb{R} con la \sigma-álgebra de Borel (i.e. la generada por los abiertos).   Vamos a considerar diferentes medidas de probabilidad en este espacio pero utilizaremos \lambda para denotar la medida de Lebesgue restringida al intervalo [0,1] (i.e. la distribución uniforme en [0,1]).

Posiblemente el primer punto interesante de la teoría de la medida es que los limites puntuales de funciones medibles también son medibles.  Esto es una mejora sobre la teoría de integración Riemann en la cual, por ejemplo, existen funciones derivables cuya derivada no es integrable.

Teorema. Si f_n: \mathbb{R} \to \mathbb{R} es Borel-medible para todo n y existe f = \lim_{n \to +\infty}f_n entonces f es Borel-medible.

Demostración. Todo abierto A se puede escribir como unión creciente y numerable de abiertos A_k cuya clausura está contenida en A.   Una vez hecho esto se ve que f(x) = \lim_n f_n(x) \in A si y sólamente si existe k tal que a partir de cierto n_0 se cumple que f_n(x) \in A_k para todo n \ge n_0.  Esto implica que f^{-1}(A) se puede escribir con uniones e intersecciones numerables a partir de los f_n^{-1}(A_k) que son medibles.  Explícitamente se obtiene:

f^{-1}(A) = \bigcup_k \bigcup_{n_0} \bigcap_{n \ge n_0} f_n^{-1}(A_k)

\Box

Si f:\mathbb{R} \to \mathbb{R} es medible, y consideramos en \mathbb{R} la medida de probabilidad \lambda, entonces f da origen a una nueva medida de probabilidad f_*\lambda llamada la medida “push-forward” o la distribución de f.   Esta medida se define a traves de la ecuación:

f_*\lambda(A) = \lambda(f^{-1}(A))

Para sucesiones de funciones convergentes. ¿Cual es la relación entre las distribuciones de la sucesión y la de su límite?

Lee el resto de esta entrada »

Una conjetura de escape hiperbólico

In Grupos y geometría, Probabilidad y Estadística, Sistemas Dinámicos on Lunes 17, mayo, 2010 at 12:04 pm

por Pablo Lessa

Voy a presentarles una idea que tengo para un teorema en sistemas dinámicos.  La idea es conseguir un análogo a algunas cosas que pasan en paseos al azar en “espacios grandes”.   Obviamente, además del hecho de que lo que digo va estar por necesidad “mal formulado”, también hay una gran chance de que directactamente la idea sea mala, o algunas de las cosas que digo esten mal.  Por eso mismo me parece interesante discutirla con el resto del coloquiooleis, si estan interesados.

Lee el resto de esta entrada »

Medidas invariantes y Teorema de Descomposición Ergódica.

In Análisis Real y Complejo, Probabilidad y Estadística, Sistemas Dinámicos on Jueves 29, abril, 2010 at 10:41 am

por Rafael Potrie

Consideremos un homeomorfismo f:X\to X donde X es un espacio métrico compacto. Decimos que una medida de probabilidad \mu en X es f-invariante, si se cumple que \mu(f^{-1}(A))=\mu(A) para todo conjunto medible A.

Estas medidas son generalmente muy útiles para estudiar la dinámica del homeomorfismo como se ver rápidamente al ver los enunciados del Teorema de Recurrencia de Poincare o el Teorema Ergódico de Birkhoff (una prueba de este último bastante simple se encuentra en este link de este mismo blog).

Hay cierto tipo de medidas invariantes que son preferidas, por ser de alguna manera, indescomponibles, estas son llamadas medidas ergódicas y verifican que si A es un conjunto f-invariante, entonces, su medida es cero o uno.

Mediante resultados clasicos de analisis funcional, se puede probar que en general, existen medidas invariantes (para un homeomorfismo de un espacio métrico compacto) e incluso medidas ergódicas. Lo primero, es una consecuencia relativamente directa del Teorema de Banach-Alaoglu, que garantiza que el espacio de medidas de probabilidad es compacto con la topología débil (y por tanto, si se construye una medida “cada vez más invariante”, su límite será invariante) y lo segundo surge del Teorema de Krein-Milman ya que dado que las medidas invariantes forman un convexo compacto, tienen que tener elementos extremales (que serán las medidas ergódicas). Sin embargo, este último teorema, que nos permite aproximar toda medida invariante por combinaciones convexas de medidas ergódicas, no termina de mostrar realmente como es esta descomposición.

El objetivo de esta nota, es presentar un formalismo, el de las particiones medibles y medidas condicionales que permiten dar un sentido a dicha descomposición.

Lee el resto de esta entrada »

Teorema de Convergencia de Martingalas

In Probabilidad y Estadística on Domingo 26, abril, 2009 at 6:28 pm

por Pablo Lessa

Este es el último de lo que resultó ser una serie de 3 artículos sobre esperanza condicional y martingalas.

El objetivo presente es demostrar el famoso Teorema de Convergencia de Martingalas.

Este teorema permite dar una demostración de la ley de grandes números y tiene otras aplicaciones.

La intuición detrás del resultado es que una martingala es una sucesión de variables aleatorias que si bien tienen la misma esperanza, tienden a crecer en tamaño (una forma de darle un sentido preciso a esto es notar que si X_n es una martingala entonces |X_n| y X_n^+ son submartingalas).  Por lo tanto si tenemos algún control sobre:

\text{sup}_nE(|X_n|)

o incluso sobre

\text{sup}_nE(X_n^+)

es razonable esperar que la sucesión X_n no varie mucho o incluso que tenga límite.

La prueba consiste en demostrar que para todo intervalo [a,b] con a < b, el número de veces que la sucesión X_0, \ldots, X_n atraviesa el intervalo de abajo hacia arriba está controlado por el tamaño esperado de la última variable X_n.  Este es el llamado lema de cruces, que demostraremos a continuación, luego de una disgresión sobre submartingalas.

Lee el resto de esta entrada »

Martingalas

In Probabilidad y Estadística on Domingo 26, abril, 2009 at 12:39 pm

por Pablo Lessa

Este artículo es la continuación de este otro sobre esperanza condicional.

Nuestro objetivo es entender el concepto de martingala.

Lee el resto de esta entrada »

Esperanza Condicional

In Probabilidad y Estadística on Domingo 19, abril, 2009 at 6:53 pm

por Pablo Lessa

Este artículo es el primero de una serie que voy a escribir a pedido del sambita.  La idea es llegar a entender el clásico teorema de convergencia de martingalas.  Luego el sambita se encargaría de utilizarlo para ayudar a demostrar algunos resultados en teoría de grupos.

En esta primera entrega el tema que nos ocupa es la definición formal e intuición, detrás del concepto de esperanza condicional.

Lee el resto de esta entrada »

El Teorema Ergódico Medio

In Probabilidad y Estadística, Sistemas Dinámicos on Miércoles 25, marzo, 2009 at 12:55 pm

por Pablo Lessa

En este artículo me dedico a hacer la prueba de la versión debil del teorema ergódico de Birkhoff. También intento traducir bien los conceptos desde el enfoque probabilístico al enfoque de transformaciones que preservan medida.

El teorema ergódio puede verse como una generalización de la ley de grandes números (la versión de Von Neumann corresponde a la ley débil, y la de Birkhoff a la ley fuerte).

Por ejemplo, supongamos que tenemos X_1, \ldots, X_n, \ldots variables aleatorias independientes e idénticamente distribuidas, todas en L^1(\Omega) (pongamosle E(X_n) = \mu). La ley de grandes números garantiza que:

\frac{1}{n}S_n \to \mu

con probabilidad 1, donde S_n = X_1 + \cdots + X_n.

Ahora si tomamos Y_n = X_n + X_{n+1}, es razonable suponer que los promedios de estas nuevas variables tiendan a 2\mu. Sin embargo dado que Y_n no es independiente de Y_{n+1} esa conclusión no se obtiene directo del teorema.

Generalizando lo anterior, si definimos Y_n = f(X_n, \ldots, X_{n+k}) para cierta función f, se obtiene una sucesión de variables con idéntica distribución pero no independientes. El teorema de Birkhoff garantizará la convergencia del promedio de estas variables.

Como última observación previa notamos que el siguiente enunciado es FALSO:

Lee el resto de esta entrada »

Distribuciones de Probabilidad Estables (un bosquejo)

In Probabilidad y Estadística on Jueves 12, marzo, 2009 at 2:56 pm

por Pablo Lessa

El teorema central del límite clásico dice:

Teorema Central del Limite.

Si X_1, \ldots, X_n, \ldots son variables aleatorias independientes e idénticamente distribuidas y tales que:

E(|X_n|) < +\infty

E(|X_n|^2) < +\infty

entonces definiendo

S_n = X_1 + \cdots + X_n

E(X_n) = \mu

E((X_n-\mu)^2) = \sigma^2

se tiene que  para todo a,b \in \mathbb{R} con a < b se tiene:

P(\frac{1}{\sqrt{n}\sigma}(S_n - n\mu) \in [a,b]) \to \frac{1}{\sqrt{2\pi}}\int_a^be^{-\frac{x^2}{2}}\mathrm{d}x

La hipótesis de que las variables sean de cuadrado integrable es escencial y tenemos el siguiente ejemplo:

Lee el resto de esta entrada »

No podés hacer guita en el casino (bajo ciertas hipotesis…)

In Probabilidad y Estadística on Miércoles 25, febrero, 2009 at 5:36 pm

por Pablo Lessa

Es obvio que se puede hacer guita en el casino. La mejor forma de hacerla es siendo dueño del mismo. La segunda mejor es jugar a un juego de azar en las que uno tiene las de ganar (por ejemplo si tenés buena memoria y concentración el blackjack puede ser un juego así) claro que en ese caso lo más probable es que te rajen.

También podés hacer guita si vas y jugás a un juego de azar en el que tenés las de perder, ponele jugas a la ruleta (supongamos que la ruleta está bien construida de manera de evitar la gran Jagger).

Lo que voy a intentar argumentar entonces es que, si jugás juegos de azar en las que tenés la de perder, utilizando alguna estrategia del estilo “si llego a tanta plata paro”.  Entonces en promedio vas a salir con menos plata de la que empezaste.

Lee el resto de esta entrada »