Supongamos $X_1, X_2, \dotsc, X_n$ son yo.yo.d. variables aleatorias. Cuando es la secuencia que se espera una disminución de la primera vez?

Question

Como el título sugiere. Supongamos $X_1, X_2, \dotsc, X_n$ son continuas yo.yo.d. variables aleatorias con pdf $f$. Considere el caso de que $X_1 \leq X_2 \dotsc \leq X_{N-1} > X_N$, $N \geq 2$, por lo tanto $N$ es cuando la secuencia disminuye por primera vez. Entonces ¿cuál es el valor de $E[N]$?

Traté de evaluar $P[N = i]$ primera. Tengo \begin{align*} P[N = 2] & = \int_{-\infty}^{\infty} f(x)F(x)dx \\ & = \frac{F(x)^2}{2}\Large|_{-\infty}^{\infty} \\ & = \frac{1}{2} \\ P[N = 3] & = \int_{-\infty}^{\infty} f(x)\int_x^{\infty}f(y)F(y)dydx \\ & = \int_{-\infty}^{\infty}f(x)\frac{1-F(x)^2}{2}dx \\ & = \frac{F(x)-F(x)^3/3}{2}\Large|_{-\infty}^{\infty} \\ & = \frac{1}{3} \end{align*} Del mismo modo, conseguí $P[N = 4] = \frac{1}{8}$. Como $i$ se hace grande, el cálculo se hace más complicada y no puedo encontrar el patrón. Puede alguien sugerir cómo debo proceder?

Answer 1

Si $\{X_i\}_{i\geq 1}$ es un intercambiables secuencia de variables aleatorias y $$N=\min\,\{n:X_{n-1}>X_n\},$$ then $N\geq n$ if and ony if $X_1\leq X_2\leq\dots\leq X_{n-1}$. Therefore, $$\Pr(N\geq n) = \Pr(X_1\leq X_2\leq\dots\leq X_{n-1})=\frac{1}{(n-1)!},$$ por la simetría. Por lo tanto, $\mathrm{E}[N]=\sum_{n=1}^\infty \Pr(N\geq n)=e\approx 2.71828\dots$.

# Monte Carlo
N <- 10^6
dec <- numeric(N)
for (i in 1:N) {
    j <- 1
    x <- rnorm(1, 0, 1) # plug your favorite distribution here!
    repeat {
        j <- j + 1
        y <- rnorm(1, 0, 1)
        if (y < x) {
            dec[i] <- j
            break
        }
        x <- y
    }
}
cat(mean(dec), "\n")
# A good example of how to program C in R!

Answer 2

Según lo sugerido por el pececillo de plata, voy a postear la solución a continuación. \begin{align*} P[N = i] & = P[X_1 \leq X_2 \dotsc \leq X_{i-1} > X_i] \\ & = P[X_1 \leq X_2 \dotsc \leq X_{i-1}] - P[X_1 \leq X_2 \dotsc \leq X_{i-1} \leq X_i] \\ & = \frac{1}{(i-1)!} - \frac{1}{i!} \end{align*} Y \begin{align*} P[N \geq i] & = 1 - P[N < i] \\ & = 1 - \left(1 -\frac{1}{2!} + \frac{1}{2!} - \frac{1}{3!} + \cdots +\frac{1}{(i-2)!} - \frac{1}{(i-1)!}\right)\\ & = \frac{1}{(i-1)!} \\ \end{align*}

Por lo tanto $E[N] = \sum_{i = 1}^{\infty}P[N \geq i] = \sum_{i = 1}^{\infty}\frac{1}{(i-1)!} = e$.

Answer 3

Un argumento alternativo: sólo hay un pedido de la $X_i$ que es el incremento, de la $n!$ permutaciones posibles de $X_1, \dots, X_n$. Estamos interesados en la compra que aumentan hasta la penúltima posición y, a continuación, disminuir: esto requiere el máximo para estar en la posición $n-1$, y una de las $n-1$ $X_i$ a estar en la posición final. Desde allí se $n-1$ maneras de escoger uno de los primeros a $n-1$ términos en nuestra secuencia ordenada y moverlo a la posición final, entonces la probabilidad es:

$$\Pr(N=n) = \frac{n-1}{n!}$$

Note $\Pr(N=2) = \frac{2-1}{2!} = \frac{1}{2}$, $\Pr(N=3) = \frac{3-1}{3!} = \frac{1}{3}$ and $\Pr(N=4) = \frac{4-1}{4!} = \frac{1}{8}$ so this is consistent with the results found by integration.

To find the expected value of $N$ we can use:

$$\mathbb{E}(N) = \sum_{n=2}^{\infty} n \Pr(N=n) = \sum_{n=2}^{\infty} \frac{n(n-1)}{n!} = \sum_{n=2}^{\infty} \frac{1}{(n-2)!}= \sum_{k=0}^{\infty} \frac{1}{k!} = e$$

(To make the summation more obvious I have used $k=n-2$; for readers unfamiliar with this sum, take the Taylor series $e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!}$ and substitute $x=1$.)

Podemos comprobar el resultado de la simulación, aquí está el código en R:

firstDecrease <- function(x) {
    counter <- 2
    a <- runif(1)
    b <- runif(1)
    while(a < b){
        counter <- counter + 1
        a <- b
        b <- runif(1)
    }
    return(counter)
}

mean(mapply(firstDecrease, 1:1e7))

Este regresó 2.718347, lo suficientemente cerca como para 2.71828 para satisfacer a mí.

Answer 4

EDIT: Mi respuesta es incorrecta. Me voy como un ejemplo de lo fácil que parece ser una sencilla pregunta como esta es malinterpretar.

No creo que su matemática es correcta para el caso de $ P[N=4] $. Podemos comprobar esto a través de una simulación simple:

n=50000
flag <- rep(NA, n)
order <- 3
for (i in 1:n) {
  x<-rnorm(100)
  flag[i] <- all(x[order] < x[1:(order-1)])==T
}
sum(flag)/n

Nos da:

> sum(flag)/n
[1] 0.33326

El cambio de la order plazo 4 nos:

> sum(flag)/n
[1] 0.25208

Y 5:

> sum(flag)/n
[1] 0.2023

Así que si confiamos en nuestros resultados de la simulación, parece que el patrón es que $P[N = X] = \frac{1}{x}$. Pero esto tiene sentido, ya que lo que en realidad está preguntando ¿cuál es la probabilidad de que una observación en un subconjunto de todas sus observaciones es el mínimo de observación (si estamos suponiendo que yo.yo.d. entonces estamos asumiendo exchangability y por lo tanto el orden es arbitrarias). Uno de ellos tiene que ser el mínimo, y así que en realidad la pregunta es ¿cuál es la probabilidad de que cualquier observación seleccionado al azar es el mínimo. Esto es sólo una simple binomio proceso.