Los seguidores de Manolo

Archive for 24 junio 2015|Monthly archive page

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?

Leer el resto de esta entrada »