I am trying to learn the information bottleneck method. On slide 15, they give this equation. I think I understand that X is a random variable (but do not understand the meaning of the exponent, n). I understand that this equation is somehow representing the random variable X^n encoded and then decoded. But what is the meaning of E and little d in this equation. How do they contribute to big D?
$E$ stands for expected value and $d(\cdot, \cdot)$ means distortion, however you define distortion. $X^n$ is a vector or $n$-tuple of random variables $X$. You could write this as $(X_1, X_2, \ldots, X_n)$ where the $X_i$ are random variables with a common distribution (but need not be independent). $f_n(X^n)$ is the result of compressing or encoding $X^n$: the result is typically a vector of shorter length. $g_n$ is the function that de-compresses or decodes its argument. Thus, $g_n$ applied to the compressed vector $f_n(X^n)$ produces a vector $Y^n = g_n(f_n(X^n))$. It is the machine learner's fondest hope that the reconstructed $Y^n$ resembles $X^n$ as much as possible. In the best of all possible worlds, the reconstructed $Y^n$ is identical to the $X^n$ that underwent compression and then decompression. In practice, $Y^n$ is not the same as $X^n$, and the distortion $d$ can be defined in various ways depending on what one is trying to achieve. We might want for example to have $$d(X^n, Y^n) = \sum_{i=1}^n |X_i-Y_i| \quad \text{or}\quad d(X^n, Y^n) = \sum_{i=1}^n (X_i-Y_i)^2 \quad \text{or}\quad d(X^n, Y^n) = \max_{i} |X_i-Y_i|.$$
FInally, putting it all together, the expectation operator is computing $D$, the average distortion over all values of $X^n$