Posted by: gupta2 | November 26, 2008

## Magic Dice: the math behind something that doesn’t yet exist

Introduction: For my reading project I chose to review the article, “Magic Dice” by Bernard D. Flury, Robert Irving, and M.N. Goria. This article seeks to explain the workings of a game of two non-independent dice (called magic dice) between a magician and a player. For 1/3 of the roll outcomes the player wins and for 1/3 of the outcomes the magician wins. For the remaining 1/3 of the outcomes no one wins. The probabilities of the outcomes where the player would win are zero while the probabilities for the outcomes where the magician wins are 2/(# of sides on dice). The remaining outcomes where no one wins all have probabilities of 1/(# of sides on the dice). An example joint probability function for six sided dice (taken from the paper) is shown below:

Consider a group of people watching this game played. After a few plays, everyone will notice the game is rigged in favor of the magician. However, if two viewers are chosen to document the marginal probabilities of each die, they will find every face has equal probability of being thrown just like a fair die. If more observers were invited to keep track of linear combinations of the form aX+bY where X and Y are the values of the first and second dice and a and b are real numbers, then until a certain number of observers is reached, no one will detect anything different from the distributions of fair dice. The number of people that can have unique linear combinations to keep track of and not notice anything different from fair dice is known as the magic number, which varies with the number of faces on the dice. For six sided dice the magic number is 5. The purpose of the paper is to find out the magic number for k-sided dice where k is greater than or equal to 2. It is important to note that the only way to have a “magic” joint probability distribution is if the outcomes of the two dice are dependent which is (as far as I know) physically impossible. The authors chose not to state this until the conclusion so I spent some time wondering how such a joint distribution was actually possible.

Mathematical Definition of Magic Numbers

If we define k as the # of faces on the dice where k is greater than or equal to 2, then we can have the ordered pair (X,Y) where X and Y are the values of the first and second dice. In this case, (X, Y) will be able to take values from the set {1,2, …, k}x{1,2, …, k} with probabilities pij, where i corresponds to X and j corresponds to Y.

A linear combination Z=aX+bY is defined as proper if its probability distribution is unchanged by setting all pij =1/$k^2$.  m(k), the magic number, is defined as the number of different proper linear combinations that can exist for a joint probability distribution where every outcome is not equal to 1/$k^2$. Since an infinite number of linear combinations can be created if a and b take any values of the real numbers, it makes sense to limit which linear combinations can be made. This is done by defining a feasibility set, , for the pairs of integers (a,b) where

Now we define U as U=[uij] where uij$k^2$*pij. This effectively creates a matrix of the joint probability distribution and effectively gets rid of the denominators by multiplying every probability by $k^2$. For (a,b)$\in$aX+bY will produce a number, Nk(a,b), of linear equations of the variables uij. Using the example from the paper, k=3 and (a,b)=(1,1) produces 5 equations:

These equations can be rewritten in the form:

C(a,b)vec(U’)=C(a,b)1k^2 (Note:The vec-operation stacks the columns of a matrix on top of each each other.)

For k=3 and (a,b)=(1,1),

For a subset , equation 2 above must be solved to find the probabilities of each outcome. There are two cases that must be considered:

1.     : vec(V’)=0 is the only solution. This means U=1k1’k and pij =1/k^2 for all i and j.

2.     : multiple solutions exist. vec(V’)=0 is still a solution. m(k) is the largest cardinality of all subsets  such that  .

Using these formulas, lots of Gaussian elimination, and then checking every linear combination in the feasibility set the authors with the help of a computer produced the following table that shows the magic numbers of dice with 2 to 24 sides:

Using this method the authors were also able to find the joint probabilities needed for magic dice with 14 sides:

Two of the intuitive findings that the authors found and later proved mathematically were:

In summary, this means that the magic number is increasing with the number of sides on the dice and has no upper limit.

Although this method works it is computationally inefficient. Later in the paper, the paper show how m(k) can be expressed in terms of the Euler totient (phi) function. Using the totient function and the results shown earlier a function can be produces that approximately describes the magic number’s behavior. Since a lot of this math has not been discussed in class and to contain the length of this review, I will just reproduce the function here:

A graph of this function is shown below:

Example joint probability distributions for k=3 and 4

From the Table 2 from the paper’s results we know the subsets  for any k less than 24 that must have the equation solved for them. From this data we can find a joint probability distribution and a magic number for a k value.

For k=3 the subset  is (1,0), (0,1), (1,1). The corresponding C matrix has rank 8 which is less than k^2=9. Therefore there are multiple solutions to the equation that will produce magic joint probability distributions. An example distribution is shown below:

 X across, Y down 1 2 3 1 1/9 2/9 0/9 2 0/9 1/9 2/9 3 2/9 0/9 1/9

In this example, all of the marginal probabilities are equal to 1/3 meaning these dice will look like fair dice. For the magician to continue with his unfair game he would chose to win on (2,1), (3,2), and (3,1) and would allow the player to win on (1,2), (2,3), (3,1). If we look at the number of different linear combinations from our feasibility set needed before we find a distribution error, it is 3 telling us that the magic number is 3 for this distribution. This value is lower than the value the m(k) approximation produces which is 3.665.

For k=4 the subset  is (1,0), (0,1), (1,1), (1,-1). The corresponding C matrix has rank 15 which is less than k^2=16. Therefore once again there are multiple solutions to the equation that will produce magic joint probability distributions. An example distribution is shown below:

 X across, Y down 1 2 3 4 1 1/16 0/16 2/16 1/16 2 0/16 1/16 1/16 2/16 3 2/16 1/16 1/16 0/16 4 1/16 2/16 0/16 1/16

In this example, all of the marginal probabilities are equal to 1/4 meaning that these dice will have similar distributions to fair dice. Here the magician would chose to win on (3,1), (4,2), (2,4), and (1,3) and the player would win on (1,2), (2,1), (3,4), (4,3). The number of linear combinations from the feasibility set we can observe until the distribution break is 4 so 4 is our magic number. This is close to the approximation produced by the m(k) approximation which produces m(4)=4.440.

It is important to remember that because rank of the C matrix for k=3 and k=4 are less than $k^2$, there are multiple distributions that will fit the criteria necessary for being a magic distribution. The two distributions shown are just two of the many possibilities.

Conclusion

The most important take away from the paper is the idea that marginal distributions do not necessarily convey joint probability distributions. In actuality, the two can be vastly different, as we have seen. The question posed in this paper is actually somewhat confusing since in reality unfair dice such as these (ones that are dependent on each other) do not exist (or at least that I know of). However, despite this reality flaw, the paper is definitely interesting and answers the question posed in the introduction in great depth. The results of the magic distributions can be related to magic squares (http://en.wikipedia.org/wiki/Magic_square), matrices where all the columns and rows add up to the same number. The columns and rows in magic squares can be said to be analogous to the marginal probabilities of each face of a die. A quick Google search on magic squares tells us that magic squares are the basis of the popular Sudoku puzzles you often see in some newspapers (http://plus.maths.org/issue38/features/aiden/). Do you think it’s possible that the results of this paper could be used to create a Sudoku solving algorithm that utilizes the value of the magic number approximation? Hmm, maybe Kate will give bonus points to someone who finds out.

Reference:

Magic Dice

Bernard D. Flury, Robert Irving, M. N. Goria Source: The American Mathematical Monthly, Vol. 106, No. 4 (Apr., 1999), pp. 324-337 Published by: Mathematical Association of America Stable URL: Accessed: 29/10/2008 13:12