La intuición detrás del concepto de indicador de variables aleatorias.

Question

Estoy estudiando Algoritmos Aleatorizados capítulo en el libro "Introducción a los Algoritmos" por Cormen et al.

En este capítulo, el libro introduce el concepto de un indicador de la variable aleatoria y el estado que el valor esperado de un indicador de la variable aleatoria como :

Estoy teniendo dificultades para entender por qué esto se llama un indicador de variable aleatoria, específicamente por qué indicador y azar y de cómo este concepto es útil en el análisis de algoritmo de los tiempos . Ha pasado algún tiempo desde que estudié la probabilidad en la escuela . Sin embargo , soy consciente de que el concepto detrás de la probabilidad. Así que usted puede basar su respuesta en esta premisa.

Como se puede ver en el diagrama de todo lo que está diciendo es que el valor esperado de un indicador de la variable aleatoria de un evento es igual a la probabilidad de ese evento . Ya tenemos el concepto de probabilidad , ¿por qué debemos saber acerca de este nuevo concepto, que pasa a ser el mismo valor que la probabilidad ?

Answer 1

Como el nombre implica, un indicador de la variable aleatoria que indica algo: el valor de $I_A$ $1$ precisamente cuando el evento $A$ se produce, y es $0$ al $A$ no se produce (es decir, $A^c$ se produce). Creo que de $I_A$ como una variable Booleana que indica la ocurrencia del evento $A$. Esta variable Booleana tiene valor $1$ con una probabilidad de $P(A)$, por lo que su valor promedio es $P(A)$. En términos de largo plazo de frecuencias, $I_A$ tendrá valor $1$, aproximadamente, $N\cdot P(A)$ $N$ ensayos del experimento, y el promedio a largo plazo valor de $I_A$ en estos $N$ ensayos será de aproximadamente $P(A)$.

Answer 2

Un indicador de la función es una función que devuelve el valor de 1 cuando algo es cierto: $$\mathbf{1}[A] = \left\{\begin{array}{cc} 1, & A\ \mathrm{ is\ true,} \\ 0, & A\ \mathrm{ is\ false.} \end{array}\right.$$

Por lo tanto, la expectativa es esencialmente lo mismo como calcular el valor esperado de una variable aleatoria de Bernoulli: el valor 1 veces la probabilidad de que $A$ es cierto, más el valor 0 veces la probabilidad de que no lo es.