El problema de la secretaria mediante inducción hacia atrás
Inicio · Problema clásico · Simulaciones · Inducción hacia atrás · Variantes · Recursos · Cronología · Referencias · Acerca del sitio
El problema clásico de la secretaria
Una solución completa mediante inducción hacia atrás
Esta página deduce la estrategia óptima a partir de los principios básicos, usando la ecuación de valor
\[ V_n=\max\{U_n,W_n\}. \]
Aquí \(U_n\) es el valor de detenerse cuando aparece un récord, \(W_n\) es el valor de continuar y \(V_n\) es el valor óptimo.
1. Modelo y objetivo
Tenemos \(N\ge3\) aspirantes que llegan en un orden uniformemente aleatorio. Sus rangos absolutos son
\[ 1,2,\ldots,N, \]
donde el rango \(1\) corresponde al mejor.
Después de cada entrevista solo observamos el rango del aspirante respecto a los ya entrevistados. Contratar a alguien termina el proceso, y los rechazos son definitivos.
Sea \(X_k\) el rango absoluto del aspirante situado en la posición \(k\). Buscamos un tiempo de parada \(\tau\) que maximice
\[ \mathbb P(X_\tau=1). \]
La recompensa es \(1\) si se selecciona al mejor de todos y \(0\) en cualquier otro caso.
2. Rangos relativos y récords
Definimos el rango relativo del aspirante en la posición \(n\) mediante
\[ R_n = 1+\sum_{j=1}^{n-1} \mathbf 1_{\{X_j<X_n\}}. \]
El evento \(R_n=1\) significa que el aspirante en el instante \(n\) es mejor que todos los anteriores.
Un aspirante así establece un récord.
Un aspirante que no establece un récord no puede ser el mejor de todos. Por tanto, conviene continuar si quedan más aspirantes y el actual no es un récord. Solo cuando \(R_n=1\) detenerse puede dar una probabilidad positiva de éxito.
3. Uniformidad de los rangos relativos
Para una permutación uniformemente aleatoria, los rangos relativos
\[ R_1,R_2,\ldots,R_N \]
son independientes. Además,
\[ \mathbb P(R_n=j)=\frac1n, \qquad j=1,\ldots,n. \]
En particular,
\[ \mathbb P(R_n=1)=\frac1n. \]
Demostración
La transformación de la permutación de rangos absolutos
\[ (X_1,\ldots,X_N) \]
a la sucesión de rangos relativos
\[ (R_1,\ldots,R_N) \]
es una biyección.
Cada sucesión admisible de rangos relativos satisface
\[ R_n\in\{1,\ldots,n\}. \]
El número de sucesiones de este tipo es
\[ 1\cdot2\cdots N=N!, \]
que coincide con el número de permutaciones de rangos absolutos.
Como todas las permutaciones de rangos absolutos tienen la misma probabilidad, cada sucesión admisible de rangos relativos tiene probabilidad \(1/N!\). Por tanto,
\[ \begin{aligned} \mathbb P(R_1=r_1,\ldots,R_N=r_N) &=\frac1{N!}\\ &=\prod_{n=1}^{N}\frac1n. \end{aligned} \]
Esta factorización demuestra que los rangos relativos son independientes y que cada \(R_n\) es uniforme en \(\{1,\ldots,n\}\). \(\square\)
4. El valor de detenerse
Supongamos que el aspirante en el instante \(n\) establece un récord.
Como el mejor de todos necesariamente establece un récord,
\[ \mathbb P(X_n=1,\ R_n=1) = \mathbb P(X_n=1) = \frac1N. \]
Por el teorema de los rangos relativos,
\[ \mathbb P(R_n=1)=\frac1n. \]
En consecuencia, la probabilidad de éxito al detenerse ante un récord en el instante \(n\) es
\[ \begin{aligned} U_n &= \mathbb P(X_n=1\mid R_n=1)\\ &= \frac{\mathbb P(X_n=1,\ R_n=1)} {\mathbb P(R_n=1)}\\ &= \frac{1/N}{1/n}\\ &= \frac nN. \end{aligned} \]
Por tanto,
\[ \boxed{U_n=\frac nN}. \]
El valor de detenerse es estrictamente creciente en \(n\).
5. El valor de continuación
Sea \(W_n\) la probabilidad condicional óptima de éxito posterior después de rechazar al aspirante en el instante \(n\), dada la información de rangos relativos disponible. Por la independencia de los rangos relativos sucesivos, este valor depende de \(n\), pero no de los rangos relativos observados anteriormente.
Cuando se observa un récord, definimos
\[ \boxed{V_n=\max\{U_n,W_n\}}. \]
En el instante \(n+1\), el siguiente aspirante establece un récord con probabilidad
\[ \frac1{n+1}. \]
Si aparece un nuevo récord, podemos decidir de nuevo entre detenernos o continuar, y el valor es \(V_{n+1}\).
Con probabilidad
\[ \frac n{n+1}, \]
el aspirante no establece un récord. Detenerse no puede dar éxito; por ello, continuamos con valor \(W_{n+1}\).
En consecuencia,
\[ \boxed{ W_n = \frac{1}{n+1}V_{n+1} + \frac{n}{n+1}W_{n+1} }. \]
Así, las ecuaciones de Bellman son
\[ \boxed{ \begin{aligned} U_n&=\frac nN,\\ V_n&=\max\{U_n,W_n\},\\ W_n&= \frac{1}{n+1}V_{n+1} + \frac{n}{n+1}W_{n+1}. \end{aligned} } \]
6. Condición terminal
En el instante \(N\), aceptar a un aspirante que establece un récord garantiza el éxito. Después de rechazarlo ya no hay oportunidades. Si fuera obligatorio seleccionar a alguien en el instante \(N\), elegir a quien no establece récord produciría recompensa cero, sin modificar el valor.
Por tanto,
\[ U_N=1, \qquad V_N=1, \qquad W_N=0. \]
A partir de estos valores terminales, los valores anteriores se calculan mediante inducción hacia atrás.
7. Por qué la estrategia óptima tiene un umbral
De la recurrencia del valor de continuación,
\[ W_n = \frac{1}{n+1}V_{n+1} + \frac{n}{n+1}W_{n+1}. \]
Al restar \(W_{n+1}\) obtenemos
\[ W_n-W_{n+1} = \frac{V_{n+1}-W_{n+1}}{n+1}. \]
Como
\[ V_{n+1} = \max\{U_{n+1},W_{n+1}\} \ge W_{n+1}, \]
se obtiene
\[ W_n-W_{n+1}\ge0. \]
Por tanto,
\[ W_1\ge W_2\ge\cdots\ge W_N. \]
El valor de continuación \(W_n\) es no creciente, mientras que el valor de detenerse
\[ U_n=\frac nN \]
es estrictamente creciente.
Por ello, \(U_n-W_n\) es estrictamente creciente en \(n\). Una vez que aceptar un récord es óptimo, continúa siendo óptimo ante todos los récords posteriores. Esto demuestra que una estrategia óptima tiene forma de umbral.
Existe un entero \(r^*\) tal que la estrategia óptima consiste en:
- Rechazar a los primeros \(r^*\) aspirantes.
- Desde la posición \(r^*+1\), aceptar al primero que establezca un récord.
- Si no aparece otro récord, el intento fracasa.
En un instante \(n\) con récord, detenerse es óptimo cuando
\[ U_n\ge W_n. \]
Si hay igualdad, detenerse o continuar son igualmente óptimos. Resolvemos los empates a favor de detenerse.
8. Ejemplo completo: (N=10)
Resolvamos el problema con \(N=10\) sin suponer de antemano la existencia o el valor del umbral.
Comenzamos con
\[ U_{10}=1, \qquad V_{10}=1, \qquad W_{10}=0. \]
Después calculamos hacia atrás mediante
\[ W_n = \frac{1}{n+1}V_{n+1} + \frac{n}{n+1}W_{n+1}. \]
Los valores resultantes son:
| \(n\) | \(U_n\) | \(W_n\) | \(V_n\) | Decisión óptima |
|---|---|---|---|---|
| 10 | \(1\) | \(0\) | \(1\) | Detenerse |
| 9 | \(9/10\) | \(1/10\) | \(9/10\) | Detenerse |
| 8 | \(4/5\) | \(17/90\) | \(4/5\) | Detenerse |
| 7 | \(7/10\) | \(191/720\) | \(7/10\) | Detenerse |
| 6 | \(3/5\) | \(55/168\) | \(3/5\) | Detenerse |
| 5 | \(1/2\) | \(1879/5040\) | \(1/2\) | Detenerse |
| 4 | \(2/5\) | \(2509/6300\) | \(2/5\) | Detenerse |
| 3 | \(3/10\) | \(3349/8400\) | \(3349/8400\) | Continuar |
| 2 | \(1/5\) | \(3349/8400\) | \(3349/8400\) | Continuar |
| 1 | \(1/10\) | \(3349/8400\) | \(3349/8400\) | Continuar |
En el instante \(3\),
\[ U_3=\frac3{10} < \frac{3349}{8400} = W_3, \]
por lo que continuar es óptimo.
En el instante \(4\),
\[ U_4=\frac25 > \frac{2509}{6300} = W_4, \]
por lo que detenerse ante un récord es óptimo.
El cruce ocurre entre los instantes \(3\) y \(4\). Por tanto, la estrategia óptima rechaza a los primeros tres aspirantes y acepta al siguiente que establezca un récord:
\[ \boxed{r^*=3}. \]
La probabilidad óptima de éxito es
\[ \boxed{ V_1 = \frac{3349}{8400} \approx0.398690 }. \]
9. Probabilidad de éxito con un umbral fijo
Fijemos
\[ r\in\{1,\ldots,N-1\}. \]
Consideremos la estrategia que rechaza a los primeros \(r\) aspirantes y acepta al primer récord posterior.
Supongamos que el mejor de todos ocupa la posición \(k>r\). La estrategia lo selecciona exactamente cuando el mejor entre los primeros \(k-1\) aparece durante el periodo inicial de rechazo.
El mejor de todos tiene la misma probabilidad de ocupar cualquier posición; por tanto,
\[ \mathbb P(X_k=1)=\frac1N. \]
Condicionado a \(X_k=1\), el mejor de los primeros \(k-1\) aspirantes tiene la misma probabilidad de ocupar cualquiera de esas posiciones. Por tanto, la probabilidad de que ocupe una de las primeras \(r\) posiciones es
\[ \frac{r}{k-1}. \]
Al sumar sobre las posibles posiciones del mejor de todos obtenemos
\[ \begin{aligned} P_N(r) &= \sum_{k=r+1}^{N} \frac1N\frac{r}{k-1}\\ &= \frac rN \sum_{k=r+1}^{N}\frac1{k-1}. \end{aligned} \]
Al cambiar el índice de la suma se obtiene
\[ \boxed{ P_N(r) = \frac rN \sum_{j=r}^{N-1}\frac1j }. \]
Si \(r=0\), se acepta inmediatamente al primer aspirante, y
\[ P_N(0)=\frac1N. \]
Las cantidades \(W_r\) y \(P_N(r)\) tienen significados distintos.
El valor \(W_r\) es la probabilidad de éxito futuro si, después del instante \(r\), todas las decisiones se toman óptimamente.
En cambio, \(P_N(r)\) es la probabilidad de éxito de la estrategia de umbral fijo \(r\).
No necesariamente coinciden.
Por ejemplo, para \(N=10\),
\[ P_{10}(1) = \frac1{10}\sum_{j=1}^{9}\frac1j \approx0.2829, \]
mientras que
\[ W_1 = \frac{3349}{8400} \approx0.3987. \]
En el umbral óptimo,
\[ \boxed{ W_{r^*}=P_N(r^*)=V_1 }. \]
10. Caracterización exacta del umbral
Para \(r=1,\ldots,N-2\),
\[ P_N(r) = \frac rN \sum_{j=r}^{N-1}\frac1j \]
y
\[ P_N(r+1) = \frac{r+1}{N} \sum_{j=r+1}^{N-1}\frac1j. \]
Como
\[ P_N(r) = \frac rN \left( \frac1r+ \sum_{j=r+1}^{N-1}\frac1j \right), \]
al restar obtenemos
\[ \boxed{ P_N(r+1)-P_N(r) = \frac1N \left( \sum_{j=r+1}^{N-1}\frac1j-1 \right) }. \]
Se deduce que \(P_N(r)\) aumenta mientras
\[ \sum_{j=r+1}^{N-1}\frac1j>1 \]
y disminuye cuando la suma se vuelve menor que \(1\).
El menor umbral óptimo es
\[ \boxed{ r^* = \min \left\{ r\in\{1,\ldots,N-1\}: \sum_{j=r+1}^{N-1}\frac1j\le1 \right\}. } \]
Equivalentemente,
\[ \boxed{ \sum_{j=r^*+1}^{N-1}\frac1j \le1 \le \sum_{j=r^*}^{N-1}\frac1j. } \]
Si la suma del lado izquierdo de la caracterización es igual a \(1\), dos umbrales consecutivos son óptimos: \(r^*\) y \(r^*+1\). La definición anterior selecciona el menor umbral de rechazo, de acuerdo con la convención de detenerse en caso de empate. Se excluye \(r=0\) para \(N\ge3\), pues \(P_N(1)=H_{N-1}/N>1/N=P_N(0)\).
11. Regla asintótica de (1/e) rule
Para \(N\) grande, la suma armónica puede aproximarse mediante una integral:
\[ \sum_{j=r+1}^{N-1}\frac1j \approx \int_r^N\frac{dx}{x} = \log\frac Nr. \]
Así, la condición del umbral se aproxima por
\[ \log\frac N{r^*}=1. \]
Al despejar \(r^*\) obtenemos
\[ \boxed{ \frac{r^*}{N}\longrightarrow\frac1e }. \]
Usando la fórmula exacta de probabilidad,
\[ P_N(r^*) = \frac{r^*}{N} \sum_{j=r^*}^{N-1}\frac1j. \]
El primer factor tiende a \(1/e\) y la suma armónica tiende a \(1\). Por tanto,
\[ \boxed{ P_N(r^*)\longrightarrow\frac1e }. \]
Numéricamente,
\[ \frac1e\approx0.367879. \]
Cuando el número de aspirantes es grande:
- Rechaza aproximadamente a los primeros \(N/e\) aspirantes.
- Recuerda al mejor aspirante observado durante ese periodo.
- Acepta al primer aspirante posterior que supere a todos los anteriores.
Tanto la fracción óptima de rechazo como la probabilidad óptima de éxito tienden aproximadamente al \(37\%\).
12. Teorema general de inducción hacia atrás
El cálculo anterior es un caso particular, con horizonte finito, del teorema de la envolvente de Snell.
Para distinguir la teoría general de la notación del problema de la secretaria, denotemos por \(G_n\) un proceso de recompensa general y por \(Z_n\) su proceso de valor.
Sea
\[ G_1,G_2,\ldots,G_N \]
un proceso integrable adaptado a una filtración
\[ \mathcal F_1,\mathcal F_2,\ldots,\mathcal F_N. \]
Define
\[ Z_N=G_N \]
y, para \(n=N-1,\ldots,1\), definamos
\[ \boxed{ Z_n = \max \left\{ G_n, \mathbb E[Z_{n+1}\mid\mathcal F_n] \right\}. } \]
Entonces
\[ Z_n = \mathop{\mathrm{ess\,sup}}_{\tau\in\mathcal T_{n,N}} \mathbb E[G_\tau\mid\mathcal F_n], \]
donde \(\mathcal T_{n,N}\) es el conjunto de los tiempos de parada con valores en
\[ \{n,\ldots,N\}. \]
Un tiempo de parada óptimo a partir del instante \(n\) es
\[ \boxed{ \tau_n^* = \inf \{k\ge n:G_k=Z_k\}. } \]
Demostración
En el instante \(N\) es obligatorio detenerse. Por tanto,
\[ Z_N=G_N. \]
Supongamos que \(Z_{n+1}\) es el valor óptimo a partir del instante \(n+1\).
En el instante \(n\) hay dos alternativas.
Si nos detenemos, recibimos la recompensa \(G_n\).
Si continuamos, el mejor valor condicional alcanzable es
\[ \mathbb E[Z_{n+1}\mid\mathcal F_n]. \]
Por tanto, el valor óptimo es
\[ Z_n = \max \left\{ G_n, \mathbb E[Z_{n+1}\mid\mathcal F_n] \right\}. \]
La inducción hacia atrás demuestra la fórmula de valor en cada instante. Detenerse en el primer momento en que la recompensa inmediata coincide con el proceso de valor alcanza ese óptimo. \(\square\)
Relación con el problema de la secretaria
Para el problema de la secretaria, sea \(\mathcal F_n=\sigma(R_1,\ldots,R_n)\) la información disponible después de las primeras \(n\) entrevistas. Definimos la recompensa medible respecto de \(\mathcal F_n\) al seleccionar al aspirante en el instante \(n\) mediante
\[ G_n=\mathbb P(X_n=1\mid\mathcal F_n) =\frac nN\,\mathbf 1_{\{R_n=1\}}. \]
En efecto, un aspirante que no establece un récord no puede ser el mejor; si \(R_n=1\), la probabilidad condicional de éxito es \(n/N\). La independencia de los rangos relativos garantiza que las observaciones anteriores no modifican esta probabilidad.
Por la propiedad de la esperanza condicionada iterada, maximizar la recompensa condicional esperada \(G_\tau\) equivale a maximizar \(\mathbb P(X_\tau=1)\). En particular, el modelo que obliga a detenerse en \(N\) tiene la misma probabilidad óptima de éxito que aquel que permite no seleccionar a nadie si no aparece otro récord.
Cuando aparece un récord en el instante \(n\), la recompensa condicional de detenerse es \(U_n=n/N\) y el valor de continuar es \(W_n\). Por ello, la recurrencia de la envolvente de Snell se reduce a
\[ \boxed{V_n=\max\{U_n,W_n\}} \]
en los instantes con récord. Si no hay récord, detenerse da valor cero, por lo que conviene continuar mientras queden aspirantes. Estas son exactamente las decisiones usadas en la inducción hacia atrás anterior.
Referencias
La teoría general de inducción hacia atrás y parada óptima se desarrolla en Chow, Robbins, y Siegmund (1971), Shiryaev (2007) y Ferguson (2010).
Entre los trabajos históricos fundamentales sobre el problema de la secretaria se encuentran Ferguson (1989) y Gilbert y Mosteller (1966).