Número esperado de Pareto-óptima de los puntos de

Question

Supongamos $S$ es un conjunto de $n$ puntos en un plano. Un punto que se llama máxima (o Pareto-óptimo) si no hay otro punto en $S$ está por encima y a la derecha de ese punto.

Si cada punto en $S$ es elegido de forma independiente y uniformemente al azar de la unidad de la plaza de $[0,1]\times [1,0]$. ¿Cuál es el exacto número esperado de Pareto-óptima puntos en $S$?

Answer 1

Etiqueta los puntos n $p_1,…,p_n$ en orden descendente de su y coordenadas. $p_1$ es máxima, ya que está por encima de todos los otros puntos, y su contribución prevista para el número total máximo de puntos es por lo tanto 1.

$p_2$ está por encima de los puntos de $p_3,…,p_n$, pero por debajo de $p_1$, y es por lo tanto la máxima iff es a la derecha de $p_1$. Dado que la distribución de $p_1$ $p_2$ en la x de dimensión es aleatorio e independiente de que en el y dimensión, es igualmente probable que uno de ellos será el de la derecha de la otra. La probabilidad de que $p_2$ es máxima por lo tanto es $\frac 1 2$, y su contribución prevista para el número total máximo de puntos es $\frac 1 2$ x 1 = $\frac 1 2$.

Ahora considere la posibilidad de cualquier punto de $p_m$. La generalización en el caso de $p_2$, $p_m$ está por encima de los puntos de $p_{m+1},…,p_n$, pero por debajo de los puntos de $p_1,…,p_{m-1}$, y es por lo tanto la máxima iff es el derecho de todos los de $p_1,…,p_{m-1}$. Dado que la distribución de $p_1,…,p_m$ en la x de dimensión es aleatorio e independiente de que en la dimensión y, es igualmente probable que uno de ellos será el de la derecha de todos los demás. La probabilidad de que $p_m$ es máxima por lo tanto es $\frac 1 m$, y su contribución prevista para el número total máximo de puntos es $\frac 1 m$ x 1 = $\frac 1 m$.

El número esperado de consumo máximo de puntos es por lo tanto 1 + $\frac 1 2$ ... + $\frac 1 n = H_n$, el $n$ésimo número Armónico.

Answer 2

Deje $I_i$ ser el indicador de la variable aleatoria que denota si la i-ésima punto en $S$ es pareto óptimo. A continuación, el número de pareto-óptima puntos en $S$ $M = \sum_{i=1}^{n} I_i$ $E[M] = \sum_{i=1}^n E[I_i]$ por la linealidad de las expectativas. Desde $I_i$ es un binario con valores de variable aleatoria, también tenemos $E[I_i] = P(I_i = 1)$. Poner esto juntos, llegamos $E[M] = \sum_{i=1}^n P(I_i = 1)$.

Para evaluar $P(I_i=1)$, tenemos que averiguar la probabilidad de que no hay ningún punto por encima y a la derecha de la i-ésima punto. Esto puede ser hecho por primera acondicionado en la i-ésima del punto de ubicación dentro de la plaza de la unidad y, a continuación, exigiendo que todos los restantes $(n-1)$ puntos no se encuentran en el pequeño rectángulo de arriba y a su derecha. Si la i-ésima punto es $(x_i,y_i)$, queremos que ninguno de los restantes $(n-1)$ puntos en el rectángulo de lados a$1-x_i$$1-y_i$. La probabilidad de que un punto al azar, se encuentra en este rectángulo es simplemente su área y de la probabilidad de que ninguno de los $(n-1)$ puntos se encuentran en este rectángulo es, por tanto,$(1-(1-x_i)(1-y_i))^{n-1}$.

\begin{eqnarray} P(I_i=1 \mid \text{ith pt} = (x_i,y_i)) &=& (1-(1-x_i)(1-y_i))^{n-1} \\ P(I_i=1) &=& \int_0^1 \int_0^1 (1-(1-x_i)(1-y_i))^{n-1} dx_i dy_i \\ &=& \int_0^1 \int_0^1 (1-uv)^{n-1} du dv \end{eqnarray}

Esta integral es bastante fácil de calcular. Mediante la celebración de $v$ constante, podemos evaluar primero el interior de la integral como

$\int_0^1 (1-uv)^{n-1} du = \frac{1}{nv} (1-(1-v)^{n})$

Haciendo la sustitución de $v \rightarrow 1-v$, obtenemos

\begin{eqnarray} P(I_i = 1) &=& \frac{1}{n} \int_0^1 \frac{1-v^n}{1-v} dv \\ &=& \frac{1}{n} \int_0^1 (1+v+\dots+v^{n-1}) dv \\ &=& \frac{1}{n} \left(1+\frac{1}{2}+\dots+\frac{1}{n}\right) = \frac{H_n}{n} \end{eqnarray}

Finalmente, calculamos el $E[M] = \sum_{i=1}^n P(I_i=1) = H_n$ donde $H_n$ es el n-ésimo número Armónico.