It’s Elementary, My Dear Riddler!

Roll four four-sided dice. Split them into unique values and duplicates; reroll the duplicates and re-sort all four; repeat. You win if all four ever become unique, and lose if all four ever become duplicates (no value appearing just once). What is your probability of winning?

Solution

After each reroll the four dice show some pattern. Two are absorbing: all four distinct (win) and “all duplicates,” meaning every value is repeated, which is either two pairs or four-of-a-kind (lose). The live patterns are one pair plus two singles, and one triple plus a single; from each you reroll the repeated dice and re-sort everything, which can send you to any pattern, including back to a live one. So this is an absorbing Markov chain with cycles, and the win probability is found by solving its balance equations rather than by unrolling.

Setting up one equation per live state (each state’s win chance is the average over its reroll outcomes) and solving the linear system, the answer comes out exactly $$\Pr(\text{win}) = \boxed{\tfrac{9}{20} = 0.45}.$$

The computation

Enumerate the distinct four-dice multisets, mark the absorbing ones, and for the rest build the equation that its win probability equals the average over rerolling its duplicate dice; solve the linear system exactly.

from itertools import product
from collections import Counter
import sympy as sp
states = sorted({tuple(sorted(r)) for r in product(range(1, 5), repeat=4)})
kind = lambda s: ('win' if all(v == 1 for v in Counter(s).values())
                  else 'lose' if all(v > 1 for v in Counter(s).values())
                  else 'live')
live = [s for s in states if kind(s) == 'live']
idx = {s: i for i, s in enumerate(live)}
A, b = sp.zeros(len(live)), sp.zeros(len(live), 1)
for s in live:
    i = idx[s]; A[i, i] += 1
    c = Counter(s)
    fixed = tuple(k for k, v in c.items() if v == 1)
    nd = sum(v for v in c.values() if v > 1)
    for rr in product(range(1, 5), repeat=nd):
        new = tuple(sorted(fixed + rr)); w = sp.Rational(1, 4**nd)
        if kind(new) == 'win': b[i] += w
        elif kind(new) == 'live': A[i, idx[new]] -= w
    # 'lose' contributes 0
W = A.solve(b)
total = sum((1 if kind(tuple(sorted(r))) == 'win' else
             0 if kind(tuple(sorted(r))) == 'lose' else
             W[idx[tuple(sorted(r))]]) for r in product(range(1, 5), repeat=4))
print(total / 4**4)                            # 9/20