What is mutual information?

Mutual information is a measure of the dependence between different variables. Specifically, the mutual information between X and Y corresponds to the amount that your uncertainty about Y is reduced by knowledge of X, and vice versa. In other words, how much do you learn about Y from observing X?

For example, there is high mutual information between knowing how many people are going to the beach and knowing how warm it is outside, since if you know that a lot of people went to the beach, it is more likely that the temperature is higher (and vice versa — knowing the temperature is higher makes it more likely that a lot of people have gone to the beach). But there is no mutual information between two flips of a fair coin, since knowing the result of one does not change your prediction about the result of the other.