[해외DS]는 해외 유수의 데이터 사이언스 전문지들에서 전하는 업계 전문가들의 의견을 담았습니다. 저희 데이터 사이언스 경영 연구소 (MDSA R&D)에서 영어 원문 공개 조건으로 콘텐츠 제휴가 진행 중입니다.

---

워런 버핏은 빌 게이츠에게 특이한 주사위 게임을 제안한 적이 있다. 버핏은 테이블 위에 주사위 4개를 놓고 규칙을 설명했다. 각자 주사위를 하나씩 골라 여러 번 굴려서 더 높은 숫자가 많이 나온 사람이 승리하는 룰이었다. 주사위는 보통의  주사위처럼 번호가 매겨져 있지 않았는데 1부터 6까지의 숫자는 주사위마다 다른 숫자로 대체되어 있었다. 버핏은 예의상 게이츠에게 먼저 주사위를 뽑으라고 권유했다. 그러자 게이츠는 직접 주사위를 검사한 후 버핏의 선의를 한사코 거절했다.

일반적으로 게임에서 선공권을 가지면 유리한 고지를 점할 수 있는데, 왜 이 거물들은 두 번째를 선택하기 위해 경쟁을 벌였을까? 그 답은 버핏 주사위의 독특한 속성에 있다. 이를 이해하기 위해 버핏이 사용한 주사위와 같은 속성을 가지고 있지만 분석하기 더 쉬운 유사한 주사위의 예를 살펴보자.

주사위 A가 주사위 B보다 높은 숫자가 나오는 빈도는 얼마나 될까? 각 주사위에는 세 개의 숫자만 있으므로 1/3의 확률로 주사위 A가 9를 굴려서 B의 숫자와 관계없이 승리한다. 그리고 다른 1/3의 확률로 A는 1을 굴려서 B의 주사위 숫자와 상관없이 패배한다. 나머지 1/3의 경우, A는 5를 굴려 3분의 2(3 또는 4가 나온 B 주사위)의 확률로 B를 이긴다. 이러한 관찰 결과를 확률 규칙으로 합산하면 A가 B를 이길 확률은 (⅓ x 1) + (⅓ x 0) + (⅓ x ⅔) = 5/9, 즉 약 56%에 달한다. 비슷한 계산을 하면 B가 C를 이기는 승률도 동일하게 나온다. 즉, B도 약 56%의 확률로 C를 이깁니다. 따라서 A가 보통 B를 이기고 B가 보통 C를 이긴다면, A가 보통 C를 이겨야 하는 것이 맞을까? 틀렸다! 실제로 C도 약 56%의 확률로 A를 이길 것이다.

이러한 불규칙한 큐브를 비추이적 주사위(intrasitive dice)라고 부른다. 인생에서 마주치는 많은 관계는 정반대의 추이적 속성을 반영한다: 영희가 철수보다 나이가 많고 철수가 민지보다 나이가 많다면 영희는 민지보다 나이가 많다는 결론을 얻는다. "보다 나이가 많다"의 정의가 추이적 관계를 따르기 때문에 이는 유효한 추론이다. 하지만 비추이적 주사위는 사람의 직관을 놀라게 한다. 평균적으로 주사위 B보다 높은 숫자가 나오기 위해 주사위 A가 항상 더 높은 숫자가 나올 필요가 없다는 점을 유의해야 한다. 결정적으로 A가 B를 이기는 경우와 A가 C에 지는 경우가 겹치기 때문에 비추이적 관계가 형성됐다.

이제 모두가 워런 버핏이 여유와 매너의 비밀을 알아챘다. 어떤 비추이적 주사위 세트를 사용하든 버핏의 게임에서는 두 번째 플레이어가 항상 상성이 유리한 주사위를 선택할 수 있기 때문이다. 많은 사람이 가위바위보를 통해 비추이적 게임을 처음 접하게 된다. 순환적인 승리 구조는 어떤 선택이 다른 선택보다 우위에 있지 않도록 보장한다. 버핏의 주사위 게임은 가위바위보에서 상대방이 다음에 무엇을 던질지 미리 말하도록 속이는 것, 즉 실수를 유도당하면 게임에서 패배하는 것과 비슷하다.

스탠퍼드 통계학자 브래들리 에프론(Bradley Efron)은 50여 년 전에 비추이적 주사위를 발명했다. 에프론이 고안한 4개의 주사위 세트에서 각 주사위가 다른 주사위를 이길 확률은 무려 3분의 2(약 67%)에 달한다. 마틴 가드너(Martin Gardner)는 사이언티픽 아메리칸의 전설적인 '수학 게임(Mathematical Games)' 칼럼에서 에프론의 주사위를 대중화했지만, 그 이후로 수학자들은 여러 가지 기발한 변형을 고안해 냈다. 이제 주사위의 개수(2개 이상)에 상관없이 비추이적 관계를 나타낼 수 있다는 것을 알고 있다. 예를 들어 26개의 주사위 세트가 존재하는데, 이 주사위 세트는 일반적으로 A가 B를 이기고, B가 C를 이기고, C가 D를 이기는 식으로 계속 순환하여 끝에 있 주사위 Z에 도달했을 땐 역으로 순환하여 A를 이길 수 있다는 것을 의미한다.

비추이적 주사위는 꼭 6개의 면을 가질 필요가 없다. 사실 모든 면의 개수(2개 이상)에 대한 비추이적 주사위 트리오가 존재한다. 심지어 네덜란드의 퍼즐 제작자 오스카 반 데벤터(Oskar van Deventer)는 버핏의 게임에서 세 명의 플레이어가 사용할 수 있는 일곱 개의 6면 주사위 게임을 발명하기도 했다. 즉, 버핏과 게이츠가 돌리 파튼(Dolly Parton)을 초대해 함께 주사위 놀이를 하면 게이츠와 파튼은 각각 7개의 주사위 중에서 하나를 고를 수 있고, 버핏은 나머지 5개의 주사위에서 항상 두 사람이 선택한 주사위를 모두 이길 수 있는 주사위를 고를 수 있는 게임이다.

주사위 놀이의 독특한 동작에 대해 어느 정도 이해했다고 생각했다면, 아래의 기발한 변형 구조를 보고 다시 한번 경외감을 느끼게 될 것이다.

위 그림으로부터 A가 B를 7/12(약 58%) 확률로 이기고, B가 C를 7/12 확률로 이기고, C가 A를 25/36(약 69%) 확률로 이긴다는 계산을 할 수 있다. 지금까지는 보지 못했던 결과다. 이들은 같은 확률로 서로를 이기지 않지만 여전히 비추이적이다. 두 개의 같은 주사위를 한 쌍으로 간주하고 각각 한 쌍에서 나온 숫자를 합산하여 비교하는 게임에선 어떻게 전개될까? 즉 두 개의 주사위 A가 두 개의 주사위 B를 능가하는 합이 나올 확률은 얼마일까? 한 쌍의 주사위가 같으므로 이전과 같은 결과가 나올까, 아니면 같은 주사위를 던지면 A가 B보다 유리한 점이 증폭될까? 놀랍게도 반전된 결과를 얻을 것이다. A 주사위 한 쌍은 보통 B 주사위 한 쌍에게 패배한다! 또한 전체 순환구조가 반전되어 한 쌍의 B 주사위가 한 쌍의 C 주사위에 패배하고 한 쌍의 C 주사위가 한 쌍의 A 주사위에 패배한다. 이 주사위 세트로 가족과 게임을 한다면 분명히 추방당할 것이다.

한 쌍의 같은 주사위 숫자 합이 승률을 어떻게 바꿨는지를 이해하려면 양면 주사위인 X와 Y의 간단한 예시를 먼저 이해하면 된다. X의 양쪽 면은 모두 1이고 Y의 면은 0과 3이라고 하자. 이 주사위의 승률은 같다. Y는 절반의 경우(3이 나올 때)는 이기고 다른 절반의 경우(0이 나올 때)는 진다. 그러나 주사위를 복제하면 Y 쌍이 X 쌍보다 강해진다. X 쌍의 합은 항상 2인데 Y 쌍의 합은 총 세 가지(0, 3, 6) 경우가 있으며 0이 나올 때만 패배(4분의 1의 확률)한다. 이 양면 주사위의 예시로 위 그림의 반전을 비슷한 현상으로 설명할 수 있다.

비추이적 관계 주사위의 존재 여부는 분명하지 않다. 그 이유가 희귀하기 때문일까? 주사위 세 개를 던졌을 때 A가 보통 B를 이기고 B가 보통 C를 이긴다는 것만 알고 있다면, A가 보통 C를 이길 가능성이 더 높을까 아니면 그 반대의 경우일까? 똑똑한 사람들이 위에서 설명한 모든 주사위를 정의했지만, 무작위로 주사위 번호를 선택했어도 비추이적 관계를 찾아낼 수 있었을까?

영국의 수학자 티모시 가우어스(Timothy Gowers)는 이 질문에 대한 답을 찾기 시작했다. 가우어스는 혁신적이고 비교적 새로운 수학 연구 패러다임인 폴리매스 프로젝트를 이끌고 있다. 폴리매스 프로젝트는 한두 대학의 수학자 몇 명이 한 문제를 파고드는 일반적인 수학 연구 모델 대신 크라우드소싱 접근 방식을 취한다. 온라인 포럼 토론을 통해 많은 기여자가 증명을 위해 얼마든지 협력할 수 있는 환경이다. 가우어스는 비추이적 주사위 문제가 크라우드 작업에 적합하다고 판단하여 2017년에 자신의 블로그에 해당 질문을 등록했다. 토론의 장이 칠판에서 워드프레스 댓글 섹션으로 바뀌자 수십 명의 사람들이 이 문제에 몰두하여 문제를 풀어냈다.

세 개의 서로 다른 주사위에 무작위로 숫자를 할당하고 그 주사위가 비추이적 관계를 나타낼 확률을 알고자 할 때, 주사위에 '무작위로 숫자를 할당'한다는 것이 정확히 무엇을 의미하느냐에 따라 결과가 달라질 수 있다. 폴리매스 팀은 이를 두 가지 자연스러운 기준으로 모델링했다. 일반적인 6면 주사위가 1에서 6 사이 숫자만 있는 것처럼, 무작위 n면 주사위에는 1에서 n 사이의 숫자만 들어 있다고 가정한다(일부 숫자는 반복될 수도 있고 일부는 전혀 나타나지 않을 수도 있다). 6면 주사위의 숫자는 1 + 2 + 3 + 4 + 5 + 6으로 합산된다. 주사위의 균형을 유지하기 위해(예를 들어 어떤 주사위에도 같은 숫자로만 구성되거나 큰 숫자만 포함되지 않아야 함), 폴리매스 팀은 n면 주사위의 경우 각 면의 합이 1부터 n까지의 숫자의 합과 같아야 한다고 조건을 두었다.

추이적 주사위와 비추이적 주사위 중 어느 쪽이 더 일반적인지 맞혀보고 싶은가? 폴리매스 프로젝트 참가자들은 세 개의 무작위 n면 주사위가 약 절반 정도는 비추이적 관계를 가질 것이라는 것을 증명했다. 즉, A가 보통 B를 이기고 B가 보통 C를 이긴다는 것을 알더라도 A가 보통 C를 이길지 아니면 그 반대일지에 대한 정보는 거의 얻을 수 없다는 뜻이다(확률이 동전 던지기와 같기 때문에). 예상이 뒤집히는 것에 지친 일부 의심스러운 독자들은 비추이적 주사위가 추이적 주사위보다 더 일반적일 것이라고 예측할 수 있다. 하지만 이 미끄러운 주사위는 매번 예측을 회피한다. 세 개 주사위의 경우 추이적 주사위와 비추이적 주사위는 같은 확률을 갖는다.

---

Warren Buffett once challenged Bill Gates to an unusual game of dice. Buffett placed four dice on the table and explained the rules. They would each pick a die, roll it a bunch of times, and whoever rolled a higher number more often would win. These weren’t numbered like standard dice. The typical one through six were replaced with other numbers that varied from die to die. As a supposed courtesy, Buffett invited Gates to pick his die first. This aroused suspicion, compelling Gates to inspect the dice for himself and then insist that Buffett choose first.

Typically, choosing first in games confers an advantage, so why were these moguls dueling for second pick? The answer lies in a peculiar property of Buffett’s dice. To appreciate it, let’s inspect an example of similar dice that have the same property as those used by Buffett but that are easier to analyze.

How often will die A roll higher than die B? Because there are just three distinct numbers on each die, one third of the time, die A will roll a 9, which wins regardless of B’s roll. One third of the time, A will roll a 1, which loses regardless of B’s roll. And the remaining third of the time, A will roll a 5, which wins on two thirds of B’s rolls (the ones that turn up 3 or 4). Aggregating these observations with the rules of probability, we get that A beats B (⅓ x 1) + (⅓ x 0) + (⅓ x ⅔) = 5/9, or about 56 percent of the time. A similar calculation yields an identical win percentage for B over C. That is, B also beats C about 56 percent of the time. So if A usually beats B and B usually beats C, then surely A should usually beat C, right? Wrong! C actually beats A about 56 percent of the time as well.

We call these delinquent cubes intransitive dice. Many relations encountered in life exhibit the opposite, transitive property: If Alicia is older than Bruno and Bruno is older than Cassandra, then Alicia is older than Cassandra. That’s a valid deduction because the relation “is older than” obeys the transitive property. Intransitive dice surprise our intuitions because the relation “typically rolls higher than” is not transitive, even though it seems like it should be. Note that to roll higher than die B on average, die A doesn’t need to always roll higher. And critically, there is overlap between cases in which A beats B and A loses to C. This interleaving of the numbers on the faces enables the intransitivity.

With any set of intransitive dice, whoever chooses first in Buffett’s game bears a disadvantage, because the second player can always pick the die that’s likely to defeat their opponent’s choice. Many people first encounter intransitive games through rock paper scissors. Its cyclic winning structure ensures that no choice uniquely outranks any other. Buffett’s dice game is akin to tricking your opponent into announcing what they intend to throw next in rock paper scissors—a mistake that would cost them the game.

Stanford statistician Bradley Efron invented intransitive dice over 50 years ago. Each die in Efron’s set of four beats another an impressive two thirds (about 67 percent) of the time. Martin Gardner popularized Efron’s dice in his legendary “Mathematical Games” column at Scientific American, but mathheads have devised many clever variants since then. We now know that any number of dice (greater than two) can exhibit an intransitive cycle, meaning, for example, there exists a set of 26 dice in which die A usually beats die B, which usually beats C, which usually beats D, and so on all the way through to die Z, which, despite residing at the end of a long chain of dominating dice, pulls an upset by cycling back and usually beating A.

Intransitive dice need not contain six sides. In fact, intransitive trios of dice with any number of sides (greater than two) exist. Dutch puzzle maker Oskar van Deventer even invented a set of seven six-sided dice that allow for three players in Buffett’s game. In other words, if Buffett and Gates invited Dolly Parton to play dice with them, then Gates and Parton could each take their pick from the seven, and Buffett would still always have a die in the remaining five that usually beats both of their choices.

Just when you think you’ve wrapped your head around the peculiar behavior of intransitive dice, the brilliant construction below will roll you right back to dumbstruck awe.

One can calculate that A beats B 7/12 (about 58 percent) of the time; B beats C 7/12 of the time; and C beats A 25/36 (about 69 percent) of the time. So far, nothing we haven’t seen before. These don’t beat each other with identical probabilities, but they’re still intransitive. Often dice come in pairs. When you imagine rolling dice, you probably picture two identical dice in your hand and summing the numbers that turn up on each. What happens if we roll pairs of dice from the figure above? What is the probability that two copies of die A roll a sum that beats two copies of die B? Is it the same as before since the copies are identical, or does duplicating the dice amplify the advantage that A has over B? In a stunning twist, the effect reverses. The pair of A dice usually lose to the pair of B dice! What’s more, the whole cycle reverses: a pair of B dice usually lose to a pair of C dice and a pair of C dice usually lose to a pair of A dice. Procuring a set of these dice is a reliable way to get banned from family game night.

To get a feel for how duplicating dice could reverse their relative strength, imagine the simple case of two two-sided dice, X and Y. Both of X’s faces have a 1 on them, while Y’s faces are 0 and 3. These dice have equal strength. Y wins half of the time (when it rolls a 3) and loses half of the time (when it rolls a 0). When we duplicate the dice however, the Y pair becomes stronger than the X pair. The X pair always rolls a total of 2. The Y pair only loses if both of them turn up 0, which only happens one quarter of the time. A similar phenomenon explains the reversal in the figure above.

It’s not obvious that intransitive dice should exist at all. But is that because they’re rare? If all you know about a trio of dice is that A usually beats B, and B usually beats C, is it more likely that A usually beats C or vice versa? Clever people have carefully constructed by hand all of the dice discussed above, but could they have just chosen dice numberings at random and had a decent shot at finding an intransitive set?

British mathematician Timothy Gowers set out to answer this question. Gowers leads the Polymath Project, an innovative and relatively new paradigm for mathematical research. Instead of a few mathematicians at one or two universities chipping away at a problem—the typical research model in math —the Polymath Project takes a crowdsourcing approach. Any number of contributors can collaborate on a proof via online forum discussion. Gowers deemed the intransitive dice question ripe for a group effort and proposed it on his blog in 2017. Replacing a chalkboard with a WordPress comments section, dozens of minds swarmed the problem and cracked it.

If you randomly assign numbers to three different dice and then want to know the chances that they exhibit intransitivity, it may depend on what exactly you mean by “randomly assign numbers” to the dice. The polymath team modeled this with two natural criteria. Just as a typical six-sided die only contains digits between 1 and 6, a random n-sided die will only contain digits between 1 and n (though some may repeat, and some may not occur at all). Also, the numbers on a typical six-sided die add up to 1 + 2 + 3 + 4 + 5 + 6. To keep the dice balanced (e.g., no die should contain all ones or exclusively massive digits), the polymath team required this of n-sided dice: the sum of their sides should equal the sum of the numbers from 1 to n.

Do you want to guess whether transitive or intransitive dice are more common? Polymath Project participants proved that three random n-sided dice will be intransitive about half of the time. In other words, knowing that A usually beats B, and B usually beats C, gives you almost no information about whether A will usually beat C or vice versa. I would have guessed that transitive dice were more common than intransitive ones. I could imagine some suspicious readers, tired of having their expectations subverted, predicting that intransitive dice are more common than transitive ones. But these slippery dice insist on evading prediction. For three dice, transitive and intransitive dice are equally common.