Método de caminar sobre esferas

En matemáticas , el método de caminata sobre esferas (WoS) es un algoritmo numérico probabilístico , o método de Montecarlo , utilizado principalmente para aproximar las soluciones de algún problema de valores en la frontera específico para ecuaciones diferenciales parciales (EDP). ^{[ 1 ] [ 2 ]} El método WoS fue introducido por primera vez por Mervin E. Muller en 1956 para resolver la ecuación de Laplace , ^{[ 1 ]} y desde entonces se ha generalizado a otros problemas.

Se basa en interpretaciones probabilísticas de ecuaciones diferenciales parciales y simula trayectorias de movimiento browniano (o, en el caso de variantes más generales, procesos de difusión ) muestreando únicamente los puntos de salida de esferas sucesivas, en lugar de simular en detalle la trayectoria del proceso. Esto suele hacerlo menos costoso que los algoritmos basados ​​en cuadrículas, y actualmente es uno de los algoritmos sin cuadrícula más utilizados para generar trayectorias brownianas.

Dejar${\displaystyle \Omega }$ser un dominio acotado en${\displaystyle \mathbb {R} ^{d}}$con un límite suficientemente regular${\displaystyle \Gamma }$, sea h una función en${\displaystyle \Gamma }$y dejar${\displaystyle x}$ser un punto dentro${\displaystyle \Omega }$.

Consideremos el problema de Dirichlet :

${\displaystyle {\begin{cases}\Delta u(x)=0&{\mbox{si }}x\in \Omega \\u(x)=h(x)&{\mbox{si }}x\in \Gamma .\end{cases}}}$

Se puede demostrar fácilmente ^{[ a ]} que cuando la solución${\displaystyle u}$existe, para${\displaystyle x\in \Omega }$:

${\displaystyle u(x)=\mathbb {E} _{x}[h(W_{\tau })]}$

donde W es un proceso de Wiener d -dimensional , el valor esperado se toma condicionalmente en { W ₀ = x } , y τ es el tiempo de primera salida de Ω .

Para calcular una solución usando esta fórmula, solo tenemos que simular el primer punto de salida de trayectorias brownianas independientes ya que con la ley de los grandes números :

${\displaystyle \mathbb {E} _{x}[h(W_{\tau })]\sim {\frac {1}{n}}\sum _{i=1}^{n}h(W_{\tau }^{i})}$

El método WoS proporciona una forma eficiente de muestrear el primer punto de salida de un movimiento browniano del dominio, al observar que para cualquier esfera ( d  −  1) centrada en x , el primer punto de salida de W fuera de la esfera tiene una distribución uniforme sobre su superficie. Por lo tanto, comienza con x ^{( 0 )} igual a x y dibuja la esfera más grande.${\displaystyle {\mathcal {S}}_{0}}$centrado en x ^{( 0 )} y contenido dentro del dominio. El primer punto de salida x ^{( 1 )} de${\displaystyle {\mathcal {S}}_{0}}$está distribuido uniformemente en su superficie. Al repetir este paso inductivamente, el WoS proporciona una secuencia ( x ^{( n )} ) de posiciones del movimiento browniano.

Según la intuición, el proceso convergerá al primer punto de salida del dominio. Sin embargo, este algoritmo tarda casi con seguridad un número infinito de pasos en terminar. Para la implementación computacional, el proceso generalmente se detiene cuando se acerca lo suficiente al borde y devuelve la proyección del proceso sobre el borde. Este procedimiento a veces se denomina introducción de un${\displaystyle \varepsilon }$-concha, o${\displaystyle \varepsilon }$-capa. ^{[ 4 ]}

Elegir${\displaystyle \varepsilon >0}$Utilizando la misma notación que la anterior, el algoritmo Walk-on-spheres se describe de la siguiente manera:

1. Inicializar  :${\displaystyle x^{(0)}=x}$
2. Mientras${\displaystyle d(x^{(n)},\Gamma )>\varepsilon }$:
   1. Colocar${\displaystyle r_{n}=d(x^{(n)},\Gamma )}$.
   2. Muestra${\displaystyle \gamma _{n}}$un vector distribuido uniformemente sobre la esfera unitaria , independientemente de los anteriores.
   3. Colocar${\displaystyle x^{(n+1)}:=x^{(n)}+r_{n}\gamma _{n}}$
3. Cuando${\displaystyle d(x^{(n)},\Gamma )\leq \varepsilon }$:
4. ${\displaystyle x_{f}:=p_{\Gamma }(x^{(n)})}$, la proyección ortogonal de${\displaystyle x^{(n)}}$en${\displaystyle \Gamma }$
5. Devolver${\displaystyle x_{f}}$

El resultado${\displaystyle x_{f}}$es un estimador del primer punto de salida de${\displaystyle \Omega }$de un proceso Wiener que comienza desde${\displaystyle x}$, en el sentido de que tienen distribuciones de probabilidad cercanas (véase más abajo para comentarios sobre el error).

Este método ha sido ampliamente estudiado, generalizado y mejorado. Por ejemplo, actualmente se utiliza extensamente para el cálculo de propiedades físicas de los materiales (como la capacitancia , la energía electrostática interna de las moléculas, etc.). Algunas extensiones destacadas incluyen:

• Fórmula de Feynman-Kac
• Procesos estocásticos y problemas de valores en la frontera
• Método de Euler-Maruyama para muestrear las trayectorias de procesos de difusión generales.

• Sabelfeld, Karl K. (1991). Métodos de Monte Carlo en problemas de contorno . Berlín [etc.]: Springer-Verlag. ISBN 9783540530015.

• Algunos métodos continuos de Montecarlo para el problema de Dirichlet. El artículo en el que Marvin Edgar Muller introdujo el método.
• Movimiento browniano, por Peter Mörters y Yuval Peres. Véase el capítulo 3.3 sobre medida armónica, funciones de Green y puntos de salida.