Muestrear dos números del 1 al 10; maximizar el producto esperado

Question

Supongamos que toma una muestra de dos números, extraídos al azar del 1 al 10; podría elegir dos estrategias: 1) elegir con reemplazo y 2) elegir sin reemplazo. ¿Qué estrategia preferirías para maximizar el producto esperado?

Me encontré con este problema mientras preparaba una entrevista. Mi intuición es que elegir con reemplazo sería mejor. Sin embargo, me pareció demasiado complejo utilizar el método de fuerza bruta para probarlo. ¿Alguien podría sugerir un enfoque mejor?

Answer 1

Sugerencia: Observe la relación entre $E[XY]$ y la covarianza. Ahora piensa en el signo de la covarianza -o si lo prefieres en esos términos, el signo de la correlación servirá- bajo los dos esquemas de muestreo (es cero bajo uno pero claramente no bajo el otro, teniendo en cuenta que aquí estamos tomando $X$ y $Y$ como los valores de los dos sorteos). La solución para maximizar $E[XY]$ es inmediato.

Esto suena como el tipo de cosa que uno podría encontrar en una de esas entrevistas en las que intentan hacerte alguna pregunta impar y ver qué haces con ella -- normalmente hay un atajo que evita el cálculo explícito; éste definitivamente tiene un atajo. Al darse cuenta de la conexión entre $E[XY]$ y $\text{Cov}[XY]$ y luego la conexión con los dos métodos de muestreo, uno debería ser capaz de responder en cuestión de segundos, y justificarlo.

---

Parece que una mayor explicación puede ser útil. Estas son las ideas en cuestión.

1. Las expectativas incondicionales no cambian tanto si se utiliza con sustitución como sin ella. Es decir $E[Y]=E[X]$ * en ambos regímenes.

2. Si se muestrea sin reemplazo, la covarianza debe ser negativa porque cuando se toma un valor por debajo de la media de la población, ahora hay más valores disponibles por encima de la media de la población que por debajo para la segunda extracción, y viceversa. Es decir, es más probable que el segundo valor esté en el lado opuesto de la media del primer valor que en el mismo lado, de manera que la covarianza será negativa en este caso.

3. $E[XY] = E[X]E[Y]+\text{Cov}[X,Y]$

   Con el reemplazo, la covarianza es 0 y $E[XY]=E[X]E[Y]$

   Sin reemplazo, la covarianza es <0 y $E[XY] < E[X]E[Y]$

---

* Si esto no parece obvio, considere el siguiente experimento mental: Tomo una baraja de cartas numeradas del 1 al 10 y las barajo minuciosamente, colocando la baraja boca abajo sobre la mesa. La persona A tomará la primera carta y la persona B la segunda. Pero ahora la persona B pide que ampliemos la baraja un poco más e intercambiemos las posiciones de las dos cartas superiores. Evidentemente, este último paso no cambia la distribuciones experimentado por A y B (el paso adicional de mezcla no lo hace menos aleatorio). Así que B debe experimentar la misma distribución bajo ambos esquemas, y por lo tanto B tiene la misma distribución (incondicional) que A - no importa si se toma la primera o la segunda carta. Así pues, es evidente, $E[Y]=E[X]$ .

(Naturalmente, sin embargo, si B observa lo que obtuvo A antes del sorteo, la distribución condicional de B y, por tanto, la expectativa condicional $E[Y|X=x]$ se ve afectado por el valor específico de $x$ . Esta no es la situación que estamos tratando, ya que estábamos tratando de encontrar la expectativa incondicional $E[Y]$ .)

Answer 2

Si no consigues el truco de la covarianza inteligente de Glen B, también podrías considerar el siguiente enfoque que es un nivel de abstracción inferior

• Paso 1: considere la posibilidad de calcular por la vía difícil sumando todos los términos de 10 en 10 de una tabla $$\frac{1}{100}\sum_{x_1=1}^{10}\sum_{x_2=1}^{10} x_1 \cdot x_2 = E[X]^2 = 5.5^2$$

  $$\begin{array}{cccccccccc} 1&2&3&4&5&6&7&8&9&10\\ 2&4&6&8&10&12&14&16&18&20\\ 3&6&9&12&15&18&21&24&27&30\\ 4&8&12&16&20&24&28&32&36&40\\ 5&10&15&20&25&30&35&40&45&50\\ 6&12&18&24&30&36&42&48&54&60\\ 7&14&21&28&35&42&49&56&63&70\\ 8&16&24&32&40&48&56&64&72&80\\ 9&18&27&36&45&54&63&72&81&90\\ 10&20&30&40&50&60&70&80&90&100 \end{array}$$

• Paso 2: sin sustitución se obtiene una suma similar pero sin los términos donde $x_1=x_2$ .

  $$\begin{array}{cccccccccc} &2&3&4&5&6&7&8&9&10\\ 2&&6&8&10&12&14&16&18&20\\ 3&6&&12&15&18&21&24&27&30\\ 4&8&12&&20&24&28&32&36&40\\ 5&10&15&20&&30&35&40&45&50\\ 6&12&18&24&30&&42&48&54&60\\ 7&14&21&28&35&42&&56&63&70\\ 8&16&24&32&40&48&56&&72&80\\ 9&18&27&36&45&54&63&72&&90\\ 10&20&30&40&50&60&70&80&90& \end{array}$$

  Entonces un truco para responder a la pregunta es analizar sólo la diferencia de esta diagonal con la media del paso anterior. La pregunta es si la media de esta diagonal $E[X^2]$ es inferior o menor que $E[X]^2 = 5.5^2$ . Desde $E[X^2] = E[X]^2 + VAR[X] > E[X]^2$ se obtiene que la diagonal tiene una contribución superior a la media y dejarla fuera reduciría la expectativa del resultado (por lo que se obtiene el resultado más alto cuando se utiliza el reemplazo, y se deja la diagonal en el sorteo).

He aquí una forma sencilla de calcularlo con fuerza bruta en R

n = 10

### generate a matrix of the outer product
M = outer(1:n,1:n, FUN = "*")

### make a second matrix but with the diagonal zero
M2 = M
diag(M2) = NA

### with replacement 30.25
mean(M)
### without replacement (no diagonal) 29.3333
mean(M2, na.rm = TRUE)

Answer 3

He aquí una aproximación intuitiva al problema. Supongamos que el primer número que elegimos es un 1 - obviamente sería mejor elegir el segundo número sin sustitución, con el fin de eliminar la posibilidad de obtener otro 1. Supongamos que el primer número que elegimos es un 10: obviamente, sería mejor elegir el segundo número con sustitución, para permitir la posibilidad de conseguir otros 10. Se puede extender esta lógica para ver que si elegimos un número por encima de la media de 5,5, preferimos elegir con reemplazo, pero si elegimos por debajo de la media, preferimos elegir sin reemplazo.

Hay 5 números por encima de la media y 5 por debajo, por lo que hay un número igual de casos en los que preferiríamos una estrategia frente a la otra, todos ellos equiprobables. Pero la diferencia está en el valor del producto potencial. Si el primer número es un 1, no importa mucho cuál sea el segundo número, ya que la puntuación se multiplica sólo por 1: con el reemplazo, la puntuación estará entre 1 y 10, en lugar de entre 2 y 10 sin. Pero si el primer número es un 10, hay un mayor impacto debido al hecho de que se multiplica por 10, dándonos una posible puntuación entre 10 y 100 con sustitución, en lugar de entre 10 y 90 sin ella. Si adoptamos la estrategia "con reemplazo", la "ganancia" de obtener doble 10 es mayor que la "pérdida" que obtenemos de escoger doble 1. Se puede extender esto simétricamente para ver que la ganancia por el doble 9 es mayor que la pérdida por el doble 2, y así sucesivamente. Siempre ganamos más en el extremo superior con la estrategia "con reemplazo" que lo que perdemos en el extremo inferior, por lo que la estrategia "con reemplazo" es preferible en general.

Answer 4

Si se te da mejor la programación que las matemáticas, creo que también hay una forma razonablemente sencilla de conseguirlo por fuerza bruta.

Proporciona una intuición ligeramente diferente: $E[XY]$ es más alto sin reemplazo cuando $X < \text{mean}(X)$ porque la eliminación de un valor bajo de $X$ aumenta $E[Y]$ es menor, y en mayor medida, cuando $X > \text{mean}(X)$ . Un poco de reflexión muestra que esta asimetría se produce porque estamos viendo el producto, por ejemplo, no ocurriría para $E[X + Y]$ .

library(tidyverse)
vals = 1:10

# Calculate E[XY|x] conditional on each possible value of X
no_replace = map_dbl(vals, function(x) mean(x * vals[vals != x])) 
with_replace = map_dbl(vals, function(x) mean(x * vals))

# Take averages over X values to get E[XY]
mean(no_replace) # 29.33333
mean(with_replace) # 30.25

# Plot
df = data.frame(x = vals, 
                `Replacement`=with_replace, 
                `Without replacement`=no_replace)
df %>% pivot_longer(-x) %>% 
  ggplot(aes(x, value, color = name)) + 
  geom_point() +
  geom_path() +
  geom_vline(linetype = 'dashed', xintercept = mean(vals)) +
  scale_x_continuous(breaks = vals) +
  labs(x = 'X', y = 'E[XY]', color = 'Method')

Answer 5

Hay tres hechos que me han llevado a la conclusión de que la sustitución da un valor esperado más alto:

1. Los productos dan lugar a distribuciones sesgadas hacia la derecha. Cuando se multiplican números juntos, se tiende a obtener resultados agrupados en su mayoría en números pequeños, con unos pocos resultados grandes.
2. En una distribución sesgada a la derecha, el aumento de la varianza tiende a aumentar la media. Dado que los extremos por encima de la mediana son más extremos que los extremos por debajo de ella, ser más extremo aumenta el resultado de la media. Por ejemplo, en la pregunta que presenta, podemos estimar rápidamente que la mediana está en torno a $5\times6$ (el producto de los dos números centrales). El mínimo es $1\times1$ y el máximo es $10\times10$ . Así que conseguir un número extremadamente bajo nos cuesta como máximo $30$ mientras que un número extremadamente alto puede darnos hasta $70$ sobre la mediana.
3. Permitir la sustitución aumenta la varianza. Con el reemplazo, se puede obtener algo que consiste enteramente en los números más extremos. Sin reemplazo, sólo puedes obtener una instancia del máximo y la otra puede ser como mucho la segunda más alta, y de forma similar para el mínimo.

No se trata de una prueba rigurosa, pero entender cómo interactúan la asimetría, la varianza y el reemplazo es importante para trabajar con la estadística.

Como nota al margen, no creo que sea realmente teoría de juegos. Si el simple hecho de formularlo como una elección entre opciones lo convirtiera en teoría de los juegos, entonces todos los problemas de optimización serían teoría de los juegos (y prácticamente todo puede formularse como un problema de optimización).