La regla del 37 %

Los candidatos llegan de uno en uno, en orden aleatorio. Puedes comparar a cada uno con los anteriores, pero debes aceptarlo o rechazarlo en el momento, sin posibilidad de volver atrás. Decide cuántos descartar de entrada; la regla elige después al primer candidato que supere a todos los descartados.

Probabilidad de elegir al mejor descartando k	$P(k)=\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}$
Corte óptimo para n grande	$k^*\approx\frac{n}{e}$
Probabilidad con ese corte	$P(k^*)\to\frac{1}{e}\approx0.3679$

Ejemplo resuelto — La regla del 37 %

Probabilidad de elegir al mejor descartando 4	39,84%
Punto de corte óptimo k*	4
Probabilidad de elegir al mejor con k*	39,84%
n/e, como comparación	4,05
Probabilidad de elegir al mejor al azar	9,09%
Probabilidad de llegar al último candidato	40%

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Lección

La teoría — La regla del 37 %

En el problema de la secretaria, n candidatos llegan en orden aleatorio. Solo puedes comparar a cada uno con los anteriores y debes aceptarlo o rechazarlo en el momento, sin posibilidad de cambiar de decisión. La regla del punto de corte descarta a los primeros k y acepta después al primero que supere a todos ellos.

De dónde viene la fórmula

Distingue los casos según dónde esté el mejor. Llama B a la posición de llegada del mejor candidato y W al suceso de elegirlo. Todos los valores de B entre 1 y n son igual de probables.
$P(B=i)=\frac{1}{n},\qquad i=1,\dots,n$
Si el mejor está entre los primeros k, lo pierdes. La regla no permite volver atrás, así que esas posiciones no aportan nada.
$B\le k:\quad P(W\mid B)=0$
Si el mejor llega en la posición i > k, solo puedes elegirlo si no has aceptado a nadie entre k + 1 e i − 1. Esto ocurre exactamente cuando el mejor de los primeros i − 1 está entre los primeros k: solo así ninguno de los candidatos intermedios supera la referencia. Cualquiera de esos i − 1 candidatos tiene la misma probabilidad de ser el mejor.
$B=i>k:\quad P(W\mid B=i)=\frac{k}{i-1}$
Suma las probabilidades de todas las posiciones.
$P(k)=\sum_{i=k+1}^{n}\frac{1}{n}\cdot\frac{k}{i-1}=\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}$
Haz crecer n. Con x = k/n, la suma se convierte en una integral y la probabilidad tiende a −x ln x. Su derivada, −ln x − 1, se anula en x = 1/e, donde la probabilidad es 1/e ≈ 36,79 %.
$P\approx x\int_{x}^{1}\frac{dt}{t}=-x\ln x,\qquad\frac{d}{dx}\left(-x\ln x\right)=-\ln x-1=0\iff x=\frac{1}{e}$

Supone: Solo ves las posiciones relativas, nunca las puntuaciones; todos los órdenes de llegada son igual de probables; no puedes recuperar a un candidato descartado y quien recibe la oferta siempre la acepta; elegir a cualquiera que no sea el mejor cuenta como un fracaso.

Problemas resueltos al detalle

Tres candidatos: todos los órdenes 3 pasos
Tres candidatos llegan en orden aleatorio. Representa cada orden mediante los puestos de los candidatos según van llegando (1 = mejor). Si descartas al primero y eliges después al primero que supere a todos los anteriores, ¿en cuántos de los seis órdenes eliges al mejor? Comprueba el resultado con la fórmula.

Abre este problema en la herramienta
1. Los seis órdenes:
  
  $123,\quad 132,\quad 213,\quad 231,\quad 312,\quad 321$
2. El primer candidato fija la referencia. En 213 y 231, el mejor supera al 2; en 312, el 1 llega en segundo lugar y resulta elegido. En 123 y 132, nadie supera al 1 descartado, así que la regla elige al último; en 321, el 2 supera al 3 y resulta elegido antes de que llegue el 1:
  
  $213\to1,\quad 231\to1,\quad 312\to1;\qquad 123\to3,\quad 132\to2,\quad 321\to2$
3. La fórmula con n = 3 y k = 1:
  
  $P(1)=\frac{1}{3}\left(\frac{1}{1}+\frac{1}{2}\right)=\frac{1}{3}\cdot\frac{3}{2}=\frac{1}{2}$
Respuesta

En 3 de los 6 órdenes: una probabilidad de 1/2, frente a 1/3 si eliges al primer candidato.

$P(1)=\frac{3}{6}=\frac{1}{2}>\frac{1}{3}=P(0)$
Cuatro candidatos: todos los cortes 2 pasos
Con cuatro candidatos, calcula la probabilidad de elegir al mejor para cada punto de corte k = 0, 1, 2, 3 y encuentra el corte óptimo.

Abre este problema en la herramienta
Mostrar solución
1. Con k = 0 eliges al primer candidato, que es el mejor con probabilidad 1/4. Para k ≥ 1, utiliza la fórmula:
  
  $P(1)=\frac{1}{4}\left(1+\frac{1}{2}+\frac{1}{3}\right)=\frac{11}{24},\quad P(2)=\frac{2}{4}\left(\frac{1}{2}+\frac{1}{3}\right)=\frac{5}{12},\quad P(3)=\frac{3}{4}\cdot\frac{1}{3}=\frac{1}{4}$
2. Compara los cuatro resultados:
  
  $P(0)=\frac{6}{24},\quad P(1)=\frac{11}{24},\quad P(2)=\frac{10}{24},\quad P(3)=\frac{6}{24}$
Respuesta

Descarta al primero y elige después al primero que lo supere: 11/24 ≈ 45,83 %.

$k^*=1,\qquad P(1)=\frac{11}{24}\approx0.4583$
Las once candidatas de Kepler 3 pasos
En 1611, Johannes Kepler empezó a buscar una segunda esposa y, a lo largo de casi dos años, consideró a once candidatas. Si aplicas la regla del punto de corte con n = 11, ¿cuál es el corte óptimo, qué probabilidad ofrece y cuál es la primera candidata que la regla puede elegir?

Abre este problema en la herramienta
Mostrar solución
1. Evalúa la fórmula en torno a n/e = 11/e ≈ 4,05:
  
  $P(4)=\frac{4}{11}\left(\frac{1}{4}+\frac{1}{5}+\dots+\frac{1}{10}\right)=\frac{4}{11}\times1.0956=0.3984$
2. La probabilidad máxima se alcanza con k = 4; con k = 3 y k = 5 es menor:
  
  $P(3)=\frac{3}{11}\left(\frac{1}{3}+\dots+\frac{1}{10}\right)=0.3897,\qquad P(5)=\frac{5}{11}\left(\frac{1}{5}+\dots+\frac{1}{10}\right)=0.3844$
3. Si descartas a las cuatro primeras, la quinta es la primera candidata que la regla puede aceptar. Kepler se casó con la quinta, aunque no siguió esta regla: según el relato que hace Ferguson de su carta, después de conocer a la quinta lo convencieron para que se declarase a la cuarta; ella lo rechazó y él volvió atrás. La regla no permite volver atrás.
Respuesta

Descarta a las cuatro primeras: la probabilidad es del 39,84 % y la quinta es la primera candidata que la regla puede elegir.

$k^*=4,\qquad P(4)\approx0.3984$
Muchos candidatos: de dónde sale 1/e 3 pasos
Para n grande, expresa la proporción descartada como x = k/n y encuentra el valor óptimo de x y la probabilidad que ofrece. Contrasta después el resultado con n = 100.

Abre este problema en la herramienta
Mostrar solución
1. La suma es una suma de Riemann de 1/t en [x, 1]:
  
  $\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}=x\sum_{j=k}^{n-1}\frac{1}{n}\cdot\frac{1}{j/n}\approx x\int_{x}^{1}\frac{dt}{t}=-x\ln x$
2. Iguala la derivada a cero:
  
  $\frac{d}{dx}\left(-x\ln x\right)=-\ln x-1=0\ \Rightarrow\ x=\frac{1}{e},\qquad -\frac{1}{e}\ln\frac{1}{e}=\frac{1}{e}\approx0.3679$
3. Para n = 100, n/e ≈ 36,79, y el corte óptimo exacto es 37:
  
  $P(36)=0.37101,\qquad P(37)=0.37104,\qquad P(38)=0.37080$
Respuesta

Descarta una proporción 1/e ≈ 36,79 %; la probabilidad tiende a 1/e. Con n = 100, el corte óptimo es 37 y la probabilidad es del 37,1 %.

$x^*=\frac{1}{e},\qquad P\to\frac{1}{e}\approx0.3679;\qquad n=100:\ k^*=37,\ P(37)\approx0.3710$
Quedarte con el último candidato 3 pasos
Tienes cien candidatos y descartas a los primeros 37. Calcula la probabilidad de que el mejor esté entre los descartados, la de llegar al último candidato y la de llegar al último y que sea el mejor.

Abre este problema en la herramienta
Mostrar solución
1. El mejor tiene la misma probabilidad de estar en cualquier posición, así que la probabilidad de que esté entre los primeros 37 es:
  
  $\frac{k}{n}=\frac{37}{100}=0.37$
2. El proceso llega al candidato 100 exactamente cuando no se acepta a ninguno del 38 al 99, es decir, cuando el mejor de los primeros 99 está entre los primeros 37:
  
  $\frac{k}{n-1}=\frac{37}{99}\approx0.3737$
3. La diferencia corresponde al caso en que el proceso llega al final y el último candidato es el mejor:
  
  $\frac{37}{99}-\frac{37}{100}=\frac{37}{9900}\approx0.0037$
Respuesta

37 %, 37,37 % y 0,37 %: más de un proceso de cada tres termina eligiendo al último candidato, y casi nunca porque sea el mejor.

$0.37,\qquad 0.3737,\qquad 0.0037$
El menor puesto esperado con tres candidatos 3 pasos
Con tres candidatos, ahora buscas minimizar el puesto esperado (1 = mejor), en lugar de maximizar la probabilidad de elegir al mejor. Encuentra la regla óptima por inducción hacia atrás y calcula su puesto esperado.

Abre este problema en la herramienta
Mostrar solución
1. Un candidato que llega en la posición i y ocupa el puesto j entre los vistos hasta entonces tiene un puesto esperado de j(n + 1)/(i + 1) en el conjunto de candidatos. Al tercero debes aceptarlo; su puesto esperado es (n + 1)/2:
  
  $\frac{j(n+1)}{i+1}=\frac{4j}{i+1},\qquad c_2=\frac{3+1}{2}=2$
2. Acepta al segundo si su puesto esperado es como máximo 2; en caso contrario, continúa:
  
  $i=2:\ \ j=1:\ \tfrac{4}{3}<2,\quad j=2:\ \tfrac{8}{3}>2;\qquad c_1=\frac{1}{2}\left(\frac{4}{3}+2\right)=\frac{5}{3}$
3. Aceptar al primero da un puesto esperado de 2, mayor que 5/3, así que continúa:
  
  $i=1:\ \ \frac{4}{2}=2>\frac{5}{3}\ \Rightarrow\ c_0=c_1=\frac{5}{3}$
Respuesta

Descarta al primero; acepta al segundo si supera al primero y, en caso contrario, acepta al tercero. El puesto esperado es 5/3 ≈ 1,67. Con tres candidatos, esta es exactamente la regla del punto de corte con k = 1.

$c_0=\frac{5}{3}\approx1.6667$
Dos candidatos con puntuaciones visibles 2 pasos
Dos candidatos tienen puntuaciones independientes con distribución uniforme entre 0 y 1. Ves cada puntuación cuando llega el candidato. Encuentra la regla que elige con mayor probabilidad la puntuación más alta y calcula esa probabilidad. Compárala con la que puedes conseguir si solo conoces las posiciones relativas.

Abre este problema en la herramienta
Mostrar solución
1. Si descartas al primero, cuya puntuación es x, debes aceptar al segundo. Aciertas cuando su puntuación es mayor, lo que ocurre con probabilidad 1 − x. Si aceptas al primero, aciertas cuando la puntuación del segundo es menor: la probabilidad es x.
  
  $S(x)=x,\qquad C(x)=1-x;\qquad S(x)\ge C(x)\iff x\ge\tfrac{1}{2}$
2. Por tanto, acepta al primero cuando x ≥ 1/2. Calcula la media sobre x:
  
  $\int_{0}^{1/2}(1-x)\,dx+\int_{1/2}^{1}x\,dx=\frac{3}{8}+\frac{3}{8}=\frac{3}{4}$
Respuesta

Acepta al primero si su puntuación es al menos 1/2: la probabilidad es 3/4. Si solo conoces las posiciones relativas, con dos candidatos la probabilidad es 1/2, decidas lo que decidas.

$P=\frac{3}{4}>\frac{1}{2}$

Problemas complementarios, solo con la respuesta

Con cinco candidatos, encuentra el corte óptimo y su probabilidad.

Mostrar respuesta

Descarta a los dos primeros: 13/30 ≈ 43,33 %.

$k^*=2,\qquad P(2)=\frac{2}{5}\left(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\right)=\frac{13}{30}\approx0.4333$
Con dos candidatos y solo sus posiciones relativas, demuestra que cualquier regla elige al mejor la mitad de las veces.

Mostrar respuesta

Si aceptas al primero, aciertas con probabilidad 1/2; si lo descartas, debes aceptar al segundo, también con probabilidad 1/2.

$P(0)=\frac{1}{2},\qquad P(1)=\frac{1}{2}\cdot\frac{1}{1}=\frac{1}{2}$
Con diez candidatos y el corte óptimo, calcula la probabilidad de que el mejor esté entre los descartados y la de llegar al último candidato.

Mostrar respuesta

k = 3: 30 % y 3/9 ≈ 33,33 %.

$k^*=3:\quad\frac{3}{10}=0.3,\qquad\frac{3}{9}\approx0.3333$
En el límite cuando n crece, calcula la probabilidad de elegir al mejor si descartas un quinto de los candidatos y si descartas tres quintos.

Mostrar respuesta

−0,2 ln 0,2 ≈ 32,19 % y −0,6 ln 0,6 ≈ 30,65 %.

$-0.2\ln0.2\approx0.3219,\qquad-0.6\ln0.6\approx0.3065$
Con cuatro candidatos, calcula el menor puesto esperado que puede conseguir una regla.

Mostrar respuesta

15/8 = 1,875.

$c_0=\frac{15}{8}=1.875$

Descartar un cuarto o la mitad: la misma probabilidad

La curva se aplana cerca del máximo, y eso hace que la regla sea fácil de aplicar. Pulsa Descarta un cuarto: 35,04 %. Pulsa Descarta la mitad: 34,91 %. Para cien candidatos, el corte óptimo es 37 y da un 37,1 %; descartar entre un cuarto y la mitad te cuesta, por tanto, como mucho 2,2 puntos. Cuando n crece, la curva tiende a −x ln x, donde x es la proporción descartada. En un cuarto y en la mitad toma exactamente el mismo valor, porque ¼ ln 4 = ½ ln 2 ≈ 34,66 %. No necesitas conocer n con gran precisión: aunque lo estimes un tercio por encima o por debajo de su valor real, si descartas el 37 % de tu estimación, para n grande conservas una probabilidad de al menos el 34,5 %.

Si solo buscas al mejor, más de un tercio de las veces te quedas con el último

La regla lo apuesta todo al mejor candidato. Cuando está entre los descartados, algo que ocurre el 37 % de las veces con cien candidatos, ninguno de los siguientes puede superar la referencia. El proceso llega hasta el final y elige a quien aparezca en último lugar. Pulsa Cien, descarta 37: el puesto esperado del candidato elegido es 20,01. En 1964, Chow, Moriguti, Robbins y Samuels buscaron una regla que minimizara el puesto esperado. Su regla puede aceptar a un candidato que esté cerca de la cabeza entre los vistos hasta entonces, con un criterio que se vuelve menos exigente a medida que quedan menos por llegar. Para n = 100, su puesto esperado es 3,60. Se mantiene por debajo de 4 para todos los valores de n de esta página y tiende a 3,8695; el de la regla del 37 % sigue creciendo con n y llega a 185,54 con mil candidatos.

Si ves las puntuaciones, la probabilidad sube al 58 %

La regla del 37 % solo utiliza posiciones relativas: quién supera a quién. Supón ahora que ves la puntuación de cada candidato y conoces la distribución de las puntuaciones, por ejemplo, uniforme entre 0 y 1. Gilbert y Mosteller resolvieron esta versión en 1966. Desaparece la fase inicial de observar sin elegir. Desde el primer candidato puedes aceptar a cualquiera que sea el mejor hasta ese momento y cuya puntuación supere cierto umbral. Ese umbral baja a medida que quedan menos candidatos: 0,5 cuando queda uno por llegar, 0,6899 cuando quedan dos y 0,9240 cuando quedan diez. La probabilidad de elegir al mejor es del 60,6 % con once candidatos y del 58,29 % con cien; tiende al 58,02 %, frente al 36,79 % que obtienes con las posiciones relativas. Saber reconocer una buena puntuación aporta unos 21 puntos.

Ruta de aprendizaje

Decidir a partir de lo que ves

Referencias (4)

The problem as now studied (n known, random order, relative ranks only, no recall, only the best counts), the cutoff rule and its chance, and the history the page uses: Kepler, after losing his first wife in 1611, spent nearly two years over at least eleven candidates, described in a letter to Baron Strahlendorf of 23 October 1613; friends persuaded him to propose to the fourth after he met the fifth, the fourth turned him down, and he chose the fifth. Ferguson notes that for n = 11 the rule's chance is largest when the fifth is the first candidate it may take, and that Kepler's recall breaks the problem's assumptions: T. S. Ferguson, Who solved the secretary problem? Statistical Science 4(3), 282–289 (1989). doi:10.1214/ss/1177012493
The classical secretary problem solved by backward induction, the limits the page quotes in insight blocks 2 and 3: the least expected rank tends to 3.8695 (Chow, Moriguti, Robbins and Samuels), and with the values revealed and their distribution known the chance of the best tends to 0.58016 (Gilbert and Mosteller), 'to be compared to the limiting value e⁻¹ when the intrinsic values are not revealed': T. S. Ferguson, Optimal Stopping and Applications, Chapter 2, Finite Horizon Problems, §§2.1–2.3. Mathematics Department, UCLA (online text).
The rank-minimising rule of insight block 2 and solved problem 6: accept a candidate whose relative rank is within a threshold that rises as the candidates run out, with expected rank tending to 3.8695: Y. S. Chow, S. Moriguti, H. Robbins and S. M. Samuels, Optimal selection based on relative rank (the "secretary problem"). Israel Journal of Mathematics 2(2), 81–90 (1964). doi:10.1007/BF02759948
The full-information problem of insight block 3 and solved problem 7: values seen, independent with a known distribution; the optimal rule takes a best-so-far above a threshold that depends on how many remain, and the chance of the best tends to 0.5802: J. P. Gilbert and F. Mosteller, Recognizing the maximum of a sequence. Journal of the American Statistical Association 61(313), 35–73 (1966). doi:10.1080/01621459.1966.10502008

Por el equipo de 7 Raven Room · Contrastado con fuentes publicadas. Se agradecen correcciones.

La regla del 37 %

De dónde viene la fórmula

Problemas complementarios, solo con la respuesta

Descartar un cuarto o la mitad: la misma probabilidad 🖖

Si solo buscas al mejor, más de un tercio de las veces te quedas con el último 🖖

Si ves las puntuaciones, la probabilidad sube al 58 % 🖖

Descartar un cuarto o la mitad: la misma probabilidad

Si solo buscas al mejor, más de un tercio de las veces te quedas con el último

Si ves las puntuaciones, la probabilidad sube al 58 %