Expected Spins of an Unequal Spinner to Land in K Distinct Regions

A spinner has $N$ regions. Each spin lands in region $i$ with probability $p_i$, independently of all other spins, where $p_1 + p_2 + \dots + p_N = 1$. You spin repeatedly. What is the expected number of spins until the spinner has landed in $K$ different regions for the first time? The first spin always lands in a new region, and the spin that produces the $K$-th distinct region counts. The specific values of $N$, $K$ and the probabilities are generated randomly, and each question states the required output format. ```hint Where the easy argument breaks When all regions are equally likely, the wait for each new region has a simple form. Ask what that argument needs to know once the probabilities differ. ``` ### Constraints and Clarifications - $K$ is a positive integer no larger than $N$. - Every $p_i$ is positive, so every region can eventually appear. ### Clarifying Questions - Are the region probabilities all equal, or given individually? - Can a region have probability zero, and if so, is $K$ still reachable? - How large are $N$ and $K$, which decides whether enumerating sets of seen regions is feasible? ### What a Strong Answer Covers - The equal-probability case as a sum of geometric waiting times - Why unequal probabilities make the waiting time depend on which regions have been seen - A correct general method, with its cost in terms of $N$ and $K$ - Sanity checks on small cases, such as $K = 1$ or two regions ### Follow-up Questions - What is the probability that at least $K$ different regions have appeared after $S$ spins? - How would you compute the variance of the number of spins? - How does the computation scale if $N$ is in the hundreds?