I'm working on a problem where I need to find the expected number of throws required for each face of a six-sided die to appear at least twice. I've conceptualized the problem using a triplet $(a, b, c)$ to represent the state of the system:
- $a$: numbers drawn twice,
- $b$: numbers drawn once,
- $c$: numbers not drawn,
with the initial state being $(0, 0, 6)$. The transitions are:
- From $c$ to $b$ with probability $\frac{c}{6}$,
- From $b$ to $a$ with probability $\frac{b}{6}$.
And then you can use brute force and write an algorithm to solve it using DP. But I’m wondering if there is any clever method. I know a lot of theorems have been studied on coupon collections issues. But this is a particular simple example so I’m curious about some simpler but clever strategy free of those existing theories that are intended for a more general scenario.