Paso en la prueba de la desigualdad de Markov.

Question

Estoy haciendo una revisión de Algoritmos Aleatorios de Motwani y Raghavan. En la página 46 presentan la siguiente prueba para la desigualdad de Markov.

Teorema 3.2 (Desigualdad de Markov): Sea $Y$ sea una variable aleatoria que suponga sólo valores no negativos. Entonces para todo $t \in R^+$ $$\mathbf{Pr}[Y \geq t] \leq \frac{E[Y]}{t}$$ Equivalentemente $$\mathbf{Pr}[Y \geq kE[Y]] \leq \frac{1}{k}$$ PROOF : Definir una función $f(y)$ por $f(y) = 1$ si $y \geq t$ y 0 en caso contrario. Entonces $$\mathbf{Pr}[Y \geq t] = E[f(Y)]$$ Desde $f(y) \leq y/t$ para todo y, $$E[f(Y)] =\mathbf{Pr}[Y \geq t] \leq E[Y/t] = \frac{E[Y]}{t}$$ y el teorema sigue.

¿Podría alguien ayudarme con los pasos que dan en la sección de pruebas? Gracias

Answer 1

No has dicho con qué paso estabas teniendo problemas. Tal vez esto pueda ayudar

• $E[f(Y)] = \Pr(f(Y)=0) \times 0 +\Pr(f(Y)=1) \times 1 = \Pr(f(Y)=1) = \Pr(Y \ge t)$
• Si $0 \le y \lt t$ entonces $f(y)=0 = \frac0t \le \frac y t$ , mientras que si $y \ge t$ entonces $f(y) = 1 = \frac t t \le \frac y t$
• $f(y) \le \frac y t \,\forall y \ge 0 \implies E[f(Y)] \le E\left[\frac Y t\right]$ y como $t$ es una constante $E\left[\frac Y t\right] = \frac{E[Y]}{t}$