Usuario:Solinruiz/El problema de secretaria

[[Categoría:Problemas de probabilidad]] [[Categoría:Decisiones óptimas]] [[Categoría:Métodos secuenciales]] [[Categoría:Teoría de la decisión]]

Supongamos que tenemos que elegir secretaria de entre 100 candidatas. Solo podemos entrevistar a cada persona una vez. Después de cada entrevista, hay que decidir si la contratamos o no. Si decidimos que no, perdemos la oportunidad para siempre. Si entrevistamos a 99 sin haber elegido, tenemos que contratar a la número 100. Cabría pensar que la probabilidad de contratar la secretaria ideal es de 1 entre 100, pero lo cierto es que podemos hacerlo mucho mejor.

Entrevistemos a la mitad de las personas y detengámonos después en la  siguiente mejor, es decir, la primera que sea mejor que la mejor de las ya entrevistadas. Una cuarta parte de las veces, la segunda mejor estará entre las 50 primeras y la mejor de todas en las 50 segundas. De manera que el 25 por ciento de las veces la regla de «parar en la siguiente mejor» dará como resultado contratar a la mejor secretaria.

Y es posible hacerlo aún mejor. John Gilbert y Frederick Mosteller, de la Universidad de Harvard, demostraron que es posible aumentar la probabilidad entrevistando a 37 personas y luego parando en la siguiente mejor que las 37 entrevistadas. La probabilidad de coger a la mejor secretaria con esta estrategia del 37 es  aproximadamente el 37% .El número 37 proviene de dividir 100 entre e, la base de los logaritmos naturales.  (El maravilloso mundo de las matemáticas pag 129  y por Mosteller en Fifty challenging problems in probability pag81 )

Solución

La estrategia es fijar un número k y después de la entrevista kª contrataremos a la próxima persona que mejore a las entrevistadas hasta entonces. Calcularemos la probabilidad de ganar con cada número k fijado y tomaremos el valor que maximice la probabilidad de ganar.

Fijamos pues un número k y calculemos ahora la probabilidad de ganar.

Sea D la posición de la secretaria ideal

p(ganar)= $\sum _{i=k+1}^{100}$ p(ganar/(D=i))·p(D=i)

Pues si i<=k, (ganar/(D=i))=0

Es fácil ver que p(D=i)=1/100

Ganaremos si la mejor secretaria hasta i-1 está entre las k primeras, pues sino la escogeremos y perderemos y por el mismo método que calculamos p(D=i)=1/100 , pues ahora concluimos que

p(ganar/(D=i))=k/(i − 1)

La probabilidad de ganar es

$\sum _{i=k+1}^{100}$ k/(i-1) · 1/100 = k/100 · (SA(100)-SA(k))

Designando por SA(m) la serie armónica hasta m:

1+1/2+1/3+ ... +1/m

sumas que se aproximan con el logaritmo neperiano

Así la probabilidad de ganar para n grande (en nuestro caso n=100) es aproximadamente

k/n · (ln(n)-ln(k)) = - k/n · (ln(k)-ln(n)) = - k/n · (ln(k/n))

Para maximizar esta función de k derivamos y igualamos a cero

-1/n ·  (ln(k/n)) - k/n · 1/n·n/k = 0

(ln(k/n)) + 1 = 0

k/n = 1/e

k = n/e

Simulación de experimento con JS Descartes

Realizamos el experimento y vamos calculando la probabilidad de ganar con la estrategia 37, es decir, entrevistamos a las 37 primeras y luego escogemos la primera que mejore a las 37 entrevistadas

Captura de la escena Descartes JS en función simulando los diversos casos de este problema

Designamos con p(37) el cociente

veces que ganamos / veces q realizamos el experimento

Enlace a la escena

Vemos un caso particular de distribución de las secretarias

Y en esta otra escena cada vez que se pulsa el triángulo se realizan 20 experimentos y se calcula para cada estrategia k el número de veces que gana entre en número de jugadas , p(k) . La gráfica muestra los puntos de abscisa k y ordenada p(k). Cuando jugamos muchas veces esta gráfica se pega a la de y=-x/100·ln(x/100).

Vemos cómo la gráfica de las p(k) se aproxima a la de -x/n·ln(x/n)

Enlaces externos y Bibliografía utilizada

• https://candes.su.domains/teaching/math2a/Hw/dowrysol.pdf (en inglés)
• El maravilloso mundo de las matemáticas New Scientist
• Fifty challenging problems in probability (Mosteller)