Valor esperado del elemento en una lista ordenada de enteros

Question

¿Si usted fuera a tomar al azar números enteros positivos, ponerlos en una lista y tipo que existe de todos modos para encontrar el valor esperado del kth elemento en la lista? La lista está ordenada en orden ascendente.

Entero positivo aleatorio me refiero algún número en el rango de 0-N donde la probabilidad de cada número que es igual. (Creo que lo que trato de decir es una distribución uniforme).

Answer 1

Para ser precisos, supongamos que $k$ enteros $y_1, y_2, \ldots, y_k$ son uniformemente y de forma independiente dibujado desde el set $S = \{0,1,\ldots, N\}$ con reemplazo.

Deje $x$ ser cualquier valor en $S$. Entonces la probabilidad de que el $r^\text{th}$ más pequeña de las $y_i$ (escrito $y_{[r]}$) es menor o igual a $x$ es la probabilidad de que $r$ o más de la $y_i$ son de menos de o igual a $x$. El número de $y_i$ menos que o igual a $x$ tiene una distribución Binomial con parámetros de $p=(x+1)/(N+1)$ (la probabilidad de un resultado en el conjunto de $\{0,1,\ldots, x\}$) y $k$ (el número de "pruebas"). Por lo tanto (teniendo en $N$$k$),

$$\Pr(y_{[r]}\le x) = \sum_{i=r}^k \binom{k}{i} p^i(1-p)^{k-i}.$$

From this we compute

$$p(x,r,k,N) = \Pr(y_{[r]}= x) = \Pr(y_{[r]}\le x) - \Pr(y_{[r]}\le x-1),$$

understanding $\Pr(y_{[r]}\le -1) = 0$, and obtain the expectation directly from its definition,

$$\mathbb{E}[y_{[r]}] = \sum_{x=0}^N p(x,r,k,N) x.$$

For example, letting $N=10$ and $k=7$, the expectations for $y_{[1]}$ through $y_{[7]}$ are

$$0.927812, 2.250436, 3.624783, 5.000000, 6.375217, 7.749564, 9.072188.$$

For sufficiently large $N$, the expectation of $y_{[r]}$ will be approximately $rN/(k+1)$.

---

R code to perform these calculations follows. Begin with computing $p(x,r,k,N)$:

prob <- function(x, r, n, k) {
  p <- (x+1)/(n+1)
  if (p>=1) return (1)
  if (p<=0) return (0)
  i <- r:k
  sum(choose(k, i) * p^i * (1-p)^(k-i))
}

This should be replaced by better code for large $k$, tales como el código proporcionado por el sistema para calcular probabilidades binomiales, como en

prob <- function(x, r, n, k) pbinom(r-1, k,  (x+1)/(n+1), lower.tail=FALSE)

Sin embargo es implementado, prob puede ser utilizado por la diferenciación, multiplicando por el x, y sumando:

> n <- 10; k <- 7
> zapsmall(sapply(1:k, function(i) 
     sum(diff(sapply(-1:n, function(x) prob(x, i, n, k))) * 0:n)))

[1] 0.927812 2.250436 3.624783 5.000000 6.375217 7.749564 9.072188

Una implementación más eficaz de los usos de la sumación por partes:

> zapsmall(n - sapply(1:k, function(i) sum(sapply(-1:(n-1), function(x) prob(x, i, n, k)))))

[1] 0.927812 2.250436 3.624783 5.000000 6.375217 7.749564 9.072188