El Problema de la secretaria

o del matrimonio ¿Cuando parar?

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 al menos 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  La solución muy bien explicada en dowrysol.pdf)
 

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)= p(ganar/(D=i))·p(D=i)

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

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

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

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

 La probabilidad de ganar es

  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
 

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

Designamos con p(37) el cociente

veces que ganamos / veces q realizamos el experimento

 

En la siguiente 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).

 


Consolación Ruiz Gil Febrero 2024  https://www.matsolin.com/secretaria/index.htm