Wikipedia:Reference desk/Archives/Mathematics/2020 May 13

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 13

Probability of a particular dice being highest when rolling multiple dice

I have a tabletop RPG I am planning to run which uses a slightly unusual dice system, and I'm trying to work out the probability of each result.

You have a cup of dice, which contains a number of 6 sided dice (d6), a number of 8 sided dice (d8), and a number of 10 sided dice (d10). You roll all the dice, and the result depends on which of the dice shows the highest number. For example, if you roll 2d6+1d8, and get a 3 and 4 on the d6, and a 2 on the d8, then the result is "d6 highest" (the actual number rolled doesn't matter, just the identity of the dice which rolled it)

The relevant results are:

• Whether there are multiple dice tied for highest, including at least two d6 (any other dice in the tie are irrelevant) (e.g. if you rolled 2d6: 5, 5; 1d8: 4; in the above example)
• Whether there are multiple dice tied for highest, including at most one d6 (no need to distinguish further based on the type of dice which are tied) (e.g. if you rolled 2d6: 6, 3; 1d8: 6; in the above example)
• When there is a single highest dice, whether this is a d6, a d8, or a d10

The number of each type of dice in your cup can change as the game progresses, so ideally I'd want a generic expression for the probability of each result for, e.g. Ad6 + Bd8 + Cd10 (where A, B, and C are 0 or positive integers).

My statistics knowledge is sufficiently rusty that I'm struggling to work out how to calculate this, so a prod along the right path would be helpful!

(For context, typical numbers would be 3 to 8 d6, and up to 2 of each of the other dice. The original system I'm basing this on is rather NSFW, and unlikely to have useful extra context, so I'm not going to link it here.) BadIdeasBureau (talk) 10:21, 13 May 2020 (UTC)

Before I consider this, could you clarify a bit? By "relevant results", do you mean, "the questions I'm interested in"? And do "Whether"/"When" mean, "What is the probability that"?  --Lambiam 11:27, 13 May 2020 (UTC)

Yes, the probabilities I want to know are the probability of each type of tie, and the probabilities of the highest single die being a d6, d8, or d10 respectively. BadIdeasBureau (talk) 11:31, 13 May 2020 (UTC)

OK, this is more a matter of combinatorics than of statistics. It looks elementary, but a bit tricky to get everything right, what with all the quirks. I'll give a start for the first question. There, a roll in which the highest value is greater than $6$ does not count, since then any tie cannot involve the d6. If you know the highest value, and it is at most $6$, you only need to know the d6 values to see if there is a tie involving at least $2$ d6. So, as a starter, I'll tackle the case where $B=C=0$. If we give each of the d6 an individual identity, there are $6^{A}$ possible combinations. How many of these have a tie with a high value $H$ (so $1\leq H\leq 6$)? There are $H^{A}$ combinations in which each die's number of eyes is at most $H$. There are $(H{-}1)^{A}$ combinations in which each die's number of eyes is below $H$. The difference is the number of combinations with at least one high value $H$. To get the number with at least two, we need to subtract the number of combinations with precisely one high value, which is $A(H{-}1)^{A{-}1}$. So the number with a tie of a repeated $H$ is:

$t_{H}=H^{A}-(H{-}1)^{A}-A(H{-}1)^{A{-}1},$

which equals the sum of the terms of the binomial expansion of $(1+(H{-}1))^{A}$, excluding the last two terms. (The formula still "works" for $A=1$, evaluating to $0$, but breaks down for $A=0,H=1$.) We need to sum $t_{H}$ for $H=1,...,6$ to get all d6 ties. Unfotunately, there is no pretty closed formula for this for general $A$, so we can't do much better than

$\sum _{H=1}^{6}H^{A}-(H{-}1)^{A}-A(H{-}1)^{A{-}1}.$

To get the probability, divide by $6^{A}$.  --Lambiam 13:13, 13 May 2020 (UTC)

This sounds too messy to do in your head while playing a game, if that's what you were hoping. An exact symbolic calculation would also be messy. You are basically comparing several multinomial distributions. See Rollout (backgammon) for a simple approach you could use with a computer, that you can make exact if the number of dice is not too large, or approximate otherwise. 2601:648:8202:96B0:3567:50D5:8BFF:4588 (talk) 12:47, 14 May 2020 (UTC)

For the general case, including $B\neq 0$ and/or $C\neq 0$, there are, in total, $6^{A}{\cdot }8^{B}{\cdot }10^{C}$ possible outcomes of a roll. As before, we count how many of these satisfy the conditions when the highest value shown equals $H$, and then sum over all possible values of $H$. Division by $6^{A}{\cdot }8^{B}{\cdot }10^{C}$ then gives the probability.

For the first question, a tie involving two d6, we need to distinguish two cases separately. The first of these is the case $1\leq H\leq 6$, the second is $7\leq H\leq 10$. When $1\leq H\leq 6$, there is a d6 tie if and only if two d6 show $H$, which, as we saw, is the case for $t_{H}$ d6 combinations as defined above. This is only for the d6; to get the number of combinations for all dice together, we have to multiply this by the number of d8–d10 combinations that does not show a higher value. There are $H^{B+C}$ of such. So for the case $1\leq H\leq 6$, expanding $t_{H}$, we get:

$\sum _{H=1}^{6}(H^{A}-(H{-}1)^{A}-A(H{-}1)^{A{-}1})\cdot H^{B+C}.$

For the second case, $H>6$, no d6 can be tied for highest value, so there are a grand total of $0$ possible combinations. So the last sum is the complete answer.

Now we turn first to the last question, with no tie. For the $H$ die being a d6, there are, as already stated above, $A(H{-}1)^{A{-}1}$ d6 combinations with one $H$ and no higher values. This has to be multiplied by $(H{-}1)^{B+C}$, the number of d8–d10 combinations that remain below $H$. As before, if $H>6$ the high value is not for a d6, so again no contribution to the total. Summing up, the number of tie-less combinations in which a d6 shows the highest eyes is:

$\sum _{H=1}^{6}A(H{-}1)^{A{-}1}\cdot (H{-}1)^{B+C}.$

For a d8 to show the non-tie high, $H$ must be at most $8$. For the d8, we have $B(H{-}1)^{B{-}1}$ combinations with one high $H$. For the d10, there are $(H{-}1)^{C}$ acceptable combinations. If $1\leq H\leq 6$, then for the d6, $(H{-}1)^{A}$ combinations are acceptable, but if $H>6$, all $6^{A}$ combinations will do. Summing their product results in

$\sum _{H=1}^{6}(H{-}1)^{A}\cdot B(H{-}1)^{B{-}1}\cdot (H{-}1)^{C}~+~\sum _{H=7}^{8}6^{A}\cdot B(H{-}1)^{B{-}1}\cdot (H{-}1)^{C}.$

For a d10 being a lone high, we obtain analogously

$\sum _{H=1}^{6}(H{-}1)^{A+B}\cdot C(H{-}1)^{C{-}1}~+~\sum _{H=7}^{8}6^{A}\cdot (H{-}1)^{B}\cdot C(H{-}1)^{C{-}1}~+~\sum _{H=9}^{10}6^{A}\cdot 8^{B}\cdot C(H{-}1)^{C{-}1}.$

The middle question involves all remaining combinations, so subtract the sum of these summations from $6^{A}{\cdot }8^{B}{\cdot }10^{C}$.  --Lambiam 21:31, 15 May 2020 (UTC)

Flipping a pentagon.

Consider a regular pentagon on an x-y grid initially set so that two neighboring vertices are at (0,0) and (1,0) and the other three have positive y coordinates. Consider a "flip" replacing a pentagon with another pentagon where both pentagons share two neighboring vertices. Questions.

1. What are the possible x,y coordinates for a vertex in a pentagon that can be gotten from flips (any number) from the starting location?
2. Can some number of flips lead to a pentagon with a vertex at (0,0) that isn't some variety of "retracing your steps" (or to put another way, where if it takes N steps, that the position at N-1 isn't the same as it was after the first flip)
3. Presuming the answer to #2 is no, is there any easy way to calculate how many flips it would take to get a pentagon with a vertex within a specific distance (say 1/2) of the origin?Naraht (talk) 14:16, 13 May 2020 (UTC)

This is much easier to deal with if you think of everything happening in the complex plane instead of the x-y plane. Let $\rho =e^{\frac {i\pi }{5}}$, so ${\bar {\rho }}=\rho ^{-1},\rho ^{5}=-1$ and let $\varphi =\rho +{\bar {\rho }}$ be the golden ratio. Then the five vertices of the original pentagon are $0,\ 1,\ \varphi \rho ,\ \varphi \rho ^{2},\ \rho ^{3}.$ The five flips around the original pentagon are given by $z\rightarrow {\bar {z}},\ z\rightarrow -\rho {\bar {z}},\ z\rightarrow \rho ^{2}{\bar {z}}+\rho ^{3}+\rho ^{4}$ and two others which I'm not bothering to compute right now. It's a exercise in elementary group theory to show that the any flip, whether on the original pentagon or one of the subsequent pentagons, is a composition of these five maps. So what you're really looking for are the orbits of the original five vertices under the group generated by the five reflections above. To answer #2 first, if you repeatedly flip on the edges adjacent to a single vertex, alternating sides each time, you get back to the original pentagon after 10 flips. So the answer to 2 is yes. Question #3 depends on the answer to #2 being no, but modifying it accordingly, the five maps listed above all map algebraic integers to algebraic integers, so the orbits consist of algebraic integers. This implies that some distances from the origin are impossible; the distance from the origin to an algebraic integer must in turn be an algebraic integer, but 1/2 (for example) is not an algebraic integer, so you can never get to a vertex with distance 1/2 from the origin. (Each orbit is also a subset of $\mathbf {Q} [\rho ],$ an example of a cyclotomic field. Not sure if that's relevant to the question at hand though.) For the first question, the group is generated by reflections and such groups for which the orbits are discrete are well studied, see reflection group. This isn't one of them though and I strongly suspect that the orbits will be dense in the complex plane. Probably the easiest way to check is to just write a short program to list a few thousand of the points and plot them. I'm guessing the orbits taken as elements of $\mathbf {Q} [\rho ],$ are discrete, but this has two additional dimensions to move around in. You might want to look into the Penrose tiling P1 since this has pentagons and some of they are connected to each other by reflections. Not every reflection is applied to every pentagon though and the pentagons do not fill up the entire plane. --RDBury (talk) 18:13, 13 May 2020 (UTC)

RDBury The fact that continuing to flip on a single vertex adds 108 degrees and 10 rotations is a multiple of 360 degrees is another way to look at it. I agree that some distances (like 1/2 are not possible), but I *think* that for any epsilon greater than zero, it is possible to get a vertex to a point closer than epsilon to one of the original vertices (excluding going back *exactly* to that vertex. Interesting idea on the penrose tiling.Naraht (talk) 14:02, 14 May 2020 (UTC)

@Naraht: take a pentagon with one side in the X axis and one side in the Y axis. Flip it with respect to X axis, then Y axis and once more X and Y. The pentagon returned to the original position with no 'retracing'. You can also do that in 3 steps if the respective sides make the angle of 120 degrees. --CiaPan (talk) 14:47, 14 May 2020 (UTC)

Or, make a pentagon with an angle of 1 degree at (1,0). Then flip it 360 times around that vertex and the original (0,0) vertex returns to the origin. It may also get back to the origin in 359 flips, depending on which side you choose to make the first flip. :) --CiaPan (talk) 14:55, 14 May 2020 (UTC)

...and if you choose the angle at (1,0) as an irrational part of the full turn, you will be unable to bring the (0,0) vertex back to the origin by flipping around (1,0) only. However, you'll get it as close as you wish with appropriate number of flips. --CiaPan (talk) 16:01, 14 May 2020 (UTC)

Each flip should leave one edge invariant. Perhaps I have misunderstood your description of these flips, but I don’t see how they leave an edge invariant.  --Lambiam 17:17, 14 May 2020 (UTC)

Hi, Lambiam. Imagine how flipping an equilateral triangle alternatively by two edges makes the triangle to cover a regular hexagon and finally get back to the initial position. Surely, every flip preserves one edge - but no edge is preserved across two flips (unless you flip back and forth by the same edge, which doesn't seem too productive). --CiaPan (talk) 19:03, 14 May 2020 (UTC)

With a hexagon, you get back to your starting configuration in 6 flips. As RDB observed above, for a pentagon it takes 10 flips; after that you keep repeating the same cycle.  --Lambiam 19:17, 14 May 2020 (UTC)

Just wanted to add a few more results of computations. It makes things easier to move and scale down the pentagon so that its vertices are the five fifth roots of 1: $1,\ \zeta =e^{\frac {2i\pi }{5}},\ \zeta ^{2},\ \zeta ^{3},\ \zeta ^{4}.$. Then the reflection through side $\zeta ^{i-1}\zeta ^{i}$ is given by $R_{i-1,i}(z)=-\zeta ^{2i-1}{\bar {z}}+\zeta ^{i-1}+\zeta ^{i}.$ You get translations with any product of the form $R_{i-1,i}R_{j-1,j}R_{k-i,k}R_{i-j+k-1,i-j+k}$ where the last indices are computed mod 5. You can use this to produce combinations of flips that translate by ${\sqrt {5}},\ \varphi {\sqrt {5}},\ \zeta {\sqrt {5}},\ \zeta \varphi {\sqrt {5}}.$ By combining these you can translation by any vector in a set T where T is dense in R², and therefore the orbit of any point is dense in R². It looks like T is actually √5Z[ζ]; the actual orbits of the vertices would be unions of cosets of this ideal, but I can't be more specific without doing more computation. --RDBury (talk) 22:49, 14 May 2020 (UTC)

PS. I've computed the orbits. The index of T=√5Z[ζ] in Z[ζ] is 25 so there are 25 cosets which are permuted by the action of the reflections. It turns out that the cosets containing a vertex are fixed under this action, so the orbit of a vertex v is simply v+T. This accounts for 5 cosets leaving 20. The orbit of 0 is the union of 10 of these, and the orbits of -v where v if s vertex are all the same and this accounts for the remaining 10 cosets. The case with a square is similar but much easier to visualize. There, T is given by (2+2i)Z[i], in other words you can translate vertically or horizontally by 4 units, diagonally by 2√2 units, or any combination thereof. T has index 8 in Z[i] so you can color the points in Z[i] with 8 colors so that the pattern is preserved under the translations. If you try to keep this pattern under reflections on the sides of the central the square, the vertices a+ib where a+b is odd can be left alone, in other words the orbit of each vertex consists of those vertices having the same color as that vertex. But the remaining four colors, for a+ib where a+b is even, have to be merged into a single color. It might be an interesting experiment to carry this out for other regular n-gons. Higher dimensional polytops are theoretically possible as well, but I think you'd lose most of the algebraic machinery I was applying in the 2-dimensional case. --RDBury (talk) 06:19, 15 May 2020 (UTC)

RDBury When you talk about the square, you are including a diagonal of 2√2 which I don't understand. It doesn't even seem that you could get that by flipping on the diagonal of the square, which will do nothing but flip the vertices. For the regular pentagon are you somehow including flipping along the line that runs between v1 and v3 (non-adjacent vertices) which will move the vertices?Naraht (talk) 09:00, 16 May 2020 (UTC)

Keep in mind that I'm doing my calculations relative to a polygon whose vertices are roots of 1. So I'm starting with the square with vertices 1, i, -1, -i. (That's (1, 0), (0, 1), (-1, 0), (0, -1) in Cartesian coordinates.) So flip once on the edge from 1 to i, then flip the resulting square on the edge from 2+i to 1+2i, and the final result will be a translation by 2+2i which is 2√2 diagonally. There's no reason you couldn't include diagonal flips as well; that would enlarge the group and possibly change the results. I'm not sure how that would affect the pentagon case but to answer you're question I was not including them in my computations. If ζ and η are any two points on the unit circle, then the reflection on the line from ζ to η is given by $R_{\zeta ,\eta }(z)=-\zeta \eta {\bar {z}}+\zeta +\eta ,$ so the machinery I was using above still runs. --RDBury (talk) 16:51, 16 May 2020 (UTC)