# Possible Probability and Irreducibility of Balanced Nontransitive Dice

Authors: Injo Hur; Yeansu Kim
Journal: Journal of Mathematics
 (2021)

---

## Abstract

We construct irreducible balanced nontransitive sets ofn-sided dice for any positive integer n. One main tool of the construction is to study so-called fair sets of dice. Furthermore, we also study the distribution of the probabilities of balanced nontransitive sets of dice. For a lower bound, we show that the winning probability can be arbitrarily close to 1/2. We hypothesize that the winning probability cannot be more than 1/2+1/9, and we construct a balanced nontransitive set of dice whose probability is 1/2+13−153/24≈1/2+1/9.12.


---

## Body

## 1. Introduction

A nontransitive triple of dice consists of three dice, labeledA,B, and C, with the property that all three probabilities that A rolls higher than B, that B rolls higher than C, and that C rolls higher than A are greater than 1/2. We write this as PA>B>1/2,PB>C>1/2, and PC>A>1/2. It is called nontransitive because if we define the relation X≻Y as PX>Y>1/2 for X,Y∈A,B,C, then the relation ≻ is not transitive. For example, the following set of 6-sided dice is nontransitive since PA>B=PB>C=PC>A=19/36:Note that nontransitive sets of dice are first introduced by Gardner [1], further studied in [2, 3], and have been generalized in several directions (see [4–14]). In [14], Schaefer and Schweig constructed balanced nontransitive sets of n-sided dice for any positive integer n≥3 (see below for the definition of “balanced” and other terms). Main idea of the construction in [14] is to combine several balanced nontransitive sets of dice. Therefore, the sets of dice that are constructed in [14] are reducible, and Schaefer and Schweig [14] question whether there exist balanced irreducible nontransitive sets of n-sided dice for all n. One main purpose of the paper is to construct irreducible nontransitive sets of n-sided dice for any positive integer n. Our main idea of the construction is to use so-called fair sets of 2-sided dice. Here, being fair means that probabilities PA>B,PB>C, and PC>A are all 1/2. Although we used 2-sided dice to construct new sets of dice, understanding fair sets of n-sided dice for any positive integer n seems to be an important step to understand all irreducible balanced nontransitive dice. We also study fair sets of n-sided dice for any positive integer n.The second purpose of the paper is to study possible probabilities of balanced nontransitive sets ofn-sided dice, i.e., possible value of PA>B. As far as we know, previous known constructions of balanced nontransitive sets of dice have probability 1/2<PA>B<3/5=1/2+1/10. We first show that there exist balanced nontransitive sets of dice such that PA>B−1/2>0 is arbitrarily small, i.e., 1/2 is a sharp lower bound for balanced nontransitive set of dice. We conjecture that, in general, 1/2<PA>B<1/2+1/9. To support the conjecture, we first explicitly calculate and prove that both the probability PA>B in our paper and the one in [14] are less than 1/2+1/9. We also provide another new construction of a balanced nontransitive set of dice such that PA>B≈1/2+1/9.12, which is less than 1/2+1/9, and is, as far as we know, the maximum among known constructions of balanced nontransitive sets of dice.Let us now describe the content of our paper. After we introduce notation and preliminaries in Section2, we study fair sets of dice in Section 3. In Section 4, we provide construction of irreducible balanced sets of n-sided dice for any positive integer n using fair sets of 2-sided dice. In Section 5, we calculate and study possible probability PA>B for balanced nontransitive sets of dice.


## 2. Notation and Preliminaries

We briefly recall definitions and notations in [14] that we are going to use.Definition 1.
Fix an integern>0. A set of n-sided dice is a collection of three pairwise-disjoint sets A,B, and C with A=B=C=n and A∪B∪C=1,…,3n. We think of dice A,B, and C as being labeled with the elements of A,B, and C, respectively, and we assume that each die is fair (i.e., the probability of rolling any one of its numbers is 1/n).Definition 2.
A set of dice is called as follows:(i)
Balanced ifPA>B=PB>C=PC>A(ii)
Nontransitive if each ofPA>B,PB>C, and PC>A exceeds 1/2(iii)
Fair ifPA>B=PB>C=PC>A=1/2Definition 3.
IfD=A,B,C is a set of n-sided dice, define a word σD by the following rule: the ith letter of σD corresponds to the die on which the number i labels a side.For a wordσ, the number of letters in the word, which we call the length of σ, is denoted by σ. A number of A (resp. B, C) in σ is denoted by Aσ (resp. Bσ, Cσ). For example, if σ corresponds to a set of n-sided dice, Aσ=Bσ=Cσ=n.LetD=A,B,C be a set of n-sided dice and σ be its corresponding word (Definition 3). Then, we denote by PDA>B or PσA>B the probability that the number rolled on A is greater than the number rolled on B when we roll A and B. Similarly, we define PDB>C,PσB>C,PDC>A, and PσC>A.Definition 4.
For a set ofn-sided dice D (and its corresponding word σ with length 3n), we let NDA>B≔n2PDA>B,NDB>C≔n2PDB>C and NDC>A≔n2PDC>A. Similarly, we also define NσA>B, NσB>C, and NσC>A.It is by definition thatD=A,B,C is balanced if NDA>B=NDB>C=NDC>A, and D=A,B,C is nontransitive if NDA>B,NDB>C,NDC>A>n2/2.Remark 1.
NDA>B in Definition 4 represents the number of consequences that a die A beats a die B when we consider all possible outcomes when we roll A and B. Note that NDA>B is the same as the notation ∑si=AqσD+si in [14].Example 1.
LetD be the following set of 3-sided dice:(1)A=951,B=843,C=762.
Then,σD=ACBBACCBA and PA>B=PB>C=PC>A=5/9. Therefore, this set of dice is balanced and nontransitive.Definition 5.
The concatenation of two wordsσ and τ is simply the word σ followed by τ, denoted by στ.We recall a recursive relation ofNA>B,NB>C, and NC>A. The following is in the proof of Lemma 2.4 in [14].Lemma 1.
(see (1) in [14]). Let σ and τ be two words that correspond to two sets of dice, respectively. Let σ=3m and τ=3n (i.e., corresponding dice are m-sided and n-sided, respectively). Then, we have(2)NστA>B=NσA>B+NτA>B+mn.


## 3. Fair Sets of Dice

In the following two lemmas “probabilities” meanPA>B, PB>C, and PC>A and x, y, or z is one of A, B, or C.Lemma 2.
Assume thatσD has xy and yx, i.e., σD=⋯xy⋯yx⋯. Then, exchanging the orders of xy and yx at the same time, i.e., σD˜=⋯yx⋯xy⋯ does not change the “probabilities.”Lemma 3.
Assume thatσD is a word having three different letters, say x, y, and z. Then, xyzσD and σDxyz have the same “probabilities” if and only if σD has the same numbers of x, y, and z.Definition 6.
Two words are called similar,σD1∼σD2, if σD1 can be rewritten to σD2 by exchanging the orders as allowed by virtue of Lemmas 2 and 3.Note that, ifσD1∼σD2, then two words have the same length and PD1A>B=PD2A>B,PD1B>C=PD2B>C, and PD1C>A=PD2C>A.Example 2.
Lemmas2 and 3 indicate that ⋯xy⋯yx⋯∼⋯yx⋯xy⋯ and xyzσD∼σDxyz if and only if xσD=yσD=zσD.Conjecture 1.
(fair dice). IfD is fair, then the length of D is a multiple of 6 and it is similar to an iterated concatenation of xyzzyx.Note thatτ≔ABCCBA is a fair set of 2-sided dice, which will be used in Section 4.Example 3.
LetσD be AABBCCCCBBAA. It is fair and(3)AABBCCCCBBAA∼ABABCCCCBABA∼ABACBCCBCABA∼ABCABCCBACBA∼ABCCBAABCCBA=ABCCBA2.To support Conjecture1, let us consider only two-die case, i.e., a fair word with only two letters A and B. In this case, a set of dice and a corresponding word are called fair if PA>B=PB>A=1/2.Theorem 1.
Assume that a given fair wordσf has 4m letters with A=B=2m. Then, σf∼ABBAm.Proof.
We may assume thatσf starts with A (if not, we exchange the notations of A and B). Then, let us claim that the factor ABBA can be extracted to the front without changing probabilities, i.e., σf∼ABBAωf, where ωf is a fair word having 4m−1 letters with A=B=2m−1. Mathematical induction with this fact leads us to the result that σf∼ABBAm.
Observe first thatσf∼ABω0, where ω0 is a word such that ABω0 is fair. If σf=ABω0, then we are done. Suppose not, i.e., σf=A⋯ABω1. We would like to see that ω1 contains a subword BA. If ω1 would not have BA, then the given fair dice should be expressed by σf=A⋯ABA⋯AB⋯B, which is not fair at all. Due to having BA in ω1, exchanging AB and BA together will hold probabilities, i.e., σf∼A⋯BAω2, where ω2 is the word obtained from ω1 by replacing BA by AB. A similar argument works to reveal that ω2 has BA and therefore σf∼A⋯BAAω3. Keep doing this procedure until σf∼ABω0.
Next see thatσf∼ABBAωf as claimed. If ω0 starts with BA, then we are done. If not, there are three cases, that is, ω0 is one of ABω4, A⋯ABω5, B⋯BAω6. Since a similar argument can be applied, let us consider the first case when ω0=ABω4. If ω4 would not have BA, then it should be expressed by A⋯AB⋯B. This means that σf∼ABABA⋯AB⋯B, which is impossible to be fair. So, ω4 contains a subword BA. Exchanging BA (in ω4) for AB (in front of ω4) shows that σf∼ABBAωf. As mentioned, in the other two cases, a similar argument reveals that σf∼ABBAωf as claimed.


## 4. Irreducible Sets of Dice

In this section, we construct irreducible balanced nontransitive sets ofn-sided dice for any positive integer n. Note that this answers Question 5.2 in [14].Definition 7.
A balanced nontransitive word (and a corresponding set of dice) is called irreducible if there do not exist balanced nontransitive wordsσ1 and σ2 (both nonempty) such that σ=σ1σ2.Lemma 4.
Letσ be a balanced nontransitive word and τ=ABCCBA. Then, τσ is balanced and nontransitive.Proof.
τ is balanced but not nontransitive since PA>B=PB>C=PC>A=1/2. Lemma 2.4 in [14] implies that τσ is balanced. It remains to prove that it is nontransitive. Let σ=3n. Equation (2) implies(4)NτσA>B=2+NσA>B+2n>2+n22+2n=n+222.
Similarly, we haveNτσB>C,NτσC>A>n+22/2. Therefore, τσ is also nontransitive (Definition 4).Lemma 5.
Letσ be an irreducible balanced nontransitive word that corresponds to a set of either 3-sided or 4-sided dice and τ=ABCCBA. Then, τkσ is an irreducible balanced nontransitive word.Proof.
Applying Lemma4k times, we conclude that τkσ is balanced and nontransitive. It remains to prove that it is irreducible. Suppose that τkσ is reducible. Then, we can write τkσ as ππ′ where π is an irreducible balanced nontransitive word and π′ is a balanced nontransitive word. Since τn is fair (so not nontransitive) and τnABC is not balanced for any nonnegative integer n, π should be of the form τkπ″ (π″ is not empty). We write τkσ as τkπ″π‴. Since π‴<12, π‴ is irreducible. This implies that σ=π″π‴ corresponds to a balanced nontransitive set of 4-sided dice and it contains a balanced nontransitive word π‴ of length less than 12, which contradicts that σ is irreducible.We are now ready to construct an irreducible balanced nontransitive set ofn-sided dice.Theorem 2.
For anyn≥3, there exists an irreducible balanced nontransitive set of n-sided dice.Proof.
We first consider the following two sets of dice:(5)A3=951,B3=843,C3=762,A4=10754,B4=12932,C4=11861.
BothD3=A3,B3,C3 and D4=A4,B4,C4 are irreducible, balanced, and nontransitive. As before, we consider τ=ABCCBA. We now construct an irreducible balanced nontransitive set of n-sided dice for any n≥3. We already constructed such a set of dice when n=3 and n=4. When n≥5 is odd, we write n=3+2k,k≥1. Then, τkσD3 is an irreducible balanced nontransitive set of n-sided dice due to Lemma 5. When n≥5 is even, we write n=4+2k,k≥1. Then, τkσD4 is an irreducible balanced nontransitive set of n-sided dice due to Lemma 5.


## 5. Possible Probability

LetA,B,C be a balanced nontransitive set of n-sided dice with PA>B=PB>C=PC>A>1/2. In this section, our interest is in a possible probability PA>B. Let us state what is on our mind.Conjecture 2.
IfA,B,C is a balanced nontransitive set of n-sided dice such that PA>B>1/2, then(6)12<PA>B<12+19.


### 5.1. Probabilities of Our Construction in Theorem2

To support Conjecture2, we first calculate all possible probabilities of the set of dice which are constructed in Section 4.Lemma 6.
Letσ (resp. τ) be a word of length 3m (resp. 3n) that corresponds to a set of dice. Then,(7)PστA>B=12+NσA>B−m2/2+NτA>B−n2/2m+n2.
Similarly, we have(8)PστB>C=12+NσB>C−m2/2+NτB>C−n2/2m+n2,PστC>A=12+NσC>A−m2/2+NτC>A−n2/2m+n2.Proof.
It is an easy consequence of equation (2) since NστA>B=m+n2PστA>B.Remark 2.
Note thatNσA>B represents the number of consequences that a die A beats a die B. Therefore, NσA>B−m2/2 in Lemma 5.2 represents how far σ is from being fair. For example, if NσA>B−m2/2=0, then PσA>B=1/2.Lemma 7.
Letσ and τ be as in Lemma 6. Assume that 1/2<PσA>B<a and 1/2<PτA>B<b. Then, 1/2<PστA>B<maxa,b.Proof.
Equation (2) with NστA>B=m+n2PστA>B,NσA>B=m2PσA>B and NτA>B=n2PτA>B implies(9)m+n2PστA>B=m2PσA>B+n2PτA>B+mn<maxa,bm2+n2+1maxa,bmn<maxa,bm+n2,since 1/2<maxa,b.We are now ready to calculate the probabilityPA>B. Let σ be a word that is constructed in Theorem 2. Then, σ is either τkτ1 or τkτ2 for some nonnegative integers k, where(10)Dτ1=951843762,Dτ2=107541293211861,Dτ=615243.Note thatτk is a fair word (i.e., PτkA>B=1/2). For i=1,2, Lemma 2.1 implies that(11)2k+ni2PσA>B=2k2PτkA>B+ni2PτiA>B+2kni=2k22+ni2+22+2kni=ni+2k2+22,which is the closest integer greater than ni+2k2/2. Here, 3ni is the length of τi and, therefore, ni=i+2.Therefore, Conjecture2 is true in this case.Remark 3.
Similarly, we can also calculate possible probabilities of the set of dice that is constructed in [14]. Let σ be a word that is constructed in Theorem 2.1 of [14]. Then, σ is a product of several τ1,τ2, and τ3, where(12)Dτ1=951843762,Dτ2=121031987211654,Dτ3=151174314109521312861.
PτiA>B=ni2+2/2/ni2 for i=1,2,3, where ni=i+2. Therefore, Lemma 7 implies that PσA>B≤5/9=1/2+1/18. Therefore, Conjecture 2 is true in this case.


### 5.2. Best Bound for Probability

We first show that1/2 is the greatest lower bound of PA>B, which means that the inequality PA>B>1/2 is optimal.Theorem 3.
There exists a balanced nontransitive set of dice such thatPA>B−1/2>0 becomes arbitrary small.Proof.
Letn=2m+1m∈ℕ. Then, we construct a word σ (or a corresponding set of dice) as follows. First, consider the word ABCCBAmBAC which is not balanced, since the number of the events for C to beat A or B is one more than the ones of the events for A or B to beat C (therefore, C always beats both A and B at least in probability). To change this word to a balanced one, let us replace BC by CB on the first factor ABCCBA. In all, the word σ obtained by(13)σ≔ACBCBAABCCBAm−1BACis balanced. A direct computation of PA>B on σ, or more precisely,(14)NσDA>B=0+2+2+4+⋯+2m−1+2m+2m+1=2m2+2m+1shows that(15)PA>B=2m2+2m+12m+12=12+0.5n2,which goes to 1/2 as n⟶∞. This indicates that 1/2 is the greatest lower bound of PA>B and the inequality PA>B>1/2 could not get better.For the upper bound ofPA>B, recall that Conjecture 2 states that(16)PA>B<12+19.To support this inequality, we provide three new constructions of sets of dice of which probability is close to1/2+1/9. For simplicity, assume that n=6p (later, we discuss when n=6p+2 or n=6p+4 which is similar to the present case). Let us start with the most unmixed fair n-sided dice σf,(17)σf≔A⋯AB⋯BC⋯CC⋯CB⋯BA⋯A,where “⋯” means that all the letters are the same as the boundary letters and the numbers of letters in “⋯” are the same, i.e., A⋯A=B⋯B=C⋯C=3p.We apply the following algorithm to construct the largest probabilityPA>B.Algorithm 1.
Step 1: if there is no tripleAB,BC,CA in a word, then replace xy and yx in a word for x,y∈A,B,C so that the resulting word contains AB,BC,CA.Step 2: if you findAB,BC,CA, then replace AB,BC,CA by BA,CB,AC, respectively.Remark 4.
Replacement in Step 1 does not change the probability due to Lemma2.Replacement in Step 2 increases the number of events forA (resp. B or C) to beat B (resp. C or A) by 1. In particular, doing this replacement keeps the words balanced and nontransitive. Therefore we may expect that keeping replacing in this way would lead the largest probability of PA>B.Since there is noCA in σf, we first apply Step 1 (exchange of BC and CB) several times to σf in order to obtain a word σ1 which is still fair but having sequels CA by(18)σ1≔A⋯AA⋯AA⋯AB⋯BB⋯BC⋯CC⋯CC⋯CB⋯BC⋯CC⋯CB⋯BB⋯BB⋯BC⋯CA⋯AA⋯AA⋯A,(i.e., the last one-third of the first B⋯B in (17) moves to the middle and the last one-third of the second C⋯C in (17) does to the front of the second A⋯A (the moved ones are in bold). Here, A⋯A=B⋯B=C⋯C=p in (18). Therefore, the numbers of replacing BC and CB by CB and BC, respectively, are the same as 3p2.)We now apply Step 23p2 times to obtain a balanced nontransitive word σ2 by(19)σ2≔B⋯BA⋯AA⋯AA⋯AC⋯CC⋯CC⋯CB⋯BB⋯BC⋯CC⋯CB⋯BB⋯BB⋯BA⋯AA⋯AA⋯AC⋯C,(i.e., in (18), the first B⋯B moves in front, the second B⋯B does to almost middle, and the last C⋯C does to the end. The moved ones are in bold as before). Here, the probability PA>B of σ2 increases to 1/2+3p2/6p2=7/12.Since there is noAB and CA in σ2, we apply Step 1 6p times as follows; we move B and C in σ2 to the ones in σ3 (all of which are in bold) in order to produce the products AB and CA.(20)σ2≔B⋯BA⋯AA⋯AA⋯AC⋯CC⋯CC⋯CB⋯BB⋯BC⋯CC⋯CB⋯BB⋯BB⋯BA⋯AA⋯AA⋯AC⋯C,σ3≔B⋯BA⋯AA⋯AA⋯ABC⋯CC⋯CC⋯CB˙⋯B¨B¨⋯B¨C¨⋯C¨C¨⋯C˙B⋯BB⋯BB⋯BCA⋯AA⋯AA⋯AC⋯CB˙andC˙have been moved toBandC,respectively.This means that we need to exchangeBC to CB in the middle part (which is blue and has two dots above the character on σ3) 6p times (3p to move B and another 3p to beat C). Then, to increase PA>B, one more exchange from BC to CB in the middle part is necessary.In addition to this observation, we would like to measure how many times we can apply Step 2 toσ3 in terms of p (this is because the denominator of PA>B is 6p2, so we would better express in p in order to examine asymptotic behavior of PA>B). Put by m the number of further replacement such that m-many B’s move between B⋯B and A⋯A in front. For this, we need extra 3pm-many exchanges of BC and CB in the middle part. Since the remaining of each B’s or C’s in the middle is 2p−m, the possible exchange of BC to CB is 2p−m2, which should be at least 9pm=3pm+3pm+3pm (the last 3pm is due to move m-many B’s in the further replacement). As a summary, we have that(21)2p−m2p−m≥9pmm≤2p⟹m≤13−1542p.Therefore, the largest probability onPA>B in the argument above is(22)12+3p2+13−154/2p⋅3p6p2=12+15−15424≈12+19.25<12+19.Note that the maximumm (in ℕ) means that, since all BC are exhausted in the last word, the probability PA>B is not able to be larger in this construction.The cases whenn=6p+2 and n=6p+4 can be investigated by a similar procedure. By applying Step 1 (or exchanging BC by CB) and Step 2 (or replacing AB, BC, and CB by BA, CB, and BC), the probability PA>B increases by(23)p3p+123p+12,whenn=6p+2orp3p+223p+22,whenn=6p+4,(which is similar to the increase p3p/6p2 when n=6p). In these cases, after doing this procedure, new words are expressed by(24)n=6p+2:σ2=B⋯BA⋯AA⋯AA⋯AABC⋯CC⋯CC⋯CCB⋯BB⋯BC⋯CC⋯CC⋯BB⋯BB⋯BBA⋯AA⋯AA⋯AAC⋯C,n=6p+4:σ2′=B⋯BA⋯AA⋯AA⋯AAABBC⋯CC⋯CC⋯CCCB⋯BB⋯BC⋯CC⋯CCC⋯BB⋯BB⋯BBBA⋯AA⋯AA⋯AAAC⋯C.Here, each⋯ has exactly p−2 letters. For example, A⋯A=p−2+2=p.Next, to make the largestPA>B, we do Step 2 further as in the previous case. Shortly speaking, when n=6p+2, we have that(25)2p−m2p+1−m−3p+1≥3m3p+1m≤2p⇔m2−13p+4m+4p2−p−1≥0⇒m≤13p+4−153p2+108p+202.Hence, the increased probability onPA>B in the argument (i.e., except 1/2) is(26)p+13p+4−153p2+108p+20/23p+16p+22⟶p⟶∞112+13−15324<19.12<19.Note that, since the numerator13p+4−153p2+108p+20 is increasing in p, the last inequality holds for all p.Similarly, whenn=6p+4, we have that(27)2p−m2p+2−m−23p+2≥3m3p+2m≤2p⇔m2−13p+8m+4p2−2p−4≥0⇒m≤13p+8−153p2+216p+802.Hence, the increased probability onPA>B for n=6p+4 (again except 1/2) is(28)p+13p+8−153p2+216p+80/23p+26p+42⟶p⟶∞112+13−15324<19.12<19.Note again that the numerator13p+8−153p2+216p+80 increases in p.Let us summarize the argument above. Start with the most unmixed fair wordσf (which is (17)). By replacing AB, BC, CA by BA, CB, AC, i.e., (Step 2) as much as possible, the probability PA>B=PB>C=PC>A increases most. Then, the computation above tells us that(29)PA>B<12+19,which upholds Conjecture 2.Remark 5.
(i)
Let us tell why we think the last constructed word in this argument provides the largest probability onPA>B. First, observe that we have considered the only case when n was even (when n=6p, 6p+2, or 6p+4). We, however, believe that this would be enough due to the following observation. A direct computation shows that there is only one possible probability PA>B when n=3, or equivalently, any three balanced, nontransitive dice with 3 sides can be expressed by a balanced, nontransitive word which is similar to σ3=CBABACACB. In this case, Pσ3A>B=5/9. Then, add CBA at the end of σ3 and then exchange CA (in σ3) to AC. Then, the constructed word σ4 is σ4=CBABAACCBCBA, which becomes balanced and nontransitive. For this, Pσ4A>B=9/16, which is greater than Pσ3A>B=5/9. A similar computation can be done for more general n. Therefore, with this trick (however, we do not know if we can do this trick at all times), the probability of PA>B would get greater for even n’s than odd ones.(ii)
Second, proving that the abovementioned probability is the largest probability related to construction of all balanced nontransitive sets of dice and it also seems to be related to property of fair sets of dice, i.e., Conjecture1, and we leave this for future work.Remark 6.
In [13], Schaefer further generalized the results in [14] to sets of n-sided m dice for any positive integer m. It will be very interesting to generalize our results to sets of m dice for m≥4 and we also leave this for future work.


## 5.1. Probabilities of Our Construction in Theorem2

To support Conjecture2, we first calculate all possible probabilities of the set of dice which are constructed in Section 4.Lemma 6.
Letσ (resp. τ) be a word of length 3m (resp. 3n) that corresponds to a set of dice. Then,(7)PστA>B=12+NσA>B−m2/2+NτA>B−n2/2m+n2.
Similarly, we have(8)PστB>C=12+NσB>C−m2/2+NτB>C−n2/2m+n2,PστC>A=12+NσC>A−m2/2+NτC>A−n2/2m+n2.Proof.
It is an easy consequence of equation (2) since NστA>B=m+n2PστA>B.Remark 2.
Note thatNσA>B represents the number of consequences that a die A beats a die B. Therefore, NσA>B−m2/2 in Lemma 5.2 represents how far σ is from being fair. For example, if NσA>B−m2/2=0, then PσA>B=1/2.Lemma 7.
Letσ and τ be as in Lemma 6. Assume that 1/2<PσA>B<a and 1/2<PτA>B<b. Then, 1/2<PστA>B<maxa,b.Proof.
Equation (2) with NστA>B=m+n2PστA>B,NσA>B=m2PσA>B and NτA>B=n2PτA>B implies(9)m+n2PστA>B=m2PσA>B+n2PτA>B+mn<maxa,bm2+n2+1maxa,bmn<maxa,bm+n2,since 1/2<maxa,b.We are now ready to calculate the probabilityPA>B. Let σ be a word that is constructed in Theorem 2. Then, σ is either τkτ1 or τkτ2 for some nonnegative integers k, where(10)Dτ1=951843762,Dτ2=107541293211861,Dτ=615243.Note thatτk is a fair word (i.e., PτkA>B=1/2). For i=1,2, Lemma 2.1 implies that(11)2k+ni2PσA>B=2k2PτkA>B+ni2PτiA>B+2kni=2k22+ni2+22+2kni=ni+2k2+22,which is the closest integer greater than ni+2k2/2. Here, 3ni is the length of τi and, therefore, ni=i+2.Therefore, Conjecture2 is true in this case.Remark 3.
Similarly, we can also calculate possible probabilities of the set of dice that is constructed in [14]. Let σ be a word that is constructed in Theorem 2.1 of [14]. Then, σ is a product of several τ1,τ2, and τ3, where(12)Dτ1=951843762,Dτ2=121031987211654,Dτ3=151174314109521312861.
PτiA>B=ni2+2/2/ni2 for i=1,2,3, where ni=i+2. Therefore, Lemma 7 implies that PσA>B≤5/9=1/2+1/18. Therefore, Conjecture 2 is true in this case.


## 5.2. Best Bound for Probability

We first show that1/2 is the greatest lower bound of PA>B, which means that the inequality PA>B>1/2 is optimal.Theorem 3.
There exists a balanced nontransitive set of dice such thatPA>B−1/2>0 becomes arbitrary small.Proof.
Letn=2m+1m∈ℕ. Then, we construct a word σ (or a corresponding set of dice) as follows. First, consider the word ABCCBAmBAC which is not balanced, since the number of the events for C to beat A or B is one more than the ones of the events for A or B to beat C (therefore, C always beats both A and B at least in probability). To change this word to a balanced one, let us replace BC by CB on the first factor ABCCBA. In all, the word σ obtained by(13)σ≔ACBCBAABCCBAm−1BACis balanced. A direct computation of PA>B on σ, or more precisely,(14)NσDA>B=0+2+2+4+⋯+2m−1+2m+2m+1=2m2+2m+1shows that(15)PA>B=2m2+2m+12m+12=12+0.5n2,which goes to 1/2 as n⟶∞. This indicates that 1/2 is the greatest lower bound of PA>B and the inequality PA>B>1/2 could not get better.For the upper bound ofPA>B, recall that Conjecture 2 states that(16)PA>B<12+19.To support this inequality, we provide three new constructions of sets of dice of which probability is close to1/2+1/9. For simplicity, assume that n=6p (later, we discuss when n=6p+2 or n=6p+4 which is similar to the present case). Let us start with the most unmixed fair n-sided dice σf,(17)σf≔A⋯AB⋯BC⋯CC⋯CB⋯BA⋯A,where “⋯” means that all the letters are the same as the boundary letters and the numbers of letters in “⋯” are the same, i.e., A⋯A=B⋯B=C⋯C=3p.We apply the following algorithm to construct the largest probabilityPA>B.Algorithm 1.
Step 1: if there is no tripleAB,BC,CA in a word, then replace xy and yx in a word for x,y∈A,B,C so that the resulting word contains AB,BC,CA.Step 2: if you findAB,BC,CA, then replace AB,BC,CA by BA,CB,AC, respectively.Remark 4.
Replacement in Step 1 does not change the probability due to Lemma2.Replacement in Step 2 increases the number of events forA (resp. B or C) to beat B (resp. C or A) by 1. In particular, doing this replacement keeps the words balanced and nontransitive. Therefore we may expect that keeping replacing in this way would lead the largest probability of PA>B.Since there is noCA in σf, we first apply Step 1 (exchange of BC and CB) several times to σf in order to obtain a word σ1 which is still fair but having sequels CA by(18)σ1≔A⋯AA⋯AA⋯AB⋯BB⋯BC⋯CC⋯CC⋯CB⋯BC⋯CC⋯CB⋯BB⋯BB⋯BC⋯CA⋯AA⋯AA⋯A,(i.e., the last one-third of the first B⋯B in (17) moves to the middle and the last one-third of the second C⋯C in (17) does to the front of the second A⋯A (the moved ones are in bold). Here, A⋯A=B⋯B=C⋯C=p in (18). Therefore, the numbers of replacing BC and CB by CB and BC, respectively, are the same as 3p2.)We now apply Step 23p2 times to obtain a balanced nontransitive word σ2 by(19)σ2≔B⋯BA⋯AA⋯AA⋯AC⋯CC⋯CC⋯CB⋯BB⋯BC⋯CC⋯CB⋯BB⋯BB⋯BA⋯AA⋯AA⋯AC⋯C,(i.e., in (18), the first B⋯B moves in front, the second B⋯B does to almost middle, and the last C⋯C does to the end. The moved ones are in bold as before). Here, the probability PA>B of σ2 increases to 1/2+3p2/6p2=7/12.Since there is noAB and CA in σ2, we apply Step 1 6p times as follows; we move B and C in σ2 to the ones in σ3 (all of which are in bold) in order to produce the products AB and CA.(20)σ2≔B⋯BA⋯AA⋯AA⋯AC⋯CC⋯CC⋯CB⋯BB⋯BC⋯CC⋯CB⋯BB⋯BB⋯BA⋯AA⋯AA⋯AC⋯C,σ3≔B⋯BA⋯AA⋯AA⋯ABC⋯CC⋯CC⋯CB˙⋯B¨B¨⋯B¨C¨⋯C¨C¨⋯C˙B⋯BB⋯BB⋯BCA⋯AA⋯AA⋯AC⋯CB˙andC˙have been moved toBandC,respectively.This means that we need to exchangeBC to CB in the middle part (which is blue and has two dots above the character on σ3) 6p times (3p to move B and another 3p to beat C). Then, to increase PA>B, one more exchange from BC to CB in the middle part is necessary.In addition to this observation, we would like to measure how many times we can apply Step 2 toσ3 in terms of p (this is because the denominator of PA>B is 6p2, so we would better express in p in order to examine asymptotic behavior of PA>B). Put by m the number of further replacement such that m-many B’s move between B⋯B and A⋯A in front. For this, we need extra 3pm-many exchanges of BC and CB in the middle part. Since the remaining of each B’s or C’s in the middle is 2p−m, the possible exchange of BC to CB is 2p−m2, which should be at least 9pm=3pm+3pm+3pm (the last 3pm is due to move m-many B’s in the further replacement). As a summary, we have that(21)2p−m2p−m≥9pmm≤2p⟹m≤13−1542p.Therefore, the largest probability onPA>B in the argument above is(22)12+3p2+13−154/2p⋅3p6p2=12+15−15424≈12+19.25<12+19.Note that the maximumm (in ℕ) means that, since all BC are exhausted in the last word, the probability PA>B is not able to be larger in this construction.The cases whenn=6p+2 and n=6p+4 can be investigated by a similar procedure. By applying Step 1 (or exchanging BC by CB) and Step 2 (or replacing AB, BC, and CB by BA, CB, and BC), the probability PA>B increases by(23)p3p+123p+12,whenn=6p+2orp3p+223p+22,whenn=6p+4,(which is similar to the increase p3p/6p2 when n=6p). In these cases, after doing this procedure, new words are expressed by(24)n=6p+2:σ2=B⋯BA⋯AA⋯AA⋯AABC⋯CC⋯CC⋯CCB⋯BB⋯BC⋯CC⋯CC⋯BB⋯BB⋯BBA⋯AA⋯AA⋯AAC⋯C,n=6p+4:σ2′=B⋯BA⋯AA⋯AA⋯AAABBC⋯CC⋯CC⋯CCCB⋯BB⋯BC⋯CC⋯CCC⋯BB⋯BB⋯BBBA⋯AA⋯AA⋯AAAC⋯C.Here, each⋯ has exactly p−2 letters. For example, A⋯A=p−2+2=p.Next, to make the largestPA>B, we do Step 2 further as in the previous case. Shortly speaking, when n=6p+2, we have that(25)2p−m2p+1−m−3p+1≥3m3p+1m≤2p⇔m2−13p+4m+4p2−p−1≥0⇒m≤13p+4−153p2+108p+202.Hence, the increased probability onPA>B in the argument (i.e., except 1/2) is(26)p+13p+4−153p2+108p+20/23p+16p+22⟶p⟶∞112+13−15324<19.12<19.Note that, since the numerator13p+4−153p2+108p+20 is increasing in p, the last inequality holds for all p.Similarly, whenn=6p+4, we have that(27)2p−m2p+2−m−23p+2≥3m3p+2m≤2p⇔m2−13p+8m+4p2−2p−4≥0⇒m≤13p+8−153p2+216p+802.Hence, the increased probability onPA>B for n=6p+4 (again except 1/2) is(28)p+13p+8−153p2+216p+80/23p+26p+42⟶p⟶∞112+13−15324<19.12<19.Note again that the numerator13p+8−153p2+216p+80 increases in p.Let us summarize the argument above. Start with the most unmixed fair wordσf (which is (17)). By replacing AB, BC, CA by BA, CB, AC, i.e., (Step 2) as much as possible, the probability PA>B=PB>C=PC>A increases most. Then, the computation above tells us that(29)PA>B<12+19,which upholds Conjecture 2.Remark 5.
(i)
Let us tell why we think the last constructed word in this argument provides the largest probability onPA>B. First, observe that we have considered the only case when n was even (when n=6p, 6p+2, or 6p+4). We, however, believe that this would be enough due to the following observation. A direct computation shows that there is only one possible probability PA>B when n=3, or equivalently, any three balanced, nontransitive dice with 3 sides can be expressed by a balanced, nontransitive word which is similar to σ3=CBABACACB. In this case, Pσ3A>B=5/9. Then, add CBA at the end of σ3 and then exchange CA (in σ3) to AC. Then, the constructed word σ4 is σ4=CBABAACCBCBA, which becomes balanced and nontransitive. For this, Pσ4A>B=9/16, which is greater than Pσ3A>B=5/9. A similar computation can be done for more general n. Therefore, with this trick (however, we do not know if we can do this trick at all times), the probability of PA>B would get greater for even n’s than odd ones.(ii)
Second, proving that the abovementioned probability is the largest probability related to construction of all balanced nontransitive sets of dice and it also seems to be related to property of fair sets of dice, i.e., Conjecture1, and we leave this for future work.Remark 6.
In [13], Schaefer further generalized the results in [14] to sets of n-sided m dice for any positive integer m. It will be very interesting to generalize our results to sets of m dice for m≥4 and we also leave this for future work.



---

*Source: 6648248-2021-01-29.xml*