Linealidad de la expectativa

Prerrequisito: Variable aleatoria
Esta publicación trata sobre conceptos matemáticos como expectativa , linealidad de expectativa . Cubre uno de los temas necesarios para comprender los algoritmos aleatorios .

Consideremos el siguiente problema simple.

Problema: dado un dado justo con 6 caras, el dado se lanza n veces, encuentre el valor esperado de la suma de todos los resultados.
Por ejemplo, si n = 2, hay un total de 36 resultados posibles.

(1, 1), (1, 2), .... (1, 6)
(2, 1), (2, 2), .... (2, 6)
................
................
(6, 1), (6, 2), ..... (6, 6)

El valor esperado de una variable aleatoria discreta es R definido de la siguiente manera. Supongamos que R puede tomar el valor r ₁ con probabilidad p ₁ , el valor r ₂ con probabilidad p ₂ , y así sucesivamente, hasta el valor r _k con probabilidad p _k . Entonces la expectativa de esta variable aleatoria R se define como:

E[R] = r1*p1 + r2*p2 + ... rk*pk

Calculemos el valor esperado para el ejemplo anterior.

Expected Value of sum = 2*1/36 + 3*1/36 + .... + 7*1/36 + 
of two dice throws      3*1/36 + 4*1/36 + .... + 8*1/36 + 
                        ........................
                        .........................
                        7*1/36 + 8*1/36 + .... + 12*1/36     
                  
                      = 7

La forma anterior de resolver el problema se vuelve difícil cuando hay más lanzamientos de dados.
Si sabemos acerca de la linealidad de la expectativa , podemos resolver rápidamente el problema anterior para cualquier cantidad de lanzamientos.

Linealidad de la expectativa: Sean R ₁ y R ₂ dos variables aleatorias discretas en algún espacio de probabilidad, entonces

     E[R1 + R2] = E[R1] + E[R2] 

Usando la fórmula anterior, podemos resolver rápidamente el problema de los dados.

Expected Value of sum of 2 dice throws = 2*(Expected value of one dice throw)
                                       = 2*(1/6 + 2/6 + .... 6/6)
                                       = 2*7/2
                                       = 7 

Expected value of sum for n dice throws is = n * 7/2 = 3.5 * n 

Algunos datos interesantes sobre Linearly of Expectation:

1. La linealidad de la expectativa es válida tanto para eventos dependientes como independientes. Por otro lado, la regla E[R ₁ R ₂ ] = E[R ₁ ]*E[R ₂ ] es verdadera solo para eventos independientes.
2. La linealidad de la expectativa es válida para cualquier número de variables aleatorias en algún espacio de probabilidad. Sean R ₁ , R ₂ , R ₃ , … R _k k variables aleatorias, entonces
   E[R ₁ + R ₂ + R ₃ + … + R _k ] = E[R ₁ ] + E[R ₂ ] + E[ R ₃ ] + … + E[R _k ]

Otro ejemplo que se puede resolver fácilmente con la linealidad de la expectativa:
Problema de verificación de sombreros: Sea un grupo de n hombres donde cada hombre tiene un sombrero. Los sombreros se redistribuyen y cada hombre recibe un sombrero al azar. ¿Cuál es el número esperado de hombres que recuperan su sombrero original?

Solución: Sea R _i una variable aleatoria, el valor de la variable aleatoria es 1 si el i-ésimo hombre recupera el mismo sombrero, de lo contrario 0.

So the expected number of men to get the right hat back is
  = E[R1] + E[R2]  +  .. + E[Rn] 
  = P(R1 = 1) + P(R2 = 1) + .... + P(Rn = 1) 
  [Here P(Ri = 1)  indicates probability that Ri is 1]
  = 1/n + 1/n + ... + 1/n 
  = 1

Entonces, en promedio, 1 persona recupera el sombrero correcto.

Ejercicio:

1. Dada una moneda justa, ¿cuál es el número esperado de caras cuando la moneda se lanza n veces?
2. Pelotas y recipientes: Supongamos que tenemos m pelotas, rotuladas i = 1, … , m y n recipientes, rotulados j = 1, .. ,n. Cada bola se lanza a uno de los contenedores de forma independiente y uniforme al azar.
        a) ¿Cuál es el número esperado de pelotas en cada contenedor
        ? b) ¿Cuál es el número esperado de contenedores vacíos?
3. Recolector de cupones: suponga que hay n tipos de cupones en una lotería y cada lote contiene un cupón (con probabilidad 1 = n cada uno). Cuántos lotes hay que comprar (en expectativa) hasta que tengamos al menos un cupón de cada tipo.

Vea a continuación la solución de Coupon Collector.
Número esperado de ensayos hasta el éxito

La linealidad de la expectativa es útil en los algoritmos. Por ejemplo, la complejidad temporal esperada de los algoritmos aleatorios como la ordenación rápida aleatoria se evalúa utilizando la linealidad de la expectativa (consulte esto como referencia).

Referencias:
http://www.cse.iitd.ac.in/~mohanty/col106/Resources/linearity_expectation.pdf

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/video-lectures/lecture-22-expectation-i/

Este artículo es una contribución de Shubham Gupta . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.