Fair but irregular polyhedral dice - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T06:01:44Z http://mathoverflow.net/feeds/question/46684 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/46684/fair-but-irregular-polyhedral-dice Fair but irregular polyhedral dice Joseph O'Rourke 2010-11-19T22:12:43Z 2011-12-11T21:49:27Z <p>I am interested in determining a collection of geometric conditions that will guarantee that a convex polyhedron of $n$ faces is a <em>fair die</em> in the sense that, upon random rolling, it has an equal $1/n$ probability of landing on each of its faces. (Assume the polyhedron is composed of a homogeneous material; i.e., it is not "loaded.")</p> <p>There has been study of what Grünbaum and Shephard call <em>isohedral</em> polyhedra, which always represent fair dice: "An <a href="http://mathworld.wolfram.com/Isohedron.html" rel="nofollow">isohedron</a> is a convex polyhedron with symmetries acting transitively on its faces with respect to the center of gravity. Every isohedron has an even number of faces." It is clear such a polyhedral die is fair. Here is an example of the <em>trapezoidal dodecahedron</em>, an isohedron of 12 congruent faces, from <a href="http://www.aleakybos.ch/Shapes.htm" rel="nofollow">an attractive web site on polyhedral dice</a>: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://people.csail.mit.edu/~orourke/MathOverflow/TrapDodeca.jpg" alt="trapezoidal dodecahedron"> <br /> But a clever argument in a delightful paper by Persi Diaconis and Joseph Keller ("<a href="http://www-stat.stanford.edu/~cgates/PERSI/papers/fairdice.pdf" rel="nofollow">Fair Dice</a>." <em>Amer. Math. Monthly</em> 96, 337-339, 1989) shows (essentially, by continuity) that there must be fair polyhedral dice that are not symmetric. For example, there is no reason to expect that equal face areas is a necessary condition for a polyhedral die to be fair. Nor is it reasonable to expect that the distance from each face to the center of gravity of the polyhedron is alone a determining condition. Rather it should depend on the dihedral angles between faces, the likelihood of one face rolling to the next&mdash;perhaps a <a href="http://en.wikipedia.org/wiki/Markov_chain" rel="nofollow">Markov chain</a> of transitions?</p> <p>My question is:</p> <blockquote> <p>Is there a collection of geometric conditions&mdash;broader than isohedral&mdash;that guarantee that a (perhaps asymetrical, perhaps unequal-face-areas) convex polyhedron represents a fair die?</p> </blockquote> <p>Sufficient conditions welcomed; necessary and sufficient conditions may be too much to hope for! Speculations and literature leads appreciated!</p> http://mathoverflow.net/questions/46684/fair-but-irregular-polyhedral-dice/46707#46707 Answer by sleepless in beantown for Fair but irregular polyhedral dice sleepless in beantown 2010-11-20T03:25:23Z 2010-11-20T03:25:23Z <p>Here's an argument for an irregular octahedral-prism die:</p> <blockquote> <p>Have two faces be regular octagons with edge-length $1$</p> <p>Have the prism height be $h$</p> <p>Call the $8$ rectangular prismatic faces with labels "1" through "8"</p> <p>Call the octahedral faces "9" and "10" or "top" and "bottom"</p> </blockquote> <p>It may require physical simulation to find the critical heights I am defining below, and it will obviously be a function of the material used to make the die , the surface onto which it is rolled, and of the frictional coefficients $\mu_{die}$ and $\mu_{felt}$, and the nature of the rolling mechanism used to toss the die onto the felt (most likely the tumbling action in 6-dimensional state-space describing the initial velocity and rotational movement of the die and the height at which it is released, etc.)</p> <p>Because of symmetry, we can say</p> <p>$p_{top}=p_{bottom}=x,$ </p> <p>$p_{i\in(1,8)}=y$,</p> <p>$2x+8y=1$,</p> <p>$0 \le x \le 1 \textrm{ and } 0 \le y \le 1$</p> <p>There will be a critical height $h_{min}$, where for $h \lt h_{min}$, the bias for "top" and "bottom" will be greater than for the prismatic faces, and $x \gt y$.</p> <p>There will also be a critical height $h_{max}$ where because the long axis is substantially longer than the flat octahedral faces, the momentum will be such as to cause a die landing on an octahedral face "top" or "bottom" to continue to move and fall/topple onto a rectangular prismatic face, with each of the 8 prismatic faces equally likely.</p> <p>Somewhere between the critical maximal and minimal heights will be a fair height, $h_{fair}$, where this non-regular die will roll fairly onto any of the ten faces with $$p=\frac{1}{10}=0.1$$</p> <p>Now this is a rotationally symmetric die with 8-rotations around the long axis and 2 orientations of the long axis, so it's not the "assymetric die" you've asked for, but it could be the beginning for a similar construction of an asymmetric die.</p> http://mathoverflow.net/questions/46684/fair-but-irregular-polyhedral-dice/46734#46734 Answer by Matt Fayers for Fair but irregular polyhedral dice Matt Fayers 2010-11-20T13:03:45Z 2010-11-20T13:25:17Z <p>I occasionally get essentially this question from non-mathematicians, some of whom are very pleased with their appeal to the Intermediate Value Theorem. But I always reply that the whole discussion is absolute nonsense: the only possible notion of a fair die is an isohedral one, because for any other die, <i>it depends how you throw it</i>.</p> <p>What do we mean by saying that a die is equally likely to land on any of its faces: what is the random element? In theory, if we could accurately measure the speed and spin of the die as it is released as well as coefficients of friction and restitution etc, we could work out in advance which face the die will land on, so in this sense there is no randomness. The randomness only arises when you choose how to throw the die: the thrower selects from a continuum of "possible throws", and we assume that he samples from some probability distribution on this continuum. Morever, there is an action of the rotation group of the die on this continuum, and what we mean by saying that an isohedral die is fair is that we assume the probability distribution the thrower uses is invariant under this action. There is no sensible further assumption that we can make about the probability distribution which will ensure that two faces of the die which are not in the same orbit under the rotation group will occur equally often. However "obvious" it is that an octagonal coin is very unlikely to land on its edge, and a pencil is very unlikely to land on its end, there's no meaningful way to find a happy medium between these. So there is no meaningful mathematics to be done here. (Feel free to substitute "pure" for "meaningful" in the last sentence.) If you wanted to make a machine to throw a die in a standard way, then you'd have no chance of making a fair die, because with a perfect machine the die would always land on the same face.</p> <p>Incidentally, the above discussion suggests that even isohedrality is not enough for a fair die - we require there to be only one orbit of faces under the rotation group of the die, not the full symetry group.</p> http://mathoverflow.net/questions/46684/fair-but-irregular-polyhedral-dice/46740#46740 Answer by Joseph O'Rourke for Fair but irregular polyhedral dice Joseph O'Rourke 2010-11-20T15:13:46Z 2011-12-09T13:25:23Z <p>This is an attempt to respond to the incisive comments of Steve Huntsman, Tom Goodwillie, Matt Fayers, and Ori Gurel-Gurevich; too long for a comment, and not an extension of the question.</p> <p>Let me suggest a model as follows. The polyhedron $P$ is oriented randomly, and then dropped from a height $h$ onto an infinite plane. Let $k$ represent some measure of elasticity between the material from which $P$ is composed and the material of the floor plane, and let $\mu$ be a coefficient of friction between $P$ and the floor. Then the probability $p_i$ that $P$ will come to rest on face $i$ is some function of these three parameters: $p_i( h, k, \mu )$. Although there seems no question that $p_i$ does vary with these three parameters, my intuition is that, within a wide range of "reasonable" values for the parameters, $p_i$ is nearly constant. I would especially expect this to hold if $P$ is "round," say, all the vertices of $P$ lie on a sphere ($P$ is <em>inscribed</em>). And then if all the $p_i$ were nearly constant and equal, I would declare this a fair die.</p> <p>I will admit that I cannot flesh out this intuition. And even if I could, it may be that Matt is correct that "there is no meaningful mathematics to be done here." But I retain some hope.</p> <hr> <p>Let me use this non-answer to display an image of a heptahedron that follows the Diaconis-Keller/sleepless construction, but in which I adjusted the dimensions to satisfy Benoît Kloeckner's idea of equal solid angles, in this case about 1.795 steradians per face, which is $4 \pi / 7$: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://people.csail.mit.edu/~orourke/MathOverflow/Heptahedron.jpg" alt="Heptahedron"></p> http://mathoverflow.net/questions/46684/fair-but-irregular-polyhedral-dice/46774#46774 Answer by sleepless in beantown for Fair but irregular polyhedral dice sleepless in beantown 2010-11-20T20:38:52Z 2010-11-23T06:25:40Z <p>I just noticed Joseph's comment in his question about Markov chains. My observations about the correctness of trying to use Markov chains to describe the rolling of a die, fair or unfair:</p> <p>If by <em>state</em> in the Markov chains, you mean just the "face" it is currently on or the "face" which is lower-most in attitude at a particular point in time, then it is inappropriate to use Markov chains because the likelihood of transitioning from die face $F_i$ to die face $F_j$ is not purely dependent upon the current state. If $F_j$ and $F_k$ are two "faces" adjacent to face $F_i$, then the likelihoods of transitioning $F_i \to F_j$ vs. $F_i \to F_k$ is not just dependent on the "current state" being $F_i$, but also dependent upon the velocity, position, and orientation of the die. The "faces" are necessary but <strong>not sufficient</strong> to encode state in such a way for Markov chains to be applicable: that the Bayesian requirement that "current state" at time $t$ is all that is needed to be known in order to be able to predict the likelihood of the state at time $t+1$ (if you talk about discrete time) or time $t+\varepsilon$ if you talk about continous time.</p> <p>If by "state", you try to get around this factor that only current state be considered and not the history of how you came to currently be in that state, then you could try to add the vectors of position, velocity, and orientation as extra "states", which is valid in numerical simulation, because ultimately all reals are still encoded into limited precision "floating point" representations of reals. However, the transition table would be huge if you allowed even for 16-bit floating point representation.</p> <p>I do not think that history-less "Markov chains" can be applied in this situation.</p> <p>older answer components below</p> <hr> <p>To answer Benoît Kloeckner's comment that &lt;&lt;[then] the solid angle under which each face is seen from the center of gravity alone would determine the probability of the dice landing on that face. But to determine all polyhedra for which this solid angle is constant is already a nice problem.>></p> <p>I don't believe that having similar solid angles is sufficient to determine the equal probabilities of the die landing on faces with similar solid angles.</p> <p>Here is a construction for 2-d die (which can easily be converted into prismatic die, disregard if the die lands on "top" or "bottom" face, and look at the relative probabilities of landing on the prismatic faces)</p> <p>Using polar coordinates $(r,\theta)$ , let's define a fair hexagonal die's profile as the closed path determined by the six vertices at </p> <p>$(1,\frac{\pi}{3}), (1,\frac{2\pi}{3}), (1,\pi), (1,\frac{4\pi}{3}), (1,\frac{5\pi}{3}), (1,{2\pi})$</p> <p>Now let us define an unfair hexagonal die's profile as the path defined by the polar coordinates</p> <p>$(1,\frac{\pi}{3}), (1,\frac{2\pi}{3}), (100,\pi), (1,\frac{4\pi}{3}), (1,\frac{5\pi}{3}), (100,{2\pi})$</p> <p>Now this die's center of mass (center of gravity) remains at $(0,0)$ since the material the die is composed of has uniformly homogeneous density. This unfair die also has each prismatic face subtending equal solid angles (and equal angles of $\pi/3$ for each edge in the $2$-dimensional case), however the this unfair die is highly biased towards landing on two faces to the detriment of the other four faces probabilities.</p> <p>Thus Benoît Kloeckner's conjecture that</p> <p>"the solid angle under which each face is seen from the center of gravity alone would determine the probability of the dice landing on that face"</p> <p>is incorrect.</p> <p>In fact, using this polar coordinate approach, it can be seen that using <em>any</em> three radii greater than $0$ in length yields a rotationally symmetric die profile with <em>equiangular faces</em> (<strong>edges which subtend equal angles in $2$-d, prismatic faces which subtend equal steradians of solid angle in $3$-d</strong>) and with center of mass still at $(0,0)$:</p> <p>$(r_1,\pi/3), (r_2,2\pi/3), (r_3, \pi), (r_1,4\pi/3), (r_2,5\pi/3), (r_3,2\pi)$</p> <p>but very few of these would be fair. Particularly the non-convex profiles, which also are equiangular, but make it possible to land on pairs of vertices/edges without landing on a specific face</p> http://mathoverflow.net/questions/46684/fair-but-irregular-polyhedral-dice/48689#48689 Answer by Robert Connelly for Fair but irregular polyhedral dice Robert Connelly 2010-12-08T23:30:00Z 2010-12-08T23:30:00Z <p>Joe,</p> <p>Here is convex polytope that could be a fair die. Consider the rhombicuboctahedron which is one of the Archimedean solids. There are three rings of square faces, each of which divides the polyhedron in half. Take one of these rings and rotate the top half by 45 degrees. This is a famous "fake" Archimedean solid. The symmetry group of this polytope is not transitive on all its vertices. There are two orbits of vertices of 8 and 16 vertices each. Take the dual of this polytope. Each face is a deltoid/kite. All 24 faces are congruent and at the same distance from the centroid, but it is not isohedral. I think that all the second moments are equal as well. Is this a fair die?</p> <p>Bob C.</p> http://mathoverflow.net/questions/46684/fair-but-irregular-polyhedral-dice/49480#49480 Answer by Bill Thurston for Fair but irregular polyhedral dice Bill Thurston 2010-12-15T03:10:44Z 2010-12-15T15:09:59Z <p>Depending on rules and technique, a person throwing a die can reasonably control the amount of angular momentum, the total kinetic energy when it first lands and the angle of its trajectory.</p> <p>I want to suppose that the collisions of the die with the throwing surface have a reasonably high coefficient of restitution, enough that the die will undergo a good number of hits on the surface before it comes to rest. (One could imagine an alternate model, where the main randomization is by shaking the die before throwing, and the die stops where it lands ---- but that's not hte situation I want to discuss).</p> <p>I think there's a reasonable range of polyhedral die shapes and energies where if the bouncing were completely elastic, the system would be ergodic --- the possible positions and motions of the die, up to translations in the plane of the throwing surface, would be visited a.s. in proportion to their measure among all states of the same energy. If the surface of the die were smooth, but just marked off into different areas of contact, this would not generally be true: KAM theory (small divisors and invariant tori) very often makes it non-ergodic. If the die can act like a top, it's not ergodic at that energy level. But I think of the rolling die more like a particle bumping into numerous obstacles, and systems like that are often ergodic.</p> <p>The rolling of a real die is not perfectly elastic, and kinetic energy is gradually lost. </p> <p>Here's a hypothesis that should guarantee fairness in the limiting case where energy is lost very slowly: Let's suppose we have a rule to partition phase space into sets $A_i$ associaed with the different possible outcomes. We want</p> <ol> <li><p>The intersection of $A_i$ with each energy level E has volume $V(E)$ independent of $i$.</p></li> <li><p>The dynamics is ergodic in each component of each energy level that intersects more than one $A_i$.</p></li> <li><p>The labeling by $A_i$ depends reasonably on energy level --- for every pair of nearby energy levels $E$ and $F$, for most $x$ at energy level $E$ and most $y$ in energy level $F$ such that $d(x,y) &lt; \epsilon$, $x$ and $y$ are in the same state. Also, the labeling shouldn't tunnel to a different connected components of the phase space of energy $&lt;\le E$: the ratios of measure of $A_i$ intersected with each connected component of an energy level should stay the same.</p></li> </ol> <p>With these hypotheses, with sufficiently slow loss of energy, the final state should be uniformly distributed. </p> <p>If the dynamics at enough energy levels also has reasonably high entropy and is mixing (I think both are likely to be true for reasonable die shapes), then the uniformization should occur fairly well at realistic rates of energy loss.</p> <p>The big difficulty though is condition (1). I think that pretty often, even with a symmetric die, the phase space becomes disconnected well before the die comes to rest. </p> <p>For a standard cubical die, what are the components of phase space just above where it settles on a face? I think it can roll on 4 sides and not have enough energy to switch which four sides. At the same energy level, it might be spinning slowly on a vertical axis on one face. If so, that would make 9 components, 6 of which are already committed to one face. These are the kinds of things one would need to understand to show an asymmetrical die is fair. With more complicated dice, the fragmentation into components looks much trickier.</p> <p>The volume of phase space must be equitably apportioned at each transition where the phase space disconnects, until the final outcome is determined, otherwise one could influence the outcome by the energy of the throw.</p> <p>Connely's suggestion of a twisted deltoidal Icositetrahedron might work, but it might fail the test (1) as energy levels are decreased. Even though each face is the same, I'm not convinced that the fragmentation into continents, before the die has settled on one face, would be fair, since it presumably depends on bigger neighborhoods that are not exactly the same. </p> <p>If one understood in detail how the components of energy levels separate and if there aren't too many of them, then one should in principle be able to engineer a die to be fair with the help of the Brouwer fixed point theorem (multi-dimensional intermediate value theorem). It would appear to be quite a challenge, though, for all but the simplest examples when there is only a small number of symmetry classes of faces.</p> <p><strong>Proving</strong> 2 seems like a significant challenge. My guess could be wrong, it might usually be non-ergodic. It's worth thinking about in it's own right.</p> <p><strong>Further thoughts</strong>: Actual dice are made with rounded edges and rounded corners. How this rounding is done seems significant.<br> If the projected image of a die along a certain axis is almost round, then at low energy levels it should roll more easily about those axes than about axes where the projection is bumpy, other things being equal. This suggests larger components of the phase space for these kinds of rolls, when the phase space becomes disconnected. Also, it depending on the details of the shape, it seems likely there are ergodic components associated with rolling at energy levels above where the phase space becomes disconnected --- this is similar to the stability of a wheel rolling on somwhat bumpy terrain, which is explained by KAM theory.</p> <p>It seems interesting to try to design shapes that <em>appear</em> fair, but are not, by exploiting this kind of behavior: creating rolling modes or rocking modes that, as the die settles down, tend to funnel the behavior into preferred outcomes.</p> http://mathoverflow.net/questions/46684/fair-but-irregular-polyhedral-dice/83037#83037 Answer by Scott Sherman for Fair but irregular polyhedral dice Scott Sherman 2011-12-09T06:45:29Z 2011-12-11T21:49:27Z <p>Yes, there are conditions broader than isohedral symmetry that guarantee a convex polyhedron represents a fair die. Consider a teetotum or dreidl. These shapes aren't isohedra, but they are mathematically fair dice in the sense that each face has an equal chance of being rolled. True, they're not convex, but you can only land on the convex hull, so you could either consider them effectively convex or easily modify them so they're convex while preserving the property of being non-isohedral fair dice.</p> <p><img src="http://loki3.com/poly/pictures/dreidl.jpg" width="350" /></p> <p>Those shapes are examples of a class of object I call polyisohedra ( <a href="http://loki3.com/poly/polyisohedra.html" rel="nofollow">http://loki3.com/poly/polyisohedra.html</a> ), where <em>sets</em> of faces are equivalent. A polyisohedron modified with the proper polyisohedral symmetry preserves the property of being a fair die, which is how I derive teetotums and dreidls from this more general category of fair dice.</p> <p>A simple example of a polyisohedron is a cube where you combine adjacent pairs of faces to essentially make a fair 3 sided die. More interesting, however, are cases where you <em>have</em> to combine multiple faces to make the shape into a fair die. One example is a gyrobifastigium, a Johnson solid with 4 square faces and 4 equilateral triangle faces. Obviously it's not a fair 8 sided die, but if you give the same label to square-triangle face pairs, you end up with a fair 4 sided die. For this shape, the triangular sides aren't stable, so you can only land on the square faces, but this isn't a required feature. However, unstable faces are used in other non-isohedral shapes commonly used as fair dice, such as barrels.</p> <p><img src="http://loki3.com/poly/images/gyro1.png" width="400" /></p> <p>I have more examples and details posted at <a href="http://loki3.com/poly/fair-dice.html" rel="nofollow">http://loki3.com/poly/fair-dice.html</a>.</p> <p><img src="http://loki3.com/poly/pictures/fair-dice.jpg" width="500" /></p> http://mathoverflow.net/questions/46684/fair-but-irregular-polyhedral-dice/83076#83076 Answer by Valerio Capraro for Fair but irregular polyhedral dice Valerio Capraro 2011-12-09T21:27:55Z 2011-12-09T21:27:55Z <p>This is a tentative to solve the questions that arose in Matt Fayer's answer and comments, regarding the impossibility of a fair experiment.</p> <p>Appealing to Information Theory, it is established that randomness is equivalent to the lack of information. More formally, uniform measures are the one that maximize Shannon's entropy. Conversely, complete knowledge is equivalent to Dirac measures. From this point of view it is clear that a perfect machine, where perfect means indeed complete knowledge, can do whatever you want and, in particular, is able to land a die always on the same face (this is a Dirac measure!). </p> <p>After these observations, it seems to me clear that a fair throwing can be simulated imposing the lack of knowledge: the person who throw the die must be blinfolded; (s)he has to throw the die uniformly (i.e., as already suggested, chosing the Haar measure on $SO(3)$) - this can be forced using heavy gloves, but also more naturally using die with a uniform structure (I will come back to this point in a moment). On the other hand, a person who bet on the die is not allowed to use any other tool but his own eyes, in the case of uniform structure (in case of <em>heavy gloves</em>, he's blinfolded either). In this case, the Nash equilibrium of the ideal game between the two players (who throws and who bets) is the uniform measure on the number of faces of the die; i.e. the experiment is fair.</p> <p>A comment about uniform structures: this probably brings to classical interpretation more or less discussed in other answers: I am thinking of a cube; more specifically, keeping this analogy with the real-world, I am thinking to something with the following property: if you close your eyes and you are allowed only to touch the die, then you cannot distinguish two different faces and the edges are trascurable; i.e. since the set of human beings is finite, take $\epsilon$ small enough such that every <em>imperfection</em> of the die is smaller than $\epsilon$.</p> <p>P.s. maybe I should write this somewhere, but an important observation to keep in mind is that fairness, randomness, knowledge and so on are subjective. Something can be really random iff it is perfectly isolated.</p>