Esta es una pregunta que me hicieron en mi entrevista: tenemos $N$ Uniforme i.i.d $(0, 1)$ variables aleatorias. Definir un buen vecino para $x_i$ como el punto más cercano a $x_i$ en valor absoluto. Llamamos par $(x_i, x_j)$ un buen par si $x_i$ es $x_j$ 's buen vecino y $x_j$ es $x_i$ buen vecino. ¿Cuál es el número esperado de pares buenos?
Respuesta
¿Demasiados anuncios?
jldugger
Puntos
7490
Estadísticas de pedidos $x_{(1)}\le x_{(2)} \le \cdots \le x_{(N)},$ a una escala adecuada, tienen iid huecos exponenciales $y_i = x_{(i+1)} - x_{(i)},$ y esos huecos son las distancias entre puntos vecinos. Un "buen" hueco es el que es menor que los huecos inmediatamente anterior y posterior.
Existen $2$ huecos con un solo hueco adyacente (a saber, $y_1$ y $y_{N-1}$ ). La probabilidad de que dicho hueco sea menor que su vecino es $1/2$ porque los dos valores son iid (y de distribución continua). De lo contrario, la probabilidad de que un hueco sea menor que dos huecos vecinos es $1/3,$ por una razón comparable. Existen $N-3$ estas lagunas. Por lo tanto, se espera
$$2\left(\frac{1}{2}\right) + (N-3)\left(\frac{1}{3}\right) = \frac{N}{3}.$$
Este análisis proporciona un detalle inesperado: salvo los pares de puntos de los extremos del intervalo (cada uno de los cuales tiene un $1/2$ probabilidad de ser buena), cualquier otro par adyacente tiene una $1/3$ oportunidad de ser bueno.
