1.3 Measuring a probabilistic bit

If you toss a fair coin and immediately cover it, you have no idea on which side it landed. In this situation your knowledge about the state of the coin is described by the uniform distribution

$$\vbox{\hbox{\includegraphics[width=30.0pt]{figs/01.png}}}=\begin{pmatrix}1/2\\ 1/2\end{pmatrix}=\frac{1}{2}\,[0]+\frac{1}{2}\,[1].$$ (1.29)

However, if you uncover the coin and see “heads”, your knowledge is updated to

$$\vbox{\hbox{\includegraphics[width=30.0pt]{figs/0.png}}}=[0]$$ (1.30)

because now you know with certainty that heads is up. We will refer to the process of uncovering a probabilistic coin to determine which side is up as measurement.³³ 3 We have borrowed this term from quantum computing where we will see that a similar procedure exists.

Notice from Eqs. 1.29 and 1.30 that the state of the coin before and after the measurement is different. Indeed, after the measurement you are no longer ignorant about which side is up. Now, imagine you cover the coin again after you have just measured it. What is its state now? Well, it clearly is still

$$\vbox{\hbox{\includegraphics[width=30.0pt]{figs/0.png}}}=[0]$$ (1.31)

because you already know that “heads” is up. In fact, even if you measure (look at) the coin again, you will still see “heads”. Similarly, if you got “tails” the first time you measured a random coin, you will keep getting “tails” no matter how many times you measure it again.

More generally, if you have a probabilistic bit described by the distribution $\bigl{(}\begin{smallmatrix}p_{0}\\ p_{1}\end{smallmatrix}\bigr{)}$, measuring it yields the outcome $0$ (or “heads”) with probability $p_{0}$ and $1$ (or “tails”) with probability $p_{1}$:

The state of the probabilistic bit after the measurement is no longer $\bigl{(}\begin{smallmatrix}p_{0}\\ p_{1}\end{smallmatrix}\bigr{)}$ but one of the basis states $[0]=\bigl{(}\begin{smallmatrix}1\\ 0\end{smallmatrix}\bigr{)}$ or $[1]=\bigl{(}\begin{smallmatrix}0\\ 1\end{smallmatrix}\bigr{)}$, depending on the measurement outcome. For example, if you got outcome $1$ (or “tails”), the new state is $[1]$. In general a measurement changes the state!

An important point about measurements is that they do not let you extract the actual probabilities $p_{0}$ and $p_{1}$ – all you get as a measurement outcome is a single bit $0$ or $1$. Also, your original probabilistic bit $\bigl{(}\begin{smallmatrix}p_{0}\\ p_{1}\end{smallmatrix}\bigr{)}$ is gone after the measurement, so you cannot measure it again. This is in fact quite intuitive. If we toss a coin exactly once then we get a single random outcome – but from this single outcome alone we cannot learn whether the coin was fair or biased!

However, suppose we toss the same coin a large number of times. In this case we would expect that the fraction of times that we obtain outcome $1$ is roughly $p_{1}$. In other words,

where $N$ is the total number of measurements and $N_{1}$ the number of times that we obtained outcome $1$. The more outcomes we have gathered, the better the approximation should get.⁴⁴ 4 How good is this estimate? One can show that, on average, the error is of the order of $1/\sqrt{N}$, so quickly goes to zero if we repeat the experiment many times.

This provides us with a procedure for estimating $p_{1}$. Of course, since $p_{0}+p_{1}=1$, this also gives us an estimate of $p_{0}$. For example, Alice could use this procedure to estimate the probability that her biased coin in 1.3 lands on and . You can now try this out for yourself.