martes, 29 de mayo de 2018

El problema de la dote del sultán

Un sultán tiene 100 hijas y decide dar la mano de una de ellas al súbdito que supere la siguiente prueba: Cada hija desfilará delante del pretendiente indicando la dote que tiene asignada. El súbdito sólo podrá casarse con la hija de mayor dote si adivina cuál de ellas es. Para ello debe decidir si la elige o prefiere continuar viendo el resto. Una vez rechazada una de las hijas, la decisión no se  puede cambiar. Se supone que todas las dotes son distintas y que no tiene información previa sobre su cuantía.

¿Cuál es la mejor estrategia para superar la prueba?

Una estrategia es dejar pasar n hijas y después elegir aquella que tenga una dote que supere a todas las precedentes (incluidas las n primeras).  ¿Cuál es el número n que maximiza la probabilidad de elgir la dote más alta?
Supongamos que hay 3 hijas, cuyas dotes se numeran de mayor (1) a menor (3). En la tabla se muestran las diferentes ordenaciones y para qué valor de n se obtiene la dote mayor. Se observa que cuando se descarta una hija, se consigue la mayor dote en tres casos: p(n=1)=3/6=1/2.

La probabilidad de acertar con N hijas habiendo rechazado las n primeras es:
$$\frac{1}{N} \frac{n}{n+k}$$
ya que acertamos si la mayor está en el puesto n+1, que ocurre con probabilidad 1/N. También si la mayor está en el puesto n+k+1 que ocurre con probabilidad 1/N y la mayor de las n+k precedentes está entre las n primeras, que ocurre con probabilidad n/(n+k).

La probabilidad de acertar es la suma de estas probabilidades extendidas a todos los valores posibles de k, desde 0 hasta N-n-1: $$p=\frac{n}{N} \left( \frac{1}{n}+\frac{1}{n+1}+\frac{1}{n+2}+ \ldots +\frac{1}{N-1} \right)$$ 
Teniendo en cuenta la serie armónica:
$$H_n=1+\frac{1}{2}+\frac{1}{3}+\ldots + \frac{1}{n}$$
la probabilidad de acertar se puede expresar:
$$p=\frac{n}{N} \left(H_{N-1} - H_{n-1}\right)$$
Y como la serie armónica se puede aproximar con la fórmula que utiliza la constante de Euler-Mascheroni: $$H_n=ln(n)+\gamma$$ la probabilidad de éxito será: $$p=-\frac{n}{N}ln\left(\frac{n-1}{N-1}\right)$$
Cuando N y n son grandes, se puede aproximar a: $$p=-\frac{n}{N}ln\left(\frac{n}{N}\right)=-\alpha ln(\alpha)$$ Optimizando se obtiene: $$\alpha=\frac{n}{N}=\frac{1}{e}=0,3679\ldots$$ y por tanto habría que dejar pasar el 36,79% de las hijas antes de empezar a elegir una de ellas.

Descargar .XLS
Sigue las instrucciones de utilización del modelo de Excel que puedes descargar a continuación:
  • Con las flechas se elige el número de novias descartadas n.
  • Con el botón 'elige' se muestran las siguientes dotes, deteniéndose si una dote supera a las anteriores y se habilita el botón 'comprobar'.
  • El botón 'comprobar' muestra las dotes ocultas y se comprueba si ha habido éxito.
  • Con las flechas se elige el número de novias N y el número de novias descartadas n.
  • Se observa numérica y gráficamente las probabilidades de éxito para cada supuesto.

No hay comentarios: