From classical deduction to Bayesian probability

Terence Tao on classical deduction and Bayesian probability:

In classical logic, one can represent one’s information about a system as a set of possible states that the system could be in, based on the information at hand. With each new measurement of the system, some possibilities could be eliminated, leading to an updated posterior set of information that is an improvement over the prior set of information. A good example of this type of updating occurs when solving a Sudoku puzzle; each new cell value that one learns about constrains the possible values of the remaining cells. Other examples can be found in the classic detective stories of Arthur Conan Doyle featuring Sherlock Holmes. Proof by contradiction can also be viewed as an instance of this type of deduction.

A modern refinement of classical deduction is that of Bayesian probability. Here, one’s information about a system is not merely represented as a set of possible states, but by a probability distribution on the space of all states, indicating one’s current beliefs on the likelihood of each particular state actually being the true state. Each new measurement of the system then updates a prior probability distribution to a posterior probability distribution, using Bayes’ formula

.

Bayesian probability is widely used in statistics, in machine learning, and in the sciences.

To relate Bayesian probability to classical deduction, recall that every probability distribution has a support, which (in the case when the space of states is discrete) is the set of all states that occur with non-zero probability. When performing a Bayesian update on a discrete space, any state which is inconsistent with the new piece of information will have its posterior probability set to zero, and thus be removed from the support. Thus we see that whilst the probability distribution evolves by Bayesian updating, the support evolves by classical deductive logic. Thus one can view classical logic as the qualitative projection of Bayesian probability, or equivalently, one can view Bayesian probability as a quantitative refinement of classical logic.

Alternatively, one can view Bayesian probability as a special case of classical logic by taking a frequentist interpretation. In this interpretation, one views the actual universe (or at least the actual system) as just one of a large number of possible universes (or systems). In each of these universes, the system is in one of the possible states; the probability assigned to each state is then the proportion of the possible universes in which that state is attained. Each new measurement eliminates some fraction of the universes in a given state, depending on how likely or unlikely that state was to actually produce that measurement; the surviving universes then have a new posterior probability distribution, which is related to the prior distribution by Bayes’ formula.

It is instructive to interpret Sherlock Holmes‘ famous quote, “When you have eliminated all which is impossible, then whatever remains, however improbable, must be the truth,” from a Bayesian viewpoint. The statement is technically correct; however, when performing this type of elimination to an (a priori) improbable conclusion, the denominator in Bayes’ formula is extremely small, and so the deduction is unstable if it later turns out that some of the possibilities thought to have been completely eliminated, were in fact only incompletely eliminated. (See also the mantra “extraordinary claims require extraordinary evidence”, which can be viewed as the Bayesian counterpoint to Holmes’ classical remark.)

Another interesting place where one can contrast classical deduction with Bayesian deduction is with regard to taking converses. In classical logic, if one knows that implies , one cannot then deduce that  implies . However, in Bayesian probability, if one knows that the presence of elevates the likelihood that is true, then an observation of will conversely elevate the prior probability that is true, thanks to Bayes’ formula: if , then . This may help explain why taking converses is an intuitive operation to those who have not yet been thoroughly exposed to classical logic. (It is also instructive to understand why this disparity between the two types of deduction is not in conflict with the previously mentioned links between the two. This disparity is roughly analogous to the disparity between worst-case analysis and average-case analysis.)

Bayesian probability can be generalised further; for instance, quantum mechanics (with the Copenhagen interpretation) can be viewed as a noncommutative generalisation of Bayesian probability, though the connection to classical logic is then lost when one is dealing with observables that do not commute. But this is another story…

__________

Please do note that Terence Tao’s original post contains neither links nor boldface highlighting. I took the liberty of adding those for convenience and emphasis. To improve legibility I also wrote the mathematical expressions in .

__________

Source:

Terence Tao, “A modern refinement of classical deduction is that of Bayesian probability”, Google Buzz, April 4, 2010.

Rainy days

A couple of weeks ago, Presh Talwalkar posted this puzzle:

In Mathland, the weather is described either as sunny or rainy. On a sunny day, there is an equal chance it will rain on the following day or be sunny. On a rainy day, however, there is a 70% chance it will rain on the following day versus a 30% chance it will be sunny. How many days is it expected to rain in a 365-day year? Assume the first day is sunny.

__________

My solution:

We will consider a period of days. Since in our oversimplified world each day is either sunny or rainy, we introduce random variables taking values in , where means that the -th day is rainy. We assume that the first day is sunny, i.e., . Hence, and .

Let us now introduce random variables taking values in , where each is defined as follows

Note that the expected value of is . We introduce a new random variable , defined by

where is the number of rainy days in a period of days. We want to find the expected number of rainy days, which is

.

Hence, to compute the desired expected value, , we must first compute the probabilities for .

Let the probability mass function (p.m.f.) on the -th day be

We know that the p.m.f. on the first day is , as we assume the first day is sunny. Propagating the p.m.f. forwards in time, we obtain , where

is the transition matrix. Hence, we have and, thus,

Matrix has the eigendecomposition and, hence, . We can finally compute by matrix-vector multiplication, a task so excruciatingly dull that I am most happy to delegate it to my Pythonic minion:

from sympy import *

# create symbolic variable
k = Symbol('k')

# define transition matrix
P = Matrix([[0.5, 0.5], [0.3, 0.7]])

# eigendecomposition of the transition matrix
Q = Matrix([[1/sqrt(2), 5/sqrt(34)], [1/sqrt(2), -3/sqrt(34)]])
D = Matrix([[1, 0], [0, 0.2]])

# check if eigendecomposition is correct
print Q * D * Q.inv() - P

# create vectors
e1 = Matrix(2, 1, [1, 0])
e2 = Matrix(2, 1, [0, 1])

# compute and print probability that the k-th day is rainy
print e1.T * Q * Matrix([[1, 0], [0, 0.2**(k-1)]]) * Q.inv() * e2

This Python / SymPy script gives us

and, finally, we obtain the desired expected value

which is equal to

.

For , we get rainy days per year. Mathland is certainly not in Southern California ;-)

Dealing cards

Imagine that you have a deck of three cards: , , and . You shuffle the deck and deal out the three cards. What is the probability that:

• the second card is even given that the first card is even?

• the first two cards are even given that the third card is even?

• the second card is even given that the first card is odd?

• the second card is odd given that the first card is odd?

(this is problem 1.5.5 in Yates & Goodman [1])

[ source ]

__________

My solution:

Our experiment consists of shuffling the deck, dealing out the cards, and observing the sequence in which the three cards are dealt. Hence, each outcome or observation is a -tuple

and the sample space, the set of all observations, is thus

.

Note that . We assume that the six observations are equally likely, i.e., for all . Let denote the event that the -th card dealt is even numbered, and let denote the event that the -th card dealt is odd numbered. Recall that an event is a subset of the sample space and, thus, the event space (the set of all events) is . Hence, we have

and . Hence

and . Thus, the probability that the 2nd card is even given that the 1st card is even is the following

.

Interpretation: if the 1st card is even numbered, after the 1st card is dealt (and observed) there will be only two cards left in the deck, one even numbered and another one odd numbered, and these two are equally likely. Hence, we conclude that the probability that the 2nd card is even given that the 1st card is even is .

Since there are only two even numbered cards in the deck, we have . Therefore, the probability that the first two cards are even given that the 3rd card is even is

.

Interpretation: if the 3rd card is even numbered, then the two cards previously dealt must be odd and even numbered (not necessarily in that order, of course), as we only have two even numbered cards in the deck. Thus, it’s impossible to get three even cards and .

Note that . Hence, we have that . Therefore, the probability that the 2nd card is even given that the 1st card is odd is

.

Interpretation: if the 1st card is odd numbered, then only even numbered cards remain in the deck. Thus, we know for sure that the 2nd card will be even if the 1st is odd.

Since we only have one odd numbered card in the deck, we can’t have an observation / outcome with two odd numbered cards, i.e., . Hence, the probability that the 2nd card is odd given that the 1st card is odd is

.

Interpretation: if the 1st card is odd numbered, then only even numbered cards will remain in the deck. Thus, it’s impossible for the 2nd card to be odd when the 1st one is odd.

__________

References

[1] Roy D. Yates, David J. Goodman, Probability and stochastic processes: a friendly introduction for electrical and computer engineers, 2nd edition, Wiley, 2004.

How many dovetail shuffles suffice?

How many shuffles are necessary to randomize a deck of cards? Mathematically, card-shuffling can be viewed as a random walk on a finite group and, thus, it can be modeled by a Markov chain. We measure the degree of “randomness” of a deck of cards after shuffles using the Kullback-Leibler distance between the probability distribution of the Markov chain after shuffles and the uniform probability distribution. Lastly, we discuss an intriguing phenomenon that resembles a phase transition.

__________

Introduction

Imagine that we have a deck of cards. We assign number to the card at the top of the deck, number to the next card, and so forth, until we assign number to the card at the bottom of the deck. This ordered arrangement of cards can be represented by an -tuple . The simplest possible shuffle would be to take the card at the top of the deck and insert it at some random position in the deck, say, at the bottom. The new ordered arrangement of cards would then be represented by the -tuple . This shuffling technique is called the top-in-at-random shuffle [1]. In this paper, we will consider the dovetail shuffle instead [2].

In order to model the shuffling process, we need to introduce some mathematical terminology first. We define . Let denote the symmetric group on set , i.e., is the group that consists of all bijections with function composition as the group operation. The elements are called permutations. Given , then is the bijection obtained by applying first and then . Every ordered arrangement, or configuration, of a deck of cards can be associated with an element . A sequence of shuffles can be thought of as a composition of bijections , as follows

.

Hence, the card to which we assigned number , and that was at position initially, will be at position after shuffles. One can think of the shuffling process as a random walk on . Thus, we can define a Markov chain on . The shuffling method that one uses defines the transition probabilities of the Markov chain. It would be an interesting challenge to start with a desired transition probability matrix and try to design shuffling methods that yield a Markov chain as close as possible to the desired one.

Let us look again at the top-in-at-random shuffling example given above. If we take the top card and insert it at the bottom of the deck, then we know exactly which permutation we did apply. However, the goal of card-shuffling is to “randomize” a deck, and if we know which permutation was applied with each shuffle, then we know exactly the new ordering of the deck. This is desirable only if our purpose is cheating. Therefore, in order to randomize a deck of cards we must apply a sufficient number of permutations chosen at random from , so that there is enough uncertainty on what the new ordering of the deck of cards is. In this post we will study how many shuffles suffice to attain a desired level of uncertainty.

__________

The Dovetail Shuffle

The dovetail shuffle, or riffle shuffle, is a common card-shuffling method that consists of cutting a deck of cards in two packets, and then interleaving the two packets together. A variation is the -shuffle, which consists of cutting the deck in packets and then interleaving them all together. In this post, we will consider dovetail -shuffles only.

A rising sequence is defined by Bayer & Diaconis in [2] as a “maximal subset of an arrangement of cards, consisting  of successive face values displayed in order”. Initially, the ordered arrangement of the deck is for all and, hence, there is exactly one rising sequence. Each dovetail shuffle tends to double the number of rising sequences, until a saturation effect takes place due to the finiteness of the size of the deck. This is an “experimental” result that anyone can verify by playing with an actual deck of cards. Do note that:

• the minimum number of rising sequences in a deck of cards is . A deck with a single rising sequence is one in which the ordering of the cards is for all .

• the maximum number of rising sequences in a deck of cards is . A deck with rising sequences is one in which the ordering of the cards is for all .

• after dovetail shuffles, there are at most rising sequences.

We introduce function , where is defined to be the number of rising sequences in . From Bayer & Diaconis’ paper [2], we know that the probability mass function on after dovetail shuffles, , is defined by

.

Since we know the probability mass function on after shuffles, we can study shuffling from an information-theoretic viewpoint. In particular, we are interested in how the entropy of the probability mass function evolves as the deck is shuffled.

__________

Entropy Generation

The Shannon entropy [3] of the probability mass function is

After shuffles there are at most rising sequences in the deck. Therefore, we only need to sum terms

.

As mentioned in [2], the cardinality of the set is the Eulerian number . Let denote the probability for any , as follows

for .  The entropy of the probability mass function is thus given by

.

Hence, we can compute by summing terms (instead of summing terms), which makes the computation tractable for modestly large values of , assuming that the Eulerian numbers can be computed efficiently, of course. A non-recursive formula for the Eulerian number is

.

Using the expression for above to compute the entropy is potentially dangerous: the binomial coefficients may take values which are too big, and this might lead to numerical errors. Therefore, it would be wise to break up the binomial coefficients into products

and to write logarithms of products as sums of logarithms

.

However, do note that might take very small values as we might want to consider decks with, say, cards. A safer way would be to “combine” with the Eulerian numbers

.

Let the uniform probability mass function on , , be defined by for all . The entropy of the uniform probability mass function is

and, since the uniform distribution maximizes entropy, we conclude that . We denote . In [1] Aldous & Diaconis use an algebraic argument to show that as , i.e., the probability mass funtion converges to the uniform one as the number of shuffles tends to infinity. Therefore, we can conclude that as and, hence, for every there exists a such that implies that . If one is given a value of , then one can find how many shuffles suffice to attain an entropy higher than .

The question “how many shuffles suffice to randomize a deck of cards?” is ill-posed. One must specify a measure of “randomness” (in this post, we use the Shannon entropy to measure randomness) and a value of to measure how much randomness is “enough” for us to say that a deck is mixed.

As mentioned before, each dovetail shuffle tends to double the number of rising sequences, until saturation occurs. Hence, after dovetail shuffles, where is “small”, there should be rising sequences. We can make the approximation

which yields

and, thus

for “small” . We conclude that dovetail shuffling generates entropy at a rate of approximately bits per shuffle, until the deck becomes saturated. Using the approximation , we have that maximum entropy would be attained after approximately shuffles.

In figures 1 and 2 we plot (in blue) the normalized entropy as a function of the number of dovetail shuffles, , for decks of sizes and , respectively. We plot also (in red) the approximation , and we plot (in magenta) the maximum normalized entropy.

[ Figure 1: Normalized entropy as a function of the number of shuffles for a deck with cards ]

[ Figure 2: Normalized entropy as a function of the number of shuffles for a deck with cards ]

Note that, as predicted theoretically, the entropy increases in an almost linear fashion during the first few shuffles. In fact, the approximation is surprisingly good until for , and until for . For , we have , which is a rough estimate of the number of shuffles after which the deck becomes saturated.

__________

Approach to Uniformity

As shown by Aldous & Diaconis in [1], the stationary probability mass function of the Markov chain is the uniform one. Therefore, the entropy generated by dovetail shuffling converges to the maximum entropy. We measure how “close” to the maximum entropy we are after shuffles using the Kullback-Leibler distance [3] between the probability mass functions and , as follows

and, hence, we obtain

.

Since , we have that

.

We can rewrite the equation above in the form

,

or in the form

,

because among all probability mass functions on , the one that maximizes the entropy is the uniform distribution . Since the logarithm is a strictly concave function, we can use Jensen’s inequality [3] to obtain

and, therefore, we have the following upper bound on the Kullback-Leibler distance

.

Since , the inequality above can be rewritten as follows

.

Imagine that our initial probability mass function is a unit mass at permutation , i.e., , where is the Kronecker delta. If this is the case, then there is zero uncertainty and, hence, the entropy is , while the -norm is maximum, . At the other extreme, the uniform probability mass function has maximum entropy , but minimum -norm, . Hence, we have that

.

Since as , then we conclude that and, from inequality , we have that . For sufficiently large, the decay of is given by the second largest (in absolute value) eigenvalue of the transition probability matrix of the Markov chain. Hence, for large there exist constants and , such that

and, thus, . Applying logarithms, we obtain

where we used the inequality . From the inequality above and the inequality on the relative entropy, we conclude that for sufficiently large . Hence, the Kullback-Leibler distance converges to zero exponentially.

__________

Concluding Remarks

We have concluded that during the first shuffles, where , the dovetail shuffling process generates entropy at a rate of approximately bits per shuffle. However, when , then becomes and the sum in the formula for the entropy “saturates” in the sense that the number of terms being summed no longer increases with . For , the deck is saturated and entropy approaches the maximum entropy asymptotically, as decays exponentially. This interesting phenomenon resembles a phase transition and was pointed out by Trefethen & Trefethen in [4], while in [5] Stark et al. present detailed analytical results.

__________

References

[1] David Aldous, Persi Diaconis, Shuffling cards and stopping times, The American Mathematical Monthly, Vol. 93, No. 5, pp. 333–348, Mathematical Association of America, 1986.

[2] Dave Bayer, Persi Diaconis, Trailing the Dovetail Shuffle to its Lair, The Annals of Applied Probability, Vol. 2, No. 2, pp. 294-313, May 1992.

[3] Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, John Wiley & Sons 2006.

[4] L. N. Trefethen, L. M. Trefethen, How many shuffles to randomize a deck of cards?, Proceedings of the Royal Society of London, Vol. 456, No. 2002, pp. 2561-2568, 2000.

[5] Dudley Stark, A. Ganesh, Neil O’Connell, Information Loss in Card Shuffling, HP Laboratories Bristol, September 1999.

__________

Related:

• What is total variation distance?

• Card Shuffling I

• Card Shuffling II – The Riffle Shuffle