Martin Gardner Circo Matemático
Capítulo 7
Paseos aleatorios por el plano y el espacio
Ya hemos examinado en el capítulo anterior las caminatas aleatorias compuestas de pasos
discretos a lo largo de una recta, con o sin barreras absorbentes, e hicimos notar su curiosa
equivalencia con varios juegos de apuestas bi-personales. En este capítulo, el paseo
aleatorio nos llevará por el plano y el espacio.
En un tipo de paseo aleatorio que ha sido muy estudiado, a cada paso el andarín va de un
vértice de un retículo cuadriculado infinito a otro vértice contiguo, como vemos en la Figura
37.
Figura 37. Paseo aleatorio sobre una red cuadrada
Cada paso tiene longitud unidad, y el paseo es «simétrico» en el sentido de que puede
tornarse cada una de las cuatro direcciones con la misma probabilidad, es decir, con
probabilidad 1/4. Podemos hacer que la caminata sea finita rodeando al paseante de
barreras absorbentes, que en la figura han sido representadas por puntos negros gruesos.
Cuando el paseante pisa una de estas «trampas» queda «absorbido» y su paseo concluye.
(No es menester que el cercado sea un cuadrado perfecto ni que tenga forma regular; la
barrera fronteriza puede tener forma cualquiera.) Lo mismo que en el caso homólogo
unidimensional, no es difícil calcular la probabilidad de que un paseo iniciado en un punto
arbitrario de la región delimitada finalice en una determinada barrera. También podemos
determinar el número esperado de pasos (número promedio de pasos correspondiente a una
serie de paseos indefinidamente repetidos) que durará la caminata hasta su fin. Las
fórmulas resultantes de tales cálculos tienen aplicaciones científicas tan numerosas como
1 Preparado por Patricio Barros
Martin Gardner Circo Matemático
inesperadas, como es la determinación de potenciales en puntos interiores de redes
eléctricas, por ejemplo.
Cuando el paseante no está encerrado entre barreras, sino que puede escapar y
vagabundear sin restricciones sobre una red cuadrada que se extiende por todo el plano, la
situación se complica mucho y plantea problemas todavía no resueltos. Algunos de los
teoremas ya demostrados son tan profundos como paradójicos. Veamos qué sucede en un
paseo aleatorio sobre un retículo plano infinito, sin barreras. Si la duración del paseo es
suficientemente larga, es seguro que el paseante visitará todo vértice del retículo, incluido el
punto de partida. Por otra parte, si el paseo prosigue un tiempo arbitrariamente largo, la
proporción de veces que el paseante visita un vértice determinado tiende a cero. Estas
nociones sirven muy bien para presentar la diferencia radical entre los conceptos de
posibilidad lógica y posibilidad práctica, y así lo hace ver John G. Kemeny en un excelente
artículo de divulgación titulado «Random Walks» [Paseos aleatorios], en Enrichment
Mathematics for Hígh School. Desde el punto de vista lógico, existe la posibilidad lógica de
que el caminante pueda estar paseándose eternamente sin pasar por un determinado
vértice. Para el estadístico, empero, la probabilidad práctica, la plausibilidad, es nula, a
pesar de que el número esperado de pasos para alcanzar un vértice prefijado cualquiera sea
infinito. Es frecuente tropezarse con situaciones de este tipo al manejar conjuntos infinitos.
Por ejemplo, si lanzamos indefinidamente una moneda, existe la posibilidad lógica de que las
caras y las cruces se alternen hasta el infinito; más la probabilidad práctica de tal suceso es
nula.
Así lo expresa Kemeny: si estamos parados en uno de los cruces del retículo infinito,
mientras un amigo nuestro, partiendo de otro cruce cualquiera, se dedica a vagar sin rumbo
por la red de calles, podríamos tener la certeza práctica de acabar reuniéndonos con él,
siempre y cuando estemos dispuestos a esperar tanto como haga falta. Podríamos dar un
enunciado aún más fuerte. Una vez producido el primer encuentro sigue existiendo
probabilidad de que si nuestro amigo prosigue su errático paseo por el retículo, volvamos a
encontrárnoslo. Dicho de otra forma, es prácticamente seguro que si un andarín así se
tomase todo el tiempo del mundo, acabaría visitando cada cruce una infinidad de veces.
Supongamos ahora que dos paseantes vagabundean al azar por un retículo cuadriculado
infinito. ¿Es seguro que lleguen a encontrarse? (Si al comenzar están separados un número
impar de pasos y van moviéndose sincrónicamente, nunca podrán reunirse en una esquina,
pero sí chocar a medio camino de una de las calles.) Como antes, la respuesta es que si
pasean lo suficiente, es seguro que se reunirán tantas veces como deseen. Si tres personas
caminan al unísono, vagando por el retículo infinito, y sus posiciones iniciales distan
2 Preparado por Patricio Barros
Martin Gardner Circo Matemático
números pares de pasos, es seguro que los tres terminarán por reunirse en algún vértice.
Sin embargo, la probabilidad de triple encuentro en un vértice prefijado es ahora menor que
1. Y para cuatro o más paseantes, también cae por debajo de 1 la probabilidad de que se
produzca la reunión simultánea en alguno de los puntos del plano.
Aún recibimos sorpresas mayores al estudiar generalizaciones a espacios de dimensión
mayor. En un retículo tridimensional (cúbico o no) finito, es prácticamente seguro que un
paseante que vaya recorriéndolo al azar llegará a cualquier intersección en un tiempo finito.
Como dice Kemeny, si nos encontramos dentro de un gran edificio cuya red interior de
pasillos y escaleras es muy complicada, podemos estar seguros de que, aun recorriéndolo a
la ventura, más pronto o más tarde daremos con una salida. En cambio, cuando el retículo
sea infinito no sucederá así. George Polya demostró, allá por 1921, que la probabilidad de
que en una red tridimensional la caminata aleatoria pase por un vértice prefijado es menor
que 1, aunque el paseo se prolongue toda la eternidad. En 1940, W. H. McCrea y F. J. H.
Whipple demostraron que la probabilidad de que el andarín retorne al origen de su caminata
es de sólo 0,35 (aproximadamente), aunque el paseo se prolongue indefinidamente.
Si en lugar de recorrer retículos planos recorremos el propio plano, desplazándonos siempre
con un paso de longitud unidad en dirección elegida al azar, la situación se complica en
ciertos aspectos, y se simplifica en otros. Por ejemplo, la distancia esperada (la distancia
media) que separa al caminante del origen de su caminata tras n pasos de igual longitud, es
sencillamente el producto de la longitud del paso por la raíz cuadrada de n. Así lo demostró
Albert Einstein en un trabajo sobre estadística molecular publicado en 1905, el mismo año
en que dio a conocer su famoso artículo sobre relatividad. (Idéntico resultado fue obtenido,
independientemente, por Marian Smoluchowski. Los lectores podrán ver una demostración
sencilla en One, Two, Three,... Infinity, de George Garnow; hay traducción española: «Uno,
dos tres, ... infinito», Espasa, Calpe. Madrid.)
Los paseos aleatorios discretos a través del espacio obedecen a la misma ley cuadrática
anterior. Por otra parte, ni en el espacio ni en el plano es necesario que los pasos sean todos
de la misma longitud. Tras n pasos, la distancia esperada al origen es el producto de la
longitud media de los pasos por la raíz cuadrada de n, y por este motivo, los paseos
aleatorios resultan de incalculable importancia en el estudio de los procesos de difusión, los
movimientos aleatorios de las moléculas de líquidos y gases, la difusión de calor a través de
los metales, la propalación de rumores, el contagio de enfermedades, y otros muchos. La
evolución de una epidemia gripal es la resultante de muchos millones de paseos aleatorios
realizados por sus gérmenes. Podernos hallar aplicaciones en casi todas las ciencias. La
primera aplicación importante del método de Monte Carlo (uno de los procedimientos para
3 Preparado por Patricio Barros
Martin Gardner Circo Matemático
utilizar los ordenadores con el fin de simular difíciles problemas probabilísticos) consistió en
calcular datos sobre paseos aleatorios de neutrones en el seno de diferentes substancias. En
fenómenos de difusión como éstos, lo mismo que en el movimiento browniano, es preciso
modificar la sencilla ley cuadrática comentada, y tener en cuenta otros muchos factores,
como temperatura, viscosidad del medio, etc. Además, tales movimientos son, por lo
común, continuos y no discretos, por lo cual se los llama «procesos de Markov», para
distinguirlos de las cadenas de Markov. La ley cuadrática da tan sólo una primera
aproximación de las distancias medias esperadas. (Si se desean más datos sobre trabajos
recientes en este campo, comenzando por el brillante primer artículo que Norbert Wiener
dedicó al movimiento browniano en 1920, véase Brownian Motion and Potential Theory, por
Reuben Hersh y Richard J. Griego, en Scientific American, marzo de 1969.)
En un paseo aleatorio un caminante que salga del origen va derivando hacia distancias cada
vez mayores, pero no con ritmo constante. Si la caminata se realiza con paso regular, la raíz
cuadrada del número de pasos (distancia esperada al origen) va creciendo, pero su tasa de
crecimiento es cada vez menor. Cuanto más largo sea el paseo, tanto más lentamente crece
la deriva. En el libro ya citado, Gamow da un ejemplo espectacular. Un cuanto de luz
cercano al centro del Sol tarda alrededor de 50 siglos en emerger a la superficie, pues su
trayectoria en el interior del astro es tan errática como la de un borracho. Pero una vez
liberado del Sol, el fotón llegará en tan solo ocho minutos a la superficie terrestre, si toma la
dirección adecuada.
He aquí una cuestión sencilla. Dos caminantes parten de un mismo punto del plano. Uno
realiza un paseo aleatorio de 70 pasos de longitud unidad y luego se detiene. El otro se para
después de sólo 30 pasos. ¿Qué distancia podemos esperar que los separe al terminar?
Figura 38. “Caminata ergódica” por un cuadrado (a la izquierda) y matriz estocástica de sus
probabilidades de transición (derecha)
4 Preparado por Patricio Barros
Martin Gardner Circo Matemático
Nos fijaremos ahora en un tipo de paseo totalmente diferente de los comentados ya.
Imaginemos un insecto que parte del vértice A del cuadrado que vemos a la izquierda de la
Figura 38, y va caminando al azar a lo largo de los lados. En lugar de suponer iguales las
«probabilidades de transición» de vértice a vértice, como hemos venido haciendo,
supongamos que en los vértices B y C la probabilidad de que el insecto se dirija hacia D sea
doble de la probabilidad de que regrese a A. Cuando está situado en A o en D, el bichito ha
de elegir entre dos caminos, cada uno con probabilidad 1/2, mientras que en B y C tomará
el camino hacia D con probabilidad 2/3 y el retorno a A con probabilidad 1/3. Aunque la
malla es finita, como no hay barreras absorbentes, el paseo no concluye jamás. Las
caminatas de este tipo acostumbran a llamarse «paseos ergódicos». Deseamos calcular la
proporción de veces que con respecto al total el insecto visitará cada uno de los vértices.
Uno de los procedimientos para lograrlo es formar la matriz «estocástica» que se muestra a
la derecha de la ilustración, donde se dan las probabilidades de transición de unos vértices a
otros. Los ceros de la matriz indican transiciones imposibles, Puesto que cada estado de la
cadena de Markov ergódica ha de conducir a otro, la suma de las probabilidades de cada
fila-filas que suelen llamarse «vectores probabilísticos», tiene que ser igual a 1.
La probabilidad de que el bichito visite un vértice dado es la suma de las probabilidades de
que lo visite, cuando se encuentra en cada uno de los vértices adyacentes.
Por ejemplo, la probabilidad de que se encuentre en D es la suma de la probabilidad de que
vaya a D desde B más la probabilidad de que vaya a D desde C. (Atención, estas
probabilidades son «a largo plazo»; no son las probabilidades de que el insecto se dirija a D
cuando echa a andar en B o en C.) Sea d la probabilidad de que el insecto se encuentre en el
vértice D, sabiendo que en ese instante se encuentra en un vértice cualquiera, y sean a, b, y
c las probabilidades correspondientes a los vértices A, B, y C. Mirando la columna D de la
matriz de transición, vernos que la probabilidad de que «a la larga» el insecto se dirija de B
a D es b(2/3), y desde C a D, c(2/3). La probabilidad a largo plazo de que el bicho se
encuentre en D es por tanto la suma de estas dos probabilidades, y podemos así plantear la
ecuación:
d = b(2/3) + c(2/3),
o escrita en forma habitual,
d = 2b/3 + 2c/3.
Las otras tres columnas de la matriz nos dan otras tantas ecuaciones para a, b y c:
5 Preparado por Patricio Barros
Martin Gardner Circo Matemático
a = b/3 + c/3
b = a/2 + d/2
c = a/2 + d/2
Cuando el insecto no se encuentre caminando por uno de los lados, seguro que se
encontrará en un vértice, y así
a+b+e+d=1
Basta una ojeada a este sistema de ecuaciones para observar que b = c y que d = 2a; ahora
es fácil resolverlo hasta el final: a = 1/6, b 1/4, c = 1/4, d = 1/3. El insecto pasará la sexta
parte del tiempo que descanse en los vértices en el vértice A, 1/4 de ese tiempo en B, 1/4
en C, y 1/3 en D. Su estadía en D será doble de la pasada en A.
Sin duda los lectores encontrarán entretenido ensayar la misma técnica en el problema
análogo sobre un cubo, que Kemeny propone en el artículo ya mencionado.
Figura 39. Caminata aleatoria ergódica sobre las aristas de un cubo(izquierda) y la matriz
de sus probabilidades de transición (a la derecha)
En el cubo que vemos en la parte izquierda de la Figura 39, la probabilidad de que el insecto
se dirija hacia H es doble de la de que se mueva en dirección a A. La matriz estocástica de
probabilidades de transición puede verse a la derecha del cubo. El sistema de ecuaciones
correspondientes a las ocho columnas, juntamente con la ecuación
6 Preparado por Patricio Barros
Martin Gardner Circo Matemático
a+b+e+d+e+f+g+h=1
tiene solución única. Al realizar su caminata ergódica perpetua, 3/54 de sus visitas a vértices
serán a A, 5/54 a cada uno de los vértices B, C, D, 8/54 a cada uno de los vértices E, F, G, y
12/54 a H. Así que visitará el vértice H con frecuencia cuatro veces mayor que el A.
Cuando un paseo ergódico de este tipo es simétrico, en el sentido de que en cada vértice
cada uno de los posibles pasos siguientes tienen la misma probabilidad, la fracción de visitas
dedicadas a cada par de vértices dados cualesquiera es proporcional al número de paseos
distintos que llevan a estos dos vértices. Por ejemplo, un gato que realizase una caminata
ergódica simétrica por los vértices de la Gran Pirámide de Egipto, visitaría la cúspide cuatro
veces por cada tres que pasara por cada uno de los vértices de la base, pues a la cúspide se
puede llegar por cuatro caminos, mientras a los vértices de la base sólo se llega por tres. Es
fácil escribir la matriz de transición y dar las ecuaciones, que muestran que a largo plazo el
gato dedica a la cúspide 1/4 de las visitas que hace a los vértices, y 3/16 a cada uno de los
vértices de la base.
He aquí otro problema fácil. Supongamos que en el cubo de la Figura 39, y con la misma
matriz estocástica, una mosca comience un paseo aleatorio en A. Al mismo tiempo, una
araña comienza en H otro paseo aleatorio. Ambas, mosca y araña, se mueven
sincrónicamente y a la misma velocidad. ¿Cuál es la probabilidad de que se tropiecen a
mitad de una arista, tras haber recorrido como mínimo una arista y media?
Hay otros muchos entretenidos problemas relacionados con paseos ergódicos aleatorios a lo
largo de las aristas de cubos u otros poliedros regulares. Si un insecto beodo parte de un
vértice de un cubo y camina hasta el vértice más alejado, optando en cada vértice con igual
probabilidad por uno de los tres posibles caminos, su paseo tendrá, en promedio, una
longitud de 10 aristas. Si el insecto sólo está «semibeodo», en el sentido de que nunca
retornará por uno de los lados recién recorridos, sino que optará con igual probabilidad por
uno de los otros dos, su caminata desde un vértice al diagonalmente opuesto tendrá, en
promedio, 6 lados. En ambos casos, el paseo promedio con retorno al punto de partida tiene
8 aristas, igual al número de vértices del cubo.
Y no es por casualidad. Thomas O'Beirne, de Glasgow, a quien debo el término
«semibeodo», ha demostrado (aunque no publicado) que en toda red regular donde cada
vértice sea topológicamente equivalente a cada uno de los demás, los paseos aleatorios con
retorno al punto de partida tienen por término medio el mismo número de pasos que
vértices tenga en total la red. Tal afirmación es válida tanto si el andarín elige en cada nudo
entre todos los caminos posibles con igual probabilidad, o sólo entre aquellos que excluyen
7 Preparado por Patricio Barros
Martin Gardner Circo Matemático
el que acaba de recorrer. Es decir, tanto si el insecto está completamente beodo como si
sólo esta medio «colocado», para ir paso a paso desde un vértice del cuadrado hasta
retornar al mismo necesitará por término medio cuatro pasos. Las aristas de todos los
poliedros platónicos y arquimedianos forman redes espaciales de este mismo tipo. Sobre un
tetraedro un insecto beodo o semibeodo recorrerá en promedio cuatro aristas antes de
retornar al vértice de partida; en un dodecaedro pasará por 20 aristas, etc. Los lectores
interesados en métodos para plantear las ecuaciones que permiten calcular paseos
promedios sobre redes de esta naturaleza encontrarán explicado el procedimiento,
particularizado al dodecaedro, en las soluciones de los problemas E 1752 y E 1897 en The
American Mathematical Monthly, febrero de 1966, p. 200, y octubre de 1967, pp. 1.008-10.
Para el rombo-dodecaedro, que no es regular, véase el artículo de O'Beirne, «A Nonsense
Result in the Traffic Statistics of Drunk Flies», en el «Bulletin of the Institute of Mathematics
and Its Applications» agosto de 1966, pp. 116-19.
No es menester que en cada paso haya de saltarse a un vértice adyacente de la red.
Fijémonos en el paseo simétrico y ergódico de una torre en el tablero de ajedrez. Se supone
que en cada jugada la torre elige entre los movimientos lícitos con igual probabilidad. Como
cada escaque es accesible desde otros catorce, la probabilidad de transición de cada jugada
es 1/14. Por consiguiente, la torre pasará en todas las casillas tiempos iguales.
Para otras piezas la situación es diferente, porque las probabilidades de transición no son
idénticas. Los caballos, por ejemplo, sólo pueden alcanzar los ángulos del tablero desde dos
casillas, mientras que cada uno de los 16 cuadros centrales es atacable desde otros ocho.
Puesto que la proporción es ahora de 2/8 o sea, 1/4, se sigue que durante un paseo
aleatorio sin fin el caballo visitará un vértice determinado con frecuencia cuatro veces menor
que un cuadro determinado elegido entre los 16 centrales. Puede verse una demostración en
«Generalized Symmetric Random Walks», por Eugene Albert, en Scripta Mathematica,
agosto de 1964, pp. 185-87.
Complementos
En este capítulo hemos encontrado ya un precioso teorema, que con terminología de la
teoría de grafos podemos enunciar así: tomemos un grafo regular arbitrario, es decir, un
grafo donde cada nudo es origen de igual número de líneas. Si un insecto parte de un nudo
cualquiera y realiza un paseo aleatorio, optando en cada nudo por una de las líneas, todas
elegibles con igual probabilidad, el número esperado de pasos (número promedio) para
retornar al nudo de partida es igual al número de nudos del grafo.
8 Preparado por Patricio Barros
Martin Gardner Circo Matemático
Aunque di algunas referencias donde se explica cómo calcular tales caminatas, no puse
ningún ejemplo. Puede ser interesante ver cómo se haría en triángulos y tetraedros; los
lectores podrían entonces generalizar el procedimiento a lados de polígonos y aristas de
poliedros así como a otros grafos regulares.
Sean A, B, C los vértices de un triángulo. Deseamos conocer la longitud esperada de un
paseo aleatorio que partiendo de A retorne hasta A, suponiendo que en cada vértice se elija
entre los dos lados con igual probabilidad.
Observemos que ello equivaldría a declarar que A es barrera absorbente (una vez dado el
primer paso) y pedir entonces la longitud esperada del paseo aleatorio hasta que el bichito
sea absorbido.
Sea x la longitud esperada de un paseo desde B hasta A. Por razones de simetría, esta
longitud es igual a la del paseo desde C hasta A.
Supongamos que el bicho se encuentra en B. Si opta por dirigirse directamente a A, el
camino esperado tiene longitud 1. Si opta por dirigirse a C, la longitud del camino esperado
será 1 más la longitud esperada del camino desde C hasta A. Como esta última es x, la
longitud esperada del camino que va desde B hasta A pasando por C es (1 + x). Se suman
las longitudes de los dos caminos, y se divide por 2 (pues el insecto elige uno de los dos con
probabilidad 1/2), con lo cual obtendremos su promedio. Resulta la sencilla ecuación:
de donde x = 2.
Sabemos ahora que si el insecto sale de B o de C, la longitud esperada del camino hasta A
es 2. Sin embargo, si el insecto partiera de A, tendría que dar primero un paso para llegar a
B o a C, y luego retornar desde allí. Por consiguiente, la longitud esperada del circuito de ida
y vuelta desde A es 1 + 2 = 3.
El problema se resuelve igual sobre el tetraedro. Sean A, B, C, D sus vértices. El insecto sale
de B. Si decidiera ir directamente hasta A su viaje tendría longitud 1. Si optase por dirigirse
a C o D, la longitud esperada del viaje a A es (1 + x). Por consiguiente, la caminata
promedio desde B hasta A, es 1 + (1 + x) + (1 + x) dividido entre 3. Nuestra ecuación es
ahora:
9 Preparado por Patricio Barros
Martin Gardner Circo Matemático
de donde resulta que x tiene que ser 3. El insecto situado en A tiene primero que dar un
paso para llegar a uno de los tres vértices; por consiguiente, el camino esperado desde A
hasta retornar a A es 1 + 3 = 4.
Como ejercicio, el lector podría entretenerse en demostrar que en un cuadrado o un cubo la
longitud esperada de los paseos que parten de un vértice y retornan a él es,
respectivamente, de 4 y 8. Lo único que sucede es que las ecuaciones son algo más
complicadas.
Soluciones
1. Dos personas salen del mismo punto del plano. Una realiza una caminata aleatoria de
70 pasos, todos de longitud unidad; la otra, un paseo de 30. ¿Cuál es la distancia
esperada (promedio) que los separará al terminar? La cuestión equivale a
preguntarse cuál será la distancia esperada al origen de un andarín que diese una
caminata de 100 pasos; para verlo basta imaginar que uno de ellos desanda su
paseo, retornando al origen, y luego prosigue siguiendo las huellas del otro. Ya
sabemos que tal distancia esperada es la raíz cuadrada del número de pasos. La
respuesta, por tanto, es 10 unidades.
2. A causa de la simetría del cubo, cualquiera que sea el primer paso que dé la mosca
borracha, es seguro que la acercará al vértice diagonalmente opuesto, desde donde
la araña ha comenzado simultáneamente su caminata. Por consiguiente, nada
importa cuál sea el primer paso de la mosca. Sin embargo, de los tres pasos
equiprobables de la araña sólo dos la conducen a vértices adyacentes a la mosca. Por
consiguiente, la probabilidad de que tras dar cada una su primer paso estén situadas,
mosca y araña, en vértices contiguos es de 2/3. Para cada par de posibles vértices
contiguos que puedan ocupar, la probabilidad de que la mosca se mueva hacia la
araña es 2/5, y la probabilidad de que la araña vaya hacia la mosca, 1/4. El producto
de estas tres probabilidades, 2/3, 2/5 y 1/4, es 1/15. Esta será la probabilidad de
que mosca y araña se tropiecen a media arista, tras viajar cada una 1 1/2 lados.
10 Preparado por Patricio Barros