Cotas de caso promedio

El Teorema de Shannon establece que, si los elementos de $U = \{ u_1, \ldots, u_n \}$ se presentan con probabilidad $p_i$ para $u_i$ (con $\sum p_i = 1$), entonces ningún compresor puede, en promedio, utilizar menos de

$H ~=~ \sum_i p_i \log_2 \frac{1}{p_i}$

bits para codificar un elemento de $U$. Este valor se llama la entropía del conjunto de probabilidades. La entropía nos da una herramienta para establecer cotas inferiores en el caso promedio, lo que no se da con la estrategia del adversario.

Note que, si todas las $p_i = \frac{1}{|U|}$, entonces la entropía resulta ser $H = \log_2 |U|$, llegando a su valor máximo. Como esto coincide con el valor del peor caso, resulta que la cota inferior de peor caso de un algoritmo (demostrada con esta técnica) también es la cota inferior de caso promedio si los inputs se presentan todos con la misma probabilidad. En particular, de los ejemplos anteriores, tenemos que la cota de $\log_2 n$ comparaciones para buscar en un arreglo ordenado o de $n\log_2 n - O(n)$ para ordenar también se aplican al caso promedio del mejor algoritmo posible, si suponemos que los elementos de $A$ se buscan con la misma probabilidad o que todos los reordenamientos de entrada de $A$ son igualmente probables, respectivamente.

Por otro lado, si resulta que tenemos que buscar en un arreglo y ciertos elementos se buscan con mayor probabilidad que otros, entonces podemos romper la cota de $\log_2 n$ comparaciones en promedio, y llegar a la entropía $H$. Pero, ¿cómo hacerlo?