6

What Do You Mean “Probably”?

Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin.

John von Neumann
223

Here’s the key to what we cover in this chapter: in any given situation, the sum of the probabilities of all the possible things that could happen always adds up to 1.

In this short chapter, I cover the basics of practical probability theory to get us started on quantum computing and its applications.

Topics covered in this chapter

1. 6.1. Being discrete
2. 6.2. More formally
3. 6.3. Wrong again?
4. 6.4. Probability and error detection
5. 6.5. Randomness
6. 6.6. Expectation
7. 6.7. Hellinger distance
8. 6.8. Markov and Chebyshev go to the casino
9. 6.9. Summary

6.1 Being discrete

Sometimes, it seems like probability is the study of flipping coins or rolling dice, given the number of books that explain it in those ways. It’s tough to break away from these convenient examples. An advantage shared by both is that they make it easy to explain discrete events and independence. A set of events is discrete if there are only a finite number of them or if we can put them in one-to-one correspondence with Z. sample space$discrete

For the sake of mixing it up, suppose we have a cookie machine. It’s a big box with a button on top. Every time you press the button, a cookie pops out of a slot on the bottom. There are four kinds of cookies: chocolate, sugar, oatmeal, and coconut.

Assume, for the moment, there is no limit to the number of cookies our machine can distribute. You get a million cookies if you hit the button a million times. Also, assume you get a random cookie each time. What does this mean, “random...

6.2 More formally

In the last section, there were initially four different possible outcomes: the four kinds of cookies that could pop out of our machine. In this situation, our sample space is the collection sample space

We also say that these four are the values of a random variable. Random variables usually have names such as X and Y. probability$random variable

A probability distribution assigns a probability to each possible outcome, which are the values of the random variable. The probability distribution for the balanced case is probability$distribution

When the probabilities are all equal, as in this case, we have a uniform distribution. probability$uniform distribution

If our sample space is finite or, at most, countably infinite, we say it is discrete. A set is countably infinite if it can be put in one-to-one correspondence with Z. sample space$discrete

The sample space is continuous if it can be put in correspondence...

6.3 Wrong again?

Suppose you have a faulty calculator that does not always compute the correct result.

If the probability of getting the wrong answer is p, the probability of getting the correct answer is 1 – p. We call this the complementary probability. We assume 0 < p < 1. Assuming there is no connection between the attempts, the probability of getting the wrong answer two times in a row is p², and the probability of getting the correct answer two times in a row is (1 – p)². probability$complementary

Exercise 6.3

Compute p² and (1 – p)² for p = 0, p = 0.5, and p = 1.0.

To make this analysis useful, we want the probability of failure p to be nonzero.

For n independent attempts, the probability of getting the wrong answer is pⁿ. Let’s suppose p = 0.6. We get the wrong answer 60% of the time in many attempts. We get the correct answer 40% of the time.

After 10 attempts, the...

6.4 Probability and error detection

Let’s return to our repetition code for error detection from section 2.1. The specific example we look at is sending information represented in bits via a binary symmetric channel. The probability that I will get an error by flipping a 0 to a 1 or a 1 to a 0 is p. The probability that no error occurs is 1 – p, as above. error detection error correction error correction$repetition code

For a binary symmetric channel, we have two representations for information, the bits 0 and 1, and hence “binary.” The probability of something wrong happening to a 0 or 1 is the same, and that’s the symmetry. error correction$binary symmetric channel

The process for sending the information to someone whom I will call Alicia is:

1. Create a message to be sent.
2. Transform that message by encoding it to contain extra information, allowing Alicia the possibility to repair the message if it...

6.5 Randomness

Many programming languages have functions that return pseudo-random numbers. The prefix “pseudo” is there because they are not genuinely random numbers but, nevertheless, they do well on statistical measurements of how well-distributed the results are. number$random

Given four possible events, E₀, E₁, E₂, and E₃, with associated probabilities p₀, p₁, p₂, and p₃, how might we use random numbers to simulate these events happening with

The probabilities add up to 1.0, as expected. random programming language$Python

In Python, the random() function returns a random real number r such that 0.0 ≤ r < 1.0. We determine that one of the E₀, E₁, E₂, and E₃, events occurred based on the value of r computed. random()`function-name random`module-name

If you are not using Python, use whatever similar function is available in your programming language and environment.

The general scheme is to run the following...

6.6 Expectation

Let’s look at the numeric finite discrete distribution of the random variable X with the probabilities given in this table: expected value expectation

If the process producing these values continues over time, what value would we “expect” to see?

If they all have the same probability of occurring, the expected value or expectation, E(X) is their average:

Note that the answer does not need to be, and often isn’t, one of the values in the distribution.

Since each value of X has a given probability, the expected value is instead the weighted average

If someone simply gives you a list of values for a random variable, you can assume a uniform distribution, and the expected value is the usual average or mean. We sometimes use the notation μ(X) instead of E(X). μ is the lowercase Greek letter “mu.” μ`italic

If X is a random...

6.7 Hellinger distance

This section examines how we can measure the similarity between two comparable collections using the concept of Hellinger distance. The idea is that if the two collections are “close to each other distance-wise,” they are similar. similarity$Hellinger distance

Consider the game of pool, played with a cue and solid and striped balls on a table. Suppose I have a large box and place one hundred yellow pool balls, one hundred red pool balls, one hundred blue pool balls, and one hundred purple pool balls in the box. I mix the balls thoroughly, so if I reach in and take out a ball, I have the same probability of getting one color as any other. That is, I have a uniform distribution of the balls.

I reach into the box and remove one hundred balls. I record the colors and the count of each:

I put the balls back in the box, stir them up well, and then you remove one hundred balls. Oddly, you pull out balls with the same...

6.8 Markov and Chebyshev go to the casino

In this section, we work through the probability math of estimating π as we previously explored in section 1.5. We dropped coins into a square and looked at how many of them had their centers on or inside a circle. Chebyshev’s Inequality Markov, Andrey Chebyshev, Pafnuty

There are two important inequalities involving expected values, variances, and error terms. Let X be a finite random variable with a known distribution so that

and each x_k ≥ 0.

Markov’s Inequality

For a real number a > 0, Markov’s Inequality

In Markov’s Inequality, the expression P(X > a) means “look at all the x_k in X, and for all those where x_k > a, add up the p_k to get P(X > a).”

Exercise 6.8

Show that Markov’s Inequality holds for the distribution at the beginning of section 6.6 for...

6.9 Summary

In this chapter, we covered the elements of probability necessary for our treatment of quantum computing and its applications. When we work with qubits and circuits in the following chapters, we will use discrete sample spaces, although they can get quite large. In these cases, the sizes of the sample spaces will be powers of 2.

Our goal in a quantum algorithm is to adjust the probability distribution so that the element in the sample space with the highest probability is the best solution to some problem. Indeed, the manipulation of probability amplitudes leads us to find what we hope is the best answer. My treatment of algorithms in Chapter 9, “Wiring Up the Circuits,” and Chapter 10, “From Circuits to Algorithms,” does not go deeply into probability calculations, but it does so sufficiently to give you an idea of how probability interacts with interference, complexity, and the number of times we must run a calculation to be confident...