He leído sobre este problema:
http://en.wikipedia.org/wiki/Secretary_problem
Pero quiero ver cómo se demuestra que la solución "óptima" es realmente óptima. Entiendo cómo se demuestra que si la solución óptima es de la forma "esperar a $t$ candidatos y luego elegir el siguiente mejor" entonces $t=n/e$ es óptima; pero ¿por qué la mejor estrategia es de esa forma en primer lugar?
No se requiere una prueba completa - una referencia a un buen texto que discute esto es bueno también.
Como se trata de un todo o nada, no tiene sentido seleccionar a un candidato que no sea el mejor hasta el momento.
Si hay $n$ candidatos en total y el $k$ es el mejor hasta el momento, entonces la probabilidad de que el $k$ El mejor candidato en general es $\frac{k}{n}$ que es una función creciente de $k$ .
Así que si tienes un método de decisión que selecciona el $k$ El candidato que mejor se comporta hasta el momento, pero que no es el $m$ a la mejor candidata hasta el momento, con $k \lt m$ entonces un método de decisión mejor (o, en un caso extremo, no peor) sería no seleccionar el $k$ candidato cuando es mejor hasta el momento, sino para seleccionar el $m$ El candidato que mejor se ha comportado hasta ahora.
Por lo tanto, en un método óptimo, si en cualquier etapa cuando usted está dispuesto a seleccionar un mejor candidato hasta el momento, usted debe estar dispuesto a seleccionar cualquier posterior mejor candidato hasta el momento. Esto da lugar a la estrategia en su pregunta de no seleccionar hasta un punto y luego seleccionar cualquier candidato mejor hasta el momento después de ese punto.
Hay un caso extremo: por ejemplo, si hay dos candidatos, da igual aceptar al primero o esperar a ver al segundo.
Según tengo entendido, cuando se entrevista a un candidato $k$ puedes sólo deciden contratar $k$ o esperar a ver si aparece alguien mejor.
Esto es simplemente una reformulación de la respuesta de Henry. Probablemente sea totalmente inútil volver a dar la misma prueba con diferentes palabras, así que lo hago en la comunidad-wiki.
Recordemos el problema de la secretaria: En cada momento $k$ Si quieres decidir si eliges al candidato $k$ o no. Ganas si el candidato que eliges es el mejor de todos $n$ candidatos, y quieres maximizar la probabilidad de ganar.
Ahora bien, tenga en cuenta que en cualquier momento $k$ , si el candidato $k$ no es el mejor entre los candidatos $1, \dots, k$ Si eliges al candidato, pierdes inmediatamente. (Este candidato ni siquiera es el mejor entre los vistos en ese momento, por lo que no puede ser el mejor entre todos los candidatos). Así que sólo escogerás a una candidata si es la mejor entre las vistas hasta ese momento. Así, cualquier estrategia óptima será de la forma que haga, en cada momento $k$ :
Si el candidato $k$ es mejor que todos los vistos anteriormente y [algunas condiciones adicionales], elija el candidato $k$ y parar.
Las "[algunas condiciones adicionales]" deben depender sólo de la información que se tenga hasta el momento $k$ y, en particular, sólo en $k$ y el orden relativo de los candidatos $1$ a $k$ . Pero como lo único que te importa es si eliges al mejor candidato o no, el único factor relevante del orden relativo es quién es el mejor entre los vistos en ese momento, y eso ya sabes que es candidato $k$ . Así que el "[algunas condiciones adicionales]" es algún predicado $P(k)$ que depende sólo de $k$ .
Ahora tenga en cuenta que si elige el candidato $k$ (quién es el mejor entre $1$ a $k$ ), entonces la probabilidad de ganar es $k/n$ (la probabilidad de que el mejor estuviera entre los primeros $k$ ). Se trata de una función creciente de $k$ lo que significa que si $k$ es bueno también lo es $k+1$ (es decir, si $P(k)$ es verdadera, entonces también debería serlo $P(k+1)$ ser). Así que $P(k)$ es de la forma $[k \ge t]$ es decir, la gama de bienes $k$ es un intervalo $\{t, \dots, n\}$ para algunos $t$ .
Esto es lo que se quería demostrar. (Y como Henry observó, para el caso especial $n=2$ , ambos $t=1$ y $t=2$ trabajo, pero para mayores $n$ puede demostrar que $t$ debe ser $n/e$ .)
Un documento relevante mediante programación lineal. Hace referencia a Dynkin y Lindley con respecto a la prueba de optimalidad. En concreto:
Dynkin, E. B. 1963. La elección óptima del instante de detención de un proceso de Markov. Sov. Math. Dokl. 4.
Lindley, D. V. 1961. Programación dinámica y teoría de la decisión. Applied Statistics 10, 39-51.
Un extracto del documento de Dynkin.
Y un enlace al documento de Lindley.
Este PDF tiene alguna información histórica sobre el problema.
Este parece una discusión bastante buena del problema, también (e incluso hace referencia al documento vinculado).
Y, desde una perspectiva más general, la teoría de la parada óptima es obviamente relevante.
No creo que estos enlaces contengan una prueba de la optimalidad de la solución del problema básico...
No, no parece que lo demuestren directamente, pero el documento histórico tiene una sección de referencias bastante extensa. Por desgracia, todo el asunto parece un poco envuelto en leyendas y habladurías, si se me permite la hipérbole.
@Jack: El historia puede estar envuelto, pero si la afirmación ha sido probada, debería ser posible dar una prueba clara ahora.
La misma página de Wikipedia cita a Bruss "Suma las probabilidades a uno y para" , Annals of Probability 28:3 (2000), pp. 1384-1391. De acceso libre, por lo que no hay problemas para conseguir el artículo. Sin embargo, es bastante pesado.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
1 votos
Estrictamente "elegir al próximo candidato que sea mejor que los ya vistos"