Comience en un punto $(0,0,z_0)$ y dé $n$ pasos de longitud unitaria en una dirección aleatoria (para cada paso) en $\mathbb{R}^3$. Que tal caminata sea válida si la posición del último paso, y solo del último paso, está debajo del plano $(x_n, y_n, z_n<0)$. Que una caminata sea casi válida si al menos el último paso está debajo del plano.
¿Cómo puedo muestrear de forma uniforme del conjunto de todas las caminatas válidas o casi válidas sin un método de prueba y rechazo?
Lo que hay que tener en cuenta cuando se muestrean direcciones de manera uniforme desde la esfera unitaria es que en tres dimensiones eso significa que $z$ está distribuido de manera uniforme. Por lo tanto, puedes ignorar el movimiento lateral y efectivamente tener un paseo aleatorio unidimensional con pasos distribuidos de manera uniforme en $[-1,1]$ (después de escalar la longitud del paso a $1$).
La proporción de paseos válidos para un $n$ dado como función de $z$ es polinomial por tramos de grado a lo sumo $n$, con un polinomio para cada intervalo entre dos enteros. Si $n$ no es demasiado grande, puedes calcular estos polinomios, luego hacer una forma no muy derrochadora de muestreo por rechazo limitándolos por una función constante o lineal o cuadrática sobre $[z_0-1,z_0+1]$. Se necesitará un poco de contabilidad para tratar correctamente el límite en $z=0$, pero no debería ser demasiado difícil.
Aquí hay una idea que creo que solo funcionará para el caso casi válido, pero podría funcionar bien para eso.
El problema es que las distribuciones polinómicas por tramos se vuelven cada vez más complicadas cuando las convolucionas con la distribución uniforme en $[-1,1]$. Por lo tanto, nos gustaría reemplazarlas por algo para lo cual la convolución con la distribución uniforme sea fácil de calcular y no aumente la complejidad. Una suma de sinusoidales encaja en eso, ya que cada sinusoidal solo se multiplica por una constante con la convolución.
Comienza desde el final con una densidad constante en $[z_0-n,0]$. Convoluciona esto con la distribución uniforme en $[-1,1]$ algunas veces, tal vez $100$ o $1000, tantas como puedas permitirte manejar los polinomios para. Ahora se asemeja fuertemente a una Gaussiana. Elige un intervalo suficientemente grande centrado en la media de la distribución en $(z_0-n)/2$ de modo que tanto el grueso de la distribución como cualquier valor de $z$ que esperes alcanzar estén bien dentro del intervalo, calcula una suma parcial de la serie de Fourier para la distribución en este intervalo, limita la magnitud de la cola restante y suma una constante correspondiente a la suma parcial para llegar a una suma de Fourier que aproxima la distribución y la limita desde arriba. Dado que la casi-Gaussiana es bastante suave, no necesitarás demasiados términos para obtener una buena aproximación.
Esta suma de Fourier es ahora tu nuevo objetivo. Puedes propagarla muy fácilmente a $n$, incluso para $n\gg1000, dado que la convolución es solo una multiplicación. Comienza con $(n,z_0)$, fingiendo que estás tratando de muestrear la distribución objetivo. Luego, cuando llegues a la etapa de la distribución objetivo, haz un paso de rechazo único en el que rechaces el paseo generado si un número dibujado uniformemente entre $0$ y la suma de Fourier está por encima de la distribución correcta. Esto te da la distribución correcta, y luego puedes proceder con los polinomios correctos.
Escribí la respuesta a continuación cuando malinterpreté la pregunta para referirse a paseos aleatorios en una red; la dejo tal cual porque podría ser interesante para otros por derecho propio.
Me gusta la pregunta. (Solía hacer simulaciones de teoría de calibre en redes.)
Para hacer esto, necesitas conocer el número $a(n,z)$ de paseos (casi) válidos.
Si desplazas $z$ en $1$ para que un paseo sea válido si termina en $z=0$, lo cual simplifica ligeramente el indexado, los números $a(n,z)$ para paseos válidos están dados por la secuencia OEIS A052179. La entrada proporciona varias prescripciones para generarlos. Creo que la más eficiente para ti es probablemente la relación de recurrencia,
$$ a(n,z)=a(n-1,z-1)+4a(n-1,z)+a(n-1,z+1)\;, $$
ya que solo necesitas calcular $a(n,z_0)$ una vez al principio y almacenar los resultados intermedios, que contendrán todos los valores que necesitas más adelante en la simulación.
Una vez que sepas los valores $a(n-1,z-1)$, $a(n-1,z)$ y $a(n-1,z+1)$ en tu punto actual, todo lo que tienes que hacer es dibujar un número aleatorio uniformemente entre $1$ y $a(n,z)$ y elegir a dónde ir según en cuál de los seis intervalos de longitudes $a(n-1,z_0-1)$, $a(n-1,z_0+1)$ y cuatro veces $a(n-1,z_0)$ caiga.
La relación de recurrencia es la misma para los paseos casi válidos; solo las condiciones iniciales son diferentes.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
