Probabilidad de encontrar un nuevo valor más pequeño

Question

Estoy haciendo algunas simulaciones y necesito una buena heurística para detener la simulación. La simulación continuamente salidas de datos con un costo en el rango [0,1]. La salida se ve gamma distribuido o posiblemente de Poisson.

Este es un estándar de Hojas de cálculo de Google histograma; todos los valores predeterminados.

Y he aquí un diagrama de dispersión, con el primer intento en el lado izquierdo. Los puntos naranjas son los puntos azules que son también los de menor costo visto hasta ahora. Esos son los que necesito para predecir.

Lo que me gustaría saber es una estimación de la probabilidad de la siguiente simulación produciendo un nuevo costo más bajo, así que puedo hacer un poco informado de la decisión de cuándo parar.

Este conjunto de datos se compone de 11,475 valores. Si desea que los datos reales o gráficos a partir de un conjunto de datos más grande o de otra carrera, hágamelo saber. Esto es parte de un programa que estoy escribiendo como un freetime proyecto; no es parte de una asignación.

EDIT: me imagino que todos los valores son independientes, ya que son ejecutadas en paralelo. Ellos toman la misma entrada, pero el uso de diferentes valores aleatorios.

Answer 1

A partir del diagrama de dispersión parece que los datos son independientes. (Hay muchas maneras de poner a prueba este: consultar información sobre los análisis de series de tiempo y las autocorrelaciones.) Suponiendo que este es el caso, la probabilidad de cualquier valor en un conjunto de $n$ de los valores (no sólo el último) al ser más pequeño no depende de cuando el valor producido. En consecuencia, todos los valores tienen la misma probabilidad de ser más pequeño. Suponiendo que no hay lazos para los más pequeños, que la oportunidad debe ser$1/n$, de modo que todas las posibilidades suma a la unidad, como probabilidades debe.

Como una aplicación, usted tiene $11,475$ valores. La próxima va a llevar a $n$$11475+1 = 11476$. Por lo tanto, la probabilidad de que se es el más pequeño es $1/11476$.

---

Por cierto, esta regla implica que el número esperado de nuevos mínimos entre dicha secuencia es de aproximadamente $\log(n)$. Los datos ilustrados parecen tener $9$ nuevos mínimos (se representan como puntos de naranja) y, de hecho,$\log(11475)\approx 9.35$. Una rápida simulación (teniendo diez segundos más o menos) nos da un sentido de la distribución de los números de los nuevos mínimos, que podría ser de algún interés (y tal vez ayudar a informar a la intuición).

Esta es la R código para producir una simulación.

N <- 1e4
sim <- apply(matrix(runif(11475 * N), ncol=N), 2, function(x) {
  y <- cummin(x)
  n <- length(y)
  sum(y[-1] != y[-n])
})
hist(sim, breaks=seq(min(sim)-1/2, max(sim)+1/2, by=1),
     xlab="# new minima", main="Histogram of Simulated Results")