How much information is gained when sampling from a random distribution?

Question

This is a problem I have encountered while considering ELO ratings for a game like Go.

Suppose we have two players, one has a known rating, the other's is unknown but assumed to be close to the first. We match the players to gain a more accurate estimate for the latter's rating.

The player has about a 50% chance to win, so I want to be able to say that we gain 1 bit of information from the result of the game (and I intend to follow with discussing ways to obtain more than 1 bit from a game, e.g. by considering the score difference rather than just a boolean win/lose).

But if taken literally, it gives nonsensical results - for example, it would mean that after 64 games, we can tell the player's rating to a precision of 64 bits.

Generally speaking, the sd of the posterior distribution for the rating goes down by the square root of the number of games played, not exponentially as can be implied by the "1 bit per game" statement.

So I thought maybe I should consider this more carefully and look at the entropy of the rating's prior distribution, and see how it differs from the posterior's. I thought that maybe the extra bit of information will manifest as a difference of 1 bit in the entropy of the distributions.

But it's not even close. For a simpler example I looked at the well-studied problem of a coin with unknown bias. If our prior distribution for the probability of Heads is Beta (100, 100), this has an entropy of -2.77846 bits (unless I made a mistake). After one toss, the posterior will be either Beta (101, 100) or Beta (100, 101), each of which has an entropy of -2.78206 bits. So we've gained only about 0.0036 bits, and not 1 as hoped.

So my question is threefold -

1. If "1 bit" is the correct amount of information gained from the sample, what metric can be used to encode how much information we have accumulated?

2. If 0.0036 bits is the correct amount of information gained in the coin toss example above, what is a simple way to determine this gain, despite the intuitive argument for a gain of 1 bit?

3. What else am I missing here?

Edit: To clarify what it is I'm trying to do, let's say there is an unknown quantity $X$ that I want to determine. I have a prior distribution $P(X)$. I draw a sample $Y$ from a known family of distributions parameterized by $X$, $Y \sim P_X(Y)$. However, $Y$ itself is unknown to me - I only know $Z=f(Y)$ for some known function $f$ (of course, it is possible that we have the special case $Z=Y$).

I want to use my knowledge of $Z$ to refine my estimation for $X$. I want to quantify how much observing $Z$ has helped me.

My original approach was to look at the entropy of the distribution $P(Z)$. This depends on the function $f$ - if it is injective, by knowing $Z$ we actually know $Y$, so we gain the maximum information. Accordingly, $P(Z)$ is supported on many different values and has high entropy.

On the other extreme, if $f$ maps all values of $Y$ to a single value, $P(Z)$ is supported on a singleton and has 0 entropy, and we have gained no information.

In between, the more often $f$ maps different values of $Y$ to the same value of $Z$, the lower is the entropy of $P(Z)$, and the less I can deduce about $X$.

So I'm trying to figure out what measure of the uncertainty on $X$ will decrease in accordance to the entropy of $P(Z)$. Or, if not specifically to the entropy, to some other attribute of the distribution of $P(Z)$. This way, I can compare different functions $f$ and $g$ and say that one is better than the other, because one of them gives $a$ units of information per sample, and the other $b$ units.

In the Go game example, $f$ could give a boolean result of who won, and $g$ could give the actual score. In this case, $g$ would be more informative.

Edit 2: I think it's worth emphasizing that this is a rather open and broad question. The exact approach I originally tried obviously doesn't work (and Bridgeburners has shed some light on the underlying reasons); and it's probably impossible to construct something that matches my expectations fully (e.g., there are examples where we can have $Z$ grow arbitrarily in entropy, with a finite bound on the knowledge gained on the distribution of $X$.

I'm basically fishing for what it is that can be said along the goal I outlined. It will probably take the form of a one-sided bound. That is, given the entropy of $P(Z)$, there is likely no lower bound on the knowledge gained on $X$ ($Z$ could be completely random and irrelevant), but there should be an upper bound - if the entropy of $P(Z)$ is $a$, then it can't possibly improve our knowledge on $X$ by more than this-and-that. But I don't know what measure on the uncertainty on $X$ lends itself to such a bound (the only measures I can think of are the sd of the distribution of $X$ and its differential entropy), or what the bound could be.

It's possible that "1 divided by the variance of the distribution of $X$" is what I'm looking for, as it increases linearly with the number of samples, and conceivably, an experiment with 2 bits of entropy for the result should increase it by twice as much as an experiment with 1 bit. But I'm not sure how to quantify the relation between the two.

Answer 1

I see two conceptual mistakes here.

First of all, "entropy" is defined as the expected amount of information you gain when drawing a sample from a distribution. After some number of coin flips, the probability distribution of the $p$ parameter is best characterized by the Beta distribution, as you say. But it is not the Beta distribution you are drawing from when flipping a coin. (Maybe that's what you're drawing from when manufacturing a coin, or taking a guess as to the value of $p$.) When flipping a coin, you are drawing from the Bernoulli distribution. If you do the entropy calculation of one draw from a Bernoulli distribution with parameter $p=1/2$ you will get exactly what you expect, namely one bit of information gained from one sample.

Secondly, you might be mixing up entropy with differential entropy. They are not like probability vs probability density, in that they don't hold an analogous connection with each other.

The definition of entropy (in nats, rather than bits) is $$-\sum_i p_i \log p_i.$$ The definition of differential entropy is $$-\int p(x) \log p(x) dx.$$ In the same sense that $p(x)$ is not actually a probability, $-\log p(x)$ is not a quantity of information. However, unlike with probability, integrating $-\log p(x)$ over a region does not give you a measure of information as we would consider when looking at normal entropy.

To see why this is, suppose we have a probability distribution $p(x)$ whose domain is $\mathcal{X}.$ However, for a subset of that region $\mathcal{Y} \subset \mathcal{X},$ $p(x)$ is uniform. That is, $p(x) = c$ for $c \in \mathcal{Y}$ where $c$ is some constant. Let $V$ be the volume of region $\mathcal{Y}.$ Then the contribution to the absolute entropy gained for observing a variable in $\mathcal{Y},$ in nats, is $- (c V) \log (c V).$ However, the contribution of differential entropy gained for observing a variable in $\mathcal{Y}$ is, $$ - \int c \log c dX = -(c V) \log c \ne -(c V) \log (c V). $$ Looking at the definition of absolute entropy, if each of these discrete events implicitly represents an integral over a continuum, then the volume of those regions are taken inside the $\log$ function, whereas that's not the case when taking the expectation of differential entropy, which is what happens when looking at the entropy of the Beta distribution. So entropy and differential entropy are fundamentally different things, and one is not inferred by taking the integral of another (which makes it not analogous to probability vs probability density).