Función de masa de probabilidad para la primera muestra no creciente de una secuencia aleatoria

Question

Considere una secuencia de números aleatorios extraídos IID de alguna distribución $g(x)$ . ¿Cómo podría determinar la distribución del valor de la primera muestra de esa secuencia que no es mayor que todas las muestras anteriores? ¿Qué pasa con el caso especial en el que $g(x)$ es uniforme sobre $[0, 1]$ ?

Ejemplo: Algunas secuencias IID de ejemplo extraídas de $U(0,1)$ son

0.35, 0.29, 0.19, 0.64, ...
      ^^^^
0.33, 0.35, 0.22, 0.62, ...
            ^^^^
0.21, 0.01, 0.98, 0.11, ...
      ^^^^
0.59, 0.77, 0.93, 0.17, ...
                  ^^^^

Las primeras muestras no monótonas son 0.29, 0.22, 0.01, 0.17 . Estoy interesado en la función de distribución de estos valores, ya sea en la general o en la $U(0,1)$ caso.

Answer 1

Dejemos que $X_1,X_2,X_3,... \sim \text{IID } G$ sea su secuencia intercambiable de variables aleatorias y defina $N \equiv \max \{ n \in \mathbb{N} | X_1 < X_2 < \cdots < X_n \}$ que es la longitud de la mayor porción creciente al principio de la secuencia. Se busca la distribución de la variable aleatoria $X_{N+1}$ , que es el primer valor que se no mayor que todos los valores anteriores. Esta cuestión es manejable si la distribución $G$ es continua, pero se complica mucho más si la distribución tiene alguna parte discreta, ya que eso requiere tratar con empates. Para simplificar, voy a mostrar la respuesta que se mantiene cuando se tiene una distribución continua.

---

Algunos trabajos preliminares: Utilizaremos $G$ para denotar la función de distribución (continua) y $g$ para denotar la función de densidad correspondiente. En esta pregunta relacionada se estableció que la función de masa para $n$ es:

$$p_N(n) = \mathbb{P}(N=n) = \frac{n}{(n+1)!} \quad \quad \quad \quad \text{for all } n \in \mathbb{N}.$$

Desde $N=n$ requiere que $X_1< \cdots <X_n \geqslant X_{n+1}$ (y el máximo es invariante al orden) también tenemos:

$$\mathbb{P}(X_n \leqslant r | N=n) = \mathbb{P}(X_i \leqslant r)^{n+1} = G(r)^{n+1},$$

que da la densidad correspondiente:

$$p(X_n = r|N=n) = (n+1) g(r) G(r)^n.$$

---

Encontrar la densidad objetivo: Utilizando los resultados anteriores tenemos:

$$\begin{equation} \begin{aligned} p(X_{N+1} = x|N=n) &= \int p(X_{n+1} = x | X_n = r, N=n) \ dP(X_{n} \leqslant r | N=n) \\[6pt] &= \int \limits_x^\infty p(X_{n+1} = x | X_n = r, N=n) \cdot p(X_{n} = r | N=n) \ dr \\[6pt] &= \int \limits_x^\infty p(X_{n+1} = x | X_{n+1} \leqslant r) \cdot p(X_{n} = r | N=n) \ dr \\[6pt] &= \int \limits_x^\infty \frac{g(x)}{G(r)} \cdot (n+1) g(r) G(r)^{n} \ dr \\[6pt] &= g(x) \int \limits_x^\infty (n+1) g(r) G(r)^{n-1} \ dr \\[6pt] &= g(x) \Bigg[ \frac{n+1}{n} \cdot G(r)^{n} \Bigg]_{r=x}^{r \rightarrow \infty} \\[12pt] &= \frac{n+1}{n} \cdot g(x) (1 - G(x)^n). \\[6pt] \end{aligned} \end{equation}$$

Por lo tanto, tenemos:

$$\begin{equation} \begin{aligned} p(X_{N+1} = x) &= \sum_{n=1}^\infty \ p(X_{n+1} = x | N=n) \cdot \mathbb{P}(N=n) \\[6pt] &= \sum_{n=1}^\infty \ \frac{n+1}{n} \cdot g(x) (1 - G(x)^n) \cdot \frac{n}{(n+1)!} \\[6pt] &= g(x) \sum_{n=1}^\infty \ \frac{1 - G(x)^n}{n!} \\[6pt] &= g(x) \sum_{n=0}^\infty \ \frac{1 - G(x)^n}{n!} \\[6pt] &= g(x) ( e - e^{G(x)} ). \\[6pt] \end{aligned} \end{equation}$$

La función de distribución correspondiente es:

$$\begin{equation} \begin{aligned} \mathbb{P}(X_{N+1} \leqslant x) &= \int \limits_{-\infty}^x g(r) ( e - e^{G(r)} ) \\[6pt] &= \Bigg[ G(r) \cdot e - e^{G(r)} \Bigg]_{r \rightarrow - \infty}^{r=x} \\[6pt] &= \Bigg[ G(x) \cdot e - e^{G(x)} - (-1) \Bigg] \\[6pt] &= 1 + G(x) \cdot e - e^{G(x)}. \\[6pt] \end{aligned} \end{equation}$$

---

Caso especial: distribución uniforme: En el caso de que utilicemos la distribución uniforme estándar tenemos $g(x) = 1$ y $G(x) = x$ para todos $0 \leqslant x \leqslant 1$ por lo que tenemos:

$$\begin{equation} \begin{aligned} p(X_{N+1} = x) &= e - e^{x}. \\[6pt] \end{aligned} \end{equation}$$

Answer 2

@Ben proporciona la mayor parte de la solución, aquí hay un resumen que corrige un error menor:

La secuencia que nos interesa consta de N elementos monótonos ( $X_1 < X_2 < ... < X_N$ ) seguido de un elemento no monótono en la posición N+1. Nos interesa $p(X_{N+1}=x)$

El PDF para el longitud de la secuencia monótona al principio de la cadena (excluyendo la primera muestra no monótona) es $p(N=n) = \frac{n}{(n+1)!}$

El PDF para el valor máximo entre los primeros N+1 elementos (que, en este contexto, es también el valor del elemento en la posición N) es $p(X_n=r | N=n) = (n+1)g(r)G(r)^n$ donde G es la función de distribución acumulativa correspondiente a g.

La distribución para $X_{N+1}$ es $p(X_{N+1} = x) = \sum_{n=1}^{\infty}\int_x^{\infty}{p(X_{N+1}=x|X_N=r, N=n)p(X_n=r|N=n)p(N=n)dr}$

Utilizando el hecho de que $X_{N+1} < X_{N}$ el primer término equivale a

$\sum_{n=1}^{\infty}\int_x^{\infty}{p(X_{N+1}=x|X_{N+1} < r, N=n)p(X_n=r|N=n)p(N=n)dr}$

Lo cual podemos voltear usando la regla de Bayes:

$\sum_{n=1}^{\infty}\int_x^{\infty}{\frac{p(X_{N+1}<r|X_{N+1}=x, N=n)p(X_{N+1}=x|N=n)}{p(X_{N+1} < r | N=n)}p(X_n=r|N=n)p(N=n)dr}$

Por último, al conectar $g$ y $G$ basado en las identidades anteriores:

$ \sum_{n=1}^{\infty}\int_x^{\infty} \frac{g(x)}{G(r)}(n+1)g(r)G(r)^n\frac{n}{(n+1)!} dr$

$ \sum_{n=1}^{\infty}g(x)\frac{1}{n!}\int_x^{\infty}ng(r)G(r)^{n-1} dr$

$ \sum_{n=1}^{\infty}\frac{g(x)}{n!}[1 - G(x)^n]$

Para el caso en que $X \sim U(0,1)$ , $g(x)=1$ , $G(x)=x$ y

$p(X_{N+1})=\sum_{n=1}^{\infty}\frac{1-x^n}{n!} = e-e^x$

Lo que podemos confirmar con la simulación de Monte Carlo:

def sample(g = np.random.uniform):    
    x = top = g()
    while x >= top:
        top = x
        x = g()
    return x

def f(x):
    return np.e - np.exp(x)

plt.hist([sample() for _ in range(100000)], bins=100, density=True)
x = np.linspace(0, 1, 20)
y = np.array([f(xx) for xx in x])
plt.plot(x, y)