Probabilidad de que dos puntos se dividan en diferentes particiones.

Question

Supongamos que $x < y \in [0, 1]$ y $U_1, U_2, ...$ son variables aleatorias distribuidas como uniformes en $(0, w)$ con $w < 1$ . Definir $S_n = \sum_{i = 1} ^ n U_i$ . Diremos que $(S_i)$ divide $x$ y $y$ si, para algunos $n$ , $x < S_n < y$ . Me interesa saber qué tipo de cosas se podrían decir sobre la probabilidad de que $x$ y $y$ están divididos. Si ayuda, toma $w$ ser pequeño y $x, y$ cerca de $1$ y $|x - y| < w$ .

Creo que esto está bastante relacionado con cualquier asignatura que estudie cosas como los procesos de Poisson. Obviamente, sé que si $|x - y| > w$ entonces $x$ y $y$ se dividirá, pero más allá de eso no estoy seguro de a qué teoría recurriría, y no sé si este tipo de problema es manejable o no (por lo que sé, podría ser trivial). La única suposición que tengo es que cerca de $|x - y| = w$ la probabilidad debe ir a $0$ como $1 - \frac{|x - y|}{w}$ y esto debería ser un límite inferior para cualquier $|x - y| < w$ . También me pueden interesar los resultados o indicaciones para $U_i$ no es uniforme, pero necesito que se dé el caso de que para puntos suficientemente alejados la probabilidad de ser dividido sea exactamente $1$ .

EDITAR : A la luz de la solución publicada por PinkElephant a continuación, voy a reformular esto de la siguiente manera. Establecer $w = 1$ y eliminar la restricción de $x, y \in [0, 1]$ para que sólo $x < y \in \mathbb R$ . ¿Cuál es la probabilidad de que $x$ y $y$ se dividen para valores grandes de $x, y$ pero para $|x - y|$ fijo, es decir $x, y \to \infty$ pero $y - x$ constante. Me parece que asintóticamente las cosas sólo deberían depender de $y - x$ para $x, y$ cerca de $0$ parece que se depende del hecho de que empezamos la suma desde $0$ de la que creo que escapamos por grandes $x, y$ .

Actualización : Tengo un argumento heurístico que da la probabilidad asintótica de $x$ y $y$ siendo dividido como $1 - (1 - |x - y|)^2_+$ donde $(a)_+$ denota $\max\{0, a\}$ . El argumento es el siguiente: no debería importar asintóticamente dónde $x$ y $y$ mentira, por lo que podemos suponer $x= k$ para algún número entero positivo $k$ . $x$ y $y$ se dividirá si, para el primer valor de $S_i$ en el intervalo $[x, x + 1]$ tenemos $x \le S_i \le y$ . Consideremos la cadena de Markov $T_j$ consistente en las partes fraccionarias de los $S_i$ tal que $(S_{i - 1}) > (S_i)$ , donde $(a)$ denota la parte fraccionaria de $a$ . La probabilidad de que $x$ y $y$ se dividen debe ser $P(T \le (y - x))$ donde $T$ se extrae de la distribución estacionaria del $T_j$ . Adiviné a ciegas que la distribución estacionaria venía dada por la densidad $f(t) = 2(1 - t)$ , sacó un montón de muestras de la cadena de Markov que describí, y verificó empíricamente que $f(t) = 2 (1 - t)$ es la respuesta que debo obtener.

Si alguien quiere hacer una prueba para verificar que $1 - (1 - |x - y|)_+^2$ es efectivamente la respuesta correcta asintóticamente, sería muy apreciado.

Answer 1

Si escalamos $x$ , $y$ y $w$ por la misma constante positiva, la respuesta no cambia, así que para simplificar tomaré $w=1$ y eliminar la restricción de que $x,y\in[0,1]$ . Definir $f(x,y)$ es la probabilidad de que $x$ y $y$ están divididos. Para la arbitrariedad $w$ la probabilidad de que $x$ y $y$ se dividen es $f\left(\frac{x}{w},\frac{y}{w}\right)$ .

Para $0<x\leq y$ , $f(x,y)$ satisface la ecuación $$f(x,y)=\int_0^1f(x-t,y-t)\,dt$$ (Ampliamos $f(x,y)$ a la región $\{y\geq x\}\subset\mathbb{R}^2$ al establecer $f(x,y)=1$ para $x<0$ , $y\geq0$ y $f(x,y)=0$ para $x<y<0$ )

Esta ecuación se puede diferenciar para obtener la ecuación diferencial de retardo $$f_x(x,y)+f_y(x,y)=f(x,y)-f(x-1,y-1)$$

La solución es analítica real a trozos, con los límites entre los trozos situados en las líneas $y=x$ , $y=x+1$ los segmentos de línea $y\in [x,x+1],x\in\mathbb{Z}_{\geq0}$ y los segmentos de línea $y\in[x,x+1],y\in\mathbb{Z}_{\geq0}$ .

No es demasiado difícil calcular recursivamente los valores de $f(x,y)$ en las distintas piezas del dominio. He calculado algunos valores con Mathematica:

Para $0<x\leq y<1$ , $f(x,y)=(y-x)e^x$ .

Para $0<x\leq 1\leq y\leq x+1$ , $f(x,y)=(y-x)e^x+1-e^{y-1}$ .

Para $1\leq x\leq y\leq 2$ , $f(x,y)=e^{x-1}-e^{y-1}+e^x\left(x^2-2x+2y-xy\right)$ .

Si quiere calcular un valor específico de $f(x,y)$ exactamente, no sé si hay una manera más rápida que continuar este cálculo recursivo. Si sólo te interesa el valor límite como $x,y\to\infty$ con $y-x$ arreglado, esto podría ser posible de calcular.

Answer 2

Dado $x$ , dejemos que $S_x$ sea la variable aleatoria $S_{\min \{n, S_n \ge x\}}$ . Tiene valores en $[x;x+1]$ y que $g_x(y)$ sea su densidad : $\forall x \le y_1 \le y_2 \le x+1, \int_{y_1}^{y_2} g_x(y)dy = P(S_x \in [y_0;y_1])$ .

Como $x$ crece, el peso que se pone $g_x(y)$ para $y$ cerca de $x$ se desplaza y se redistribuye a todos los demás $y \in [x;x+1]$ . En particular, si $x_1 \le x_2 \le y_1 \le y_2 \le x_1+1$ entonces $y_1$ y $y_2$ reciben la misma cantidad de peso al pasar de $x_1$ a $x_2$ Así que..: $g_{x_2}(y_1) - g_{x_1}(y_1) = g_{x_2}(y_2) - g_{x_1}(y_2)$ y esto implica que la función $g_x(y_2)-g_x(y_1)$ es constante para el rango de $x$ donde tiene sentido.

De esto podemos deducir que hay dos funciones $F(x),G(y)$ tal que $g_x(y) = G(y)+F(x)$ siempre que $g_x(y)$ tiene sentido.

Ahora, debemos tener que para todos $x>1$ , $g_x(x+1)=0$ Por lo tanto $F(x) = -G(x+1)$ y así $g_x(y) = G(y)-G(x+1)$ . Además, para todos los $x$ , $1 = \int_x^{x+1} g_x(y)dy = -G(x+1)+ \int_x^{x+1} G(y)dy$ . Diferenciando esto se obtiene $0 = -G'(x+1)+G(x+1)-G(x)$ por lo que el problema se reduce a estudiar la ecuación diferencial con retardo $$f'(x) = f(x) - f(x-1)$$

Nuestra condición inicial es $G(x) = 1$ para $0 \le x < 1$ y $G(1)=0$ . El objetivo es demostrar que para $a \in [0;1], G(x) - G(x+a) = 2a + o(1)$ .

La solución que nos interesa se puede definir pieza por pieza, resulta que $G(x+1) = 1 - e^x\sum_{0 \le k \le x} (\frac{k-x}e)^k/k!$

---

Supongamos que $f$ es una solución de la ecuación diferencial. Poner $g(x) = \int_{x-1}^x f(t) dt - f(x)$ . Entonces $g'(x) = f(x) - f(x-1) -f'(x) = 0$ . Así que $g(x) = C$ y restando $2Cx$ de $f(x)$ podemos suponer sin pérdida de generalidad que $g(x) = 0$ .

Definir $h(x) = \int_{x-1}^x (f(t)-f(x))^2 dt$ . Entonces $$h'(x) = (f(x)^2 - f(x-1)^2) -2(f(x)^2-f(x-1)f(x)+f'(x)\int_{x-1}^x f(t)dt) + 2f(x)f'(x) \\ = (f(x)^2 - f(x-1)^2) -2(f(x)^2-f(x-1)f(x)) = -(f(x-1)-f(x))^2 = -f'(x)^2$$ $h$ es obviamente positivo, y decreciente, por lo que tiene un límite, y en particular, para cualquier $a\in [0;1], h(x)-h(x+a) \to 0$ , de manera uniforme en $a$ .

Finalmente, $(f(x+a)-f(x))^2 = \left(\int_x^{x+a} f'(t)dt \right)^2 \le a \int_x^{x+a} f'(t)^2 dt = a(h(x+a) - h(x)) \to 0$ . Por lo tanto, en el contexto original, $g_x(y) \to 0$ (uniformemente) como $x \to \infty$