Los seguidores de Manolo

Notas de Caminatas al azar

In Uncategorized on Miércoles 24, junio, 2015 at 6:20 pm

por Pablo Lessa

Hace poco tuve la suerte de dar un cursito en una escuela para estudiantes de grado en la universidad Notre Dame (Indiana, EEUU).  Escribo este artículo para divulgar las notas (en inglés) que preparé para el curso que están disponibles acá.  Aprovecho también para dar una idea de que se trató el asunto.

Comenzamos con el Teorema de Pòlya que dice que una caminata al azar simple en \mathbb{Z}^2 es recurrente (i.e. con probabilidad 1 visitará cada vértice infinitas) mientras que en \mathbb{Z}^3 no lo es (con probabilidad 1 eventualmente escapa cualquier conjunto finito de vértices para nunca regresar).

Las caminatas al azar simples son el ejemplo más sencillo de proceso aleatorio en un grafo infinito.  Formalmente se define una caminata al azar simple como una sucesión de vértices al azar x_0,x_1,\ldots tales que x_{n+1} se construye a partir de x_n eligiendo un vecino al azar (todos los vecinos son equiprobables y todas las elecciones son independientes).  La idea es que es una trayectoria al azar “continua” pero sin memoria ni “inteligencia” (un borracho en un grafo básicamente).

La idea del curso fué discutir la pregunta más básica sobre caminatas al azar que es: ¿En cuáles grafos infinitos la caminata al azar simple es recurrente?

Hicimos esto enfocándonos en dos familias de ejemplos:  grafos de Cayley de grupos discretos, y árboles.

Los grafos de Cayley son ejemplos de grafos “homogéneos” en el sentido que son iguales en todos lados (formalmente diríamos que es posible enviar un vértice a cualquier otro con un isomorfismo del grafo).  Se definen como sigue:  el grafo de Cayley de un grupo discreto G respecto a un generador finito y simétrico F tiene como conjunto de vértices el conjunto G y una arista une dos vértices x,y \in G si y sólamente si x = yg para algún g \in F.

Una primer pregunta es: ¿La recurrencia de un grafo de Cayley es una propiedad del grupo o puede depender del generador finito simétrico elegido?

En las notas respondemos esta pregunta (de hecho la recurrencia es invariante por quasi-isometrías) y de hecho llegamos a clasificar los grafos de Cayley recurrentes como aquellos que tienen crecimiento de orden n^2 (que al final son o bien grupos finitos, grupos que son virtualmente \mathbb{Z}, o grupos que son virtualmente \mathbb{Z}^2).

En el curso nos limitamos a discutir varios ejemplos incluyendo el grafo de Cayley de \mathbb{Z}^d con los generadores estandard (base canónica y opuestos), el grupo libre en dos generados, el grupo modular (i.e. Möebius z \mapsto (az + b)/(cz+d) con a,b,c,d \in \mathbb{Z} y ad-bc=1) con respecto al generador z \mapsto z \pm 1, z \mapsto -1/z, el grupo de Heisenberg (matrices 3\times 3 triangulares superiores con entradas enteras y elementos diagonales iguales a 1), el grupo de empapelado *632 generado por simetrías axiales respecto a 12 ejes relacionados con un hexágono regular en el plano, y un grupo muy interesante llamado el “Lamplighter group” sobre \mathbb{Z}.

En varios de estos ejemplos no es trivial analizar la recurrencia de la caminata “a mano”.  Por ejemplo una caminata en el “Lamplighter group” sobre \mathbb{Z} se puede imaginar como sigue:  Suponete que hay un tipo parado en un vértice en \mathbb{Z} y que en cada entero hay una lámpara que está inicialmente apagada.  El tipo en cada turno elige entre tres movimientos que son o cambiar el estado de la lámpara en la que está, o moverse a la derecha un lugar, o moverse a la izquierda un lugar.  El teorema de Pólya muestra que el tipo va a volver al origen infinitas veces.  La pregunta es:  ¿Volverá infinitas veces a estar parado en el origen y con todas las lámparas apagadas?

Los árboles son una familia bastante amplia de grafos que también es relativamente analizable.  Un ejemplo básico y bastante interesante son los árboles “radialmente simétricos” que se consiguen a través de una sucesión de naturales a_0,a_1,\ldots como sigue:  Hay una raiz con a_0 “hijos, cada uno de los cuales tiene a_1 hijos, cada uno de los cuales tiene a_2 hijos, etc.  ¿Para qué sucesiones a_n el árbol resultante es recurrente?

Terminamos demostrando en el curso que un árbol radialmente simétrico es recurrente si y sólamente si se cumple:

\sum\limits_{n = 0}^{+\infty}\frac{1}{a_0a_1\cdots a_n} = +\infty.

En las notas mostramos que la recurrencia de cualquier árbol es una propriedad métrica del borde (en el sentido de Gromov).  Por ejemplo si el borde tiene dimensión de Hausdorff positiva entonces el árbol no es recurrente.  El criterio exácto para la recurrencia que el borde tenga capacidad logaritmica nula.

En fin, creo que el tema de las caminatas al azar es bastante rico y está relacionado con muchas otras áreas (geométrica, análisis armónico, y hasta dinámica si consideramos los exponentes de Lyapunov de caminatas en grupos de matrices).   Hay muchos aspectos que obviamente quedaron sin cubrir en ese mini curso y estas notas.  En particular tengo ideas de una segunda parte cuya temática sería, dentro de los grafos no recurrentes, discutir “velocidad de escape” y su relación con funciones armónicas y desigualdades isoperimétricas.   Quizás ese eventual curso y sus notas sean en español🙂.  ¡Salute!

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: