Camí aleatori

Eixemple de huit camins aleatoris en una dimensió escomençant en 0. La gràfica mostra la posició actual sobre una llínea (eix vertical) versus els intervals de temps (eix horisontal).

Archiu:2D Random Walk 400x400.ogv

Un eixemple animat d'un moviment browniano-com a camí aleatori en un bou

La caminada aleatòria o passejada aleatòria o camí aleatori, abreviat en anglés com RW (Random Walks), és una formalisació matemàtica de la trayectòria que resulta de fer successius passos aleatoris. Per eixemple, la ruta traçada per una molècula mentres viaja per un líquit o un gas, el camí que seguix un animal en la seua busca de menjar, el preu d'una acció fluctuante i la situació financera d'un jugador poden tractar-se com una caminada aleatòria. El terme caminada aleatòria va ser introduït per Karl Pearson en 1905.^[1] Els resultats de l'estudi de les caminades aleatòries han segut aplicats a molts camps com la computació, la física, la química, l'ecologia, la biologia, la psicologia o l'economia.^[2]^[3]^[4]^[5]^[6]^[7]^[8]^[9] En particular en este últim camp la teoria de la passejada aleatòria de Burton G. Malkiel en la seua obra Una passejada aleatòria per Wall Street es fonamenta en l'hipòtesis dels mercats eficients, desenrollat en tres formes o hipòtesis. En física el model ha servit, per eixemple, per a modelar el camí seguit per una molècula que viaja a través d'un líquit o un gas (moviment browniano). En ecologia, s'ampra per a modelar els moviments d'un animal de pastoreig, etc. Varis tipos diferents de camins aleatoris són d'interés. A sovint, els camins aleatoris se suponen que són cadenes de Márkov o procés de Márkov, pero atres camins més complicats també són d'interés. Alguns camins aleatoris es donen en grafos finitos, uns atres en la recta, en el pla, o en dimensions majors, mentres alguns camins aleatoris es donen en grups.

En la seua forma més general, les caminades aleatòries són qualsevol procés aleatori a on la posició d'una partícula en cert instant depén solament de la seua posició en algun instant previ i alguna variable aleatòria que determina la seua subsecuente direcció i la llongitut de pas. Els camins aleatoris també varien sobre el temps. Casos específics o llímits d'estos inclouen la caminada d'un borracho, el vol de Lévy i el moviment browniano. Les passejades aleatòries estan relacionats en els models de difusió i són un tema fonamental en la discussió dels processos de Márkov. Vàries propietats de les passejades aleatòries inclouen distribucions disperses, temps de primer creuament i rutes de trobada.

Definició

Digam que $X (t)$ definix una trayectòria que escomença en la posició $X (0) = X_{0}$ . Una passejada aleatòria es modela per mig de la següent expressió:

a on $Φ$ és la variable aleatòria que descriu la llei de provabilitat per a prendre el següent pas i $τ$ és l'interval de temps entre passos subsecuentes. A mida que la llongitut i direcció d'un pas donat depén solament de la posició $X (t)$ i no d'alguna posició prèvia, es diu que la passejada aleatòria posseïx la Propietat de Márkov. Comunament la distribució del pas serà independent de la posició o del temps transcorregut, una propietat anomenada homogeneïtat. De qualsevol modo, la formulació és extremadament general. Les passejades aleatòries poden ocórrer en qualsevol número de dimensions, ser parcials o imparcials, discrets o continus en el temps i/o espai, i poden violar l'homogeneïtat en algun número de formes.

Caminades aleatòries en grafos

En l'estudi de la teoria general de les caminades aleatòries, apareix en prou freqüència que l'espai a on es requerix realisar la caminada, pot ser modelat com a cert grafo. La situació usual és com seguix: Donat un grafo $G$ i començant en un dels seus vèrtiços, seleccionem d'alguna manera a l'encert un dels seus veïns i nos movem a est; llavors nosatres seleccionem un veí d'este últim vèrtiç i nos movem de nou, etc. La successió aleatòria de vèrtiços obtinguts d'esta forma és una caminada aleatòria sobre el grafo $G$ . La teoria relacionada en caminades aleatòries es desenrolla en el marc general de la teoria dels processos estocàstics, més exactament en la relacionada en les cadenes de Márkov, i no solament això; no hi ha molta diferència entre la teoria de les caminades aleatòries en grafos i la teoria de les cadenes de Márkov finitas ya que cada cadena de Márkov d'estes, pot ser vista com una caminada aleatòria sobre cert grafo dirigit. De manera similar, les cadenes de Márkov reversibles poden ser vistes com a caminades aleatòries en grafos no dirigits, i les cadenes de Márkov simètriques, com a caminades aleatòries en grafos regulars.

Caminades aleatòries en grafos sorgixen en molts models en matemàtiques i en física. De fet, esta és una d'eixes nocions que escomencen a aparéixer en tots els llocs una volta s'escomença a buscar-les. Per eixemple, considere la disposició d'una baralla de cartes, construïxca un grafo els vèrtiços del qual siguen totes les permutació de les cartes de la baralla de tal manera que dos permutació són adjacents si i solament si una s'obté a partir de l'atra canviant la posició de dos de les cartes. Barallar el mall de cartes, correspon a una caminada aleatòria en este grafo.^[10]

Recentment caminades aleatòries en grafos més generals, encara que finitos, han rebut major atenció, i els aspectes estudiats són més quantitatius: quànt es deu caminar fins a aplegar a la posició inicial, fins a aplegar a un vèrtiç donat o fins a passar per tots els vèrtiços del grafo. Les caminades aleatòries també estan relacionades en atres branques de la teoria de grafos; propietats bàsiques de les caminades aleatòries són determinades pel espectre del grafo i també per la resistència elèctrica de la ret associada de manera natural en est; és per açò que gran part de la terminologia corresponent a tals caminades es dona en térmens de la teoria de rets elèctriques lo que resulta ser prou útil ya que és possible extrapolar resultats de tal teoria a la de caminades aleatòries en grafos i viceversa. Totes eixes conexions són fructíferes i donen tant ferramentes per a l'estudi com a oportunitats per a trobar noves aplicacions.

Definició

Siga $G = (V, E)$ un grafo dirigit en components conexas no trivials i $E \subset V^{2}$ un conjunt d'arestes tal que $(x, y) \in E ⟺ (y, x) \in E$ en la condició adicional de que no té bucles, és dir $(x, x) \in̸ E$ . Siga $N (x) = {y \in V : (x, y) \in E}$ el conjunt de veïns de $x \in V$ i $d (x) = | N (x) |$ el seu grau.

Una funció $c : V^{2} \mapsto ℝ$ simètrica en el sentit de $c (x, y) = c (y, x)$ i a on $c (x, y) > 0$ si $(x, y) \in E$ i $c (x, y) = 0$ en cas contrari serà cridada una conductància. Tal com la terminologia sugerix, es pot imaginar un electró viajant pel grafo a on este junt a la funció $c$ modelarien una ret elèctrica a on els vèrtiços són els seus nodos i les arestes tenen una conductància elèctrica donada per $c$ . Siga $C (x) = \sum_{y \in V} c (x, y)$ i si suponem $c (x) < \infty$ per a cada $x \in V$ . La cadena de Márkov $X = (X_{n})_{n \in ℕ}$ en espai d'estats $V$ i matriu de transició $P$ donada per:

π_{x y} : = P (X_{n + 1} = y | X_{n} = x) = \frac{c (x, y)}{C (x)}, (x, y) \in V^{2}

És cridada caminada aleatòria en $G$ . Esta cadena descriu el moviment aleatori d'una partícula a lo llarc dels vèrtiços de $G$ . Si la partícula està en un vèrtiç $x \in V$ en un moment donat, llavors la partícula estarà en un veí de $x$ en el següent moment, a on el veí serà triat aleatoriamente d'acort a la conductància. En el cas d'una ret elèctrica la partícula seria més precisament un electró. Note que en multiplicar la conductància $c$ per una constant positiva, no hi ha canvi en la caminada aleatòria associada.

Caminada aleatòria simètrica

Suponent que cada aresta té la mateixa conductància, açò és que cada vèrtiç té grau finito. Llavors

$C (x) = c \cdot d (x) para cada x \in V$
La matriu de transició està donada per:

Una cadena com la descrita anteriorment, en la qual si la partícula es troba en un vèrtiç $x$ té la mateixa provabilitat de moure's a cada veí de $x$ , és cridada caminada aleatòria simètrica en $G$ .

Caminades aleatòries en cuadrículas

Les caminades aleatòries sobre les cuadrículas $ℤ^{k}$ en $k \in ℕ^{+}$ són particularment interessants. Considere primer la caminada aleatòria simple $X = (X_{n})_{n \in ℕ}$ sobre $ℤ$ en provabilitats de transició:

a on $p \in (0, 1)$ és un paràmetro. Note que la cadena aixina definida resulta irreducible. Ademés la cadena és periòdica de periodo 2 (ya que la cadena és irreducible és suficient revisar si el periodo de 0 és 2):^[11] Com en escomençar en el vèrtiç 0 la cadena solament pot aplegar de nou a 0 en una cantitat parell de passos i la cadena retorna a 0 en el temps $2 n$ si i solament si hi ha $n$ passos a la dreta i n passos a l'esquerra llavors

π_{00}^{(2 n)} = (\binom{2 n}{n}) p^{n} (1 - p)^{n} y π_{00}^{(2 n - 1)} = 0 para todo n \geq 1

D'açò s'obté usant la Fòrmula de Stirling $π_{00}^{(2 n)} \approx \frac{1}{\sqrt{π n}} (4 p (1 - p))^{n}$ i aixina $π_{00}^{*} = \sum_{n = 0}^{\infty} π_{00}^{(2 n)} < \infty$ si $p \neq 1 / 2$ o lo que és lo mateix 0 és transitori i en ser la cadena irreducible , resulta ser $X$ transitòria. Pel contrari si $p = 1 / 2$ , $π_{00}^{*} = \sum_{n = 0}^{\infty} π_{00}^{(2 n)} = \infty$ i 0 és recurrent, aixina com la cadena $X$ .^[11] D'esta manera, per al cas $p = 1 / 2$ en el que $X$ és la caminada simètrica en $ℤ$ , una partícula que partixca de qualsevol vèrtiç en algun moment retornarà a est.

Supongam que tracem una marca a certa distància de l'orige de la passejada. ¿Quantes voltes creuarà la passejada aleatòria tal marca? La solució és la següent teorema (que estén lo anterior): per a qualsevol passejada aleatòria unidimensional, cada punt del domini de definició d'una funció serà casi segurament creuat un número infinit de voltes. (En dos dimensions el resultat anàlec diu que qualsevol llínea serà creuada un número infinit de voltes). Este problema té diversos noms: el problema de creuament de nivells, el problema de recurrencia o el problema de la ruïna del apostador. L'orige d'este últim nom és el següent: si un jugador en una cantitat finita de diners juga a un joc no biaixat contra una banca en infinits diners, sempre termina perdent. La cantitat de diners del jugador efectuarà una passejada aleatòria segons vaja guanyant o perdent, i sempre, en algun moment, alcançarà el 0 i el joc terminarà.

Erro al crear miniatura:

Passejada aleatòria en dos dimensions.

En el cas general considere $ℤ^{k}$ en $k \in ℕ^{+}$ . Per a $i \in {1, 2, \dots, k}$ siga $e_{i} \in ℤ^{k}$ el vector unitari en un 1 en la posició $i$ i 0 en totes les demés. La caminada aleatori simple en $ℤ^{k}$ té provabilitats de transició:

π_{x, x + e_{i}} = p_{i}, π_{x, x - e_{i}} = q_{i}; x \in ℤ^{k}, i \in {1, 2, \dots, k}

a on $p_{i} > 0$ , $q_{i} > 0$ per a cada $i$ i $\sum_{i = 1}^{k} (p_{i} + q_{i}) = 1$ . Clarament quan $k$ és gran és menys provable que partint d'un vèrtiç es puga aplegar novament a ell. Aixina i tot, el comportament quan $k = 2$ és similar al comportament quan $k = 1$ . La cadena és recurrent solament en el cas simètric quan $p_{1} = q_{1} = p_{2} = q_{2} = 1 / 4$ . Quan la dimensió de $k$ és 3 o més, la cadena és transitòria per a tots els valors dels paràmetros $p_{i}, q_{i}$ , encara en el cas simètric. Les proves són similars a la recent feta, encara que els detalls són alguna cosa més complexos. Es pot vore que

π_{00}^{(2 n)} \approx \frac{C_{k}}{n^{k / 2}}

a on $C_{k}$ és una constant positiva que depén de la dimensió de $k$ . Aixina $π_{00}^{*} = \infty$ i la cadena és recurrent si $k \in {1, 2}$ , mentres $π_{00}^{*} < \infty$ i la cadena és transitòria si $k \in {3, 4, \dots}$ .

Com a ilustració de lo anterior, imaginem ara un borracho caminant aleatoriamente per una ciutat els carrers de la qual formen una malla quadrada. En cada creuament, el borracho elegix una de les quatre possibles direccions que donen a eixe creuament (incloent aquella per la que ha vingut) en la mateixa provabilitat. Formalment, açò seria una passejada aleatòria sobre $ℤ^{2}$ . El problema de saber si el borracho aplegarà eventualment des del bar a la seua casa, caminant a l'encert, té una resposta positiva. Pero si realisem un problema similar en 3 o més dimensions, no succeïx aixina. En atres térmens, un pardal despistat podria vagar a l'encert pel cel per sempre sense trobar mai el seu niu.

Atres resultats

Retornem al cas general d'una caminada aleatòria $X$ en un grafo $G$ . Es tenen clarament els següents fets:

Si $G$ és conexo, llavors $X$ és irreducible.
Si $G$ és conexo i finito, llavors $X$ és recurrent.
En particular, si $G$ no és conexo, les components conexas de $G$ que són finitas, resulten recurrents.

Ademés suponent que $X$ és una caminada aleatòria en un grafo finito conexo, $X$ és o aperiódica o té periodo 2. Més encara, $G$ té periodo 2 si i solament si bipartito. Açò és, el conjunt de vèrtiços $V$ pot ser particionado en conjunts $A$ i $B$ tals que cada aresta en $E$ té un punt final en $A$ i un punt final en $B$ .

Essencialment totes les cadenes de Márkov reversibles poden ser interpretades com a caminades aleatòries en grafos. Este fet és una de les raons per les quals tals caminades són d'interés i es tenen els següents resultats:

Una caminada aleatòria positiva recurrent $X$ en un grafo $G$ és sempre reversible.
Recíprocamente, suponga que $X$ és una cadena de Márkov reversible en matriu de transició $P$ i funció de densitat de provabilitat invariante $f$ . Suponga $P_{x x} = 0$ per a cada $x \in S$ . Llavors $X$ pot ser interpretada com una caminada aleatòria sobre el grafo $G$ en $V = S$ i $E = {(x, y) \in S^{2} : P_{x y} > 0}$ en funció de conductància donada per:

c (x, y) = f (x) \cdot P_{x y}, (x, y) \in S^{2}

Referències

↑ Pearson, K. (1905). The Problem of the Random Walk. Nature. 72, 294.
↑ Van Kampen N. G., Stochastic Processes in Physics and Chemistry, revised and enlarged edition (North-Holland, Amsterdam) 1992.
↑ Redner S., A Guide to First-Passage Process (Cambridge University Press, Cambridge, UK) 2001.
↑ Goel N. W. and Richter-Dyn N., Stochastic Models in Biology (Academic Press, New York) 1974.
↑ Doi M. and Edwards S. F., The Theory of Polymer Dynamics (Clarendon Press, Oxford) 1986
↑ De Gennes P. G., Scaling Concepts in Polymer Physics (Cornell University Press, Ithaca and London) 1979.
↑ Risken H., The Fokker–Planck Equation (Springer, Berlin) 1984.
↑ .
↑ Cox D. R., Renewal Theory (Methuen, London) 1962.
↑ P. Diaconis, Group Representations in Probability and Statistics, Inst. of Math. Statistics, Hayward, Californis, 1988
↑ ^11,0 ^11,1 Erro en la cita: L'element <ref> no és vàlit; puix no n'hi ha una referència en text nomenada [9]

Este artícul conté una traducció derivada de «Camino aleatorio» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Pearson, K. (1905). The Problem of the Random Walk. Nature. 72, 294.

[[1]-2] Van Kampen N. G., Stochastic Processes in Physics and Chemistry, revised and enlarged edition (North-Holland, Amsterdam) 1992.

[[2]-3] Redner S., A Guide to First-Passage Process (Cambridge University Press, Cambridge, UK) 2001.

[[3]-4] Goel N. W. and Richter-Dyn N., Stochastic Models in Biology (Academic Press, New York) 1974.

[[4]-5] Doi M. and Edwards S. F., The Theory of Polymer Dynamics (Clarendon Press, Oxford) 1986

[[4c]-6] De Gennes P. G., Scaling Concepts in Polymer Physics (Cornell University Press, Ithaca and London) 1979.

[[5]-7] Risken H., The Fokker–Planck Equation (Springer, Berlin) 1984.

[[6]-8] .

[[7]-9] Cox D. R., Renewal Theory (Methuen, London) 1962.

[[8]-10] P. Diaconis, Group Representations in Probability and Statistics, Inst. of Math. Statistics, Hayward, Californis, 1988

[[9]-11] 11,0 ^11,1 Erro en la cita: L'element <ref> no és vàlit; puix no n'hi ha una referència en text nomenada [9]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]