October 8 Information

I remember seeing a question from a YouTube video about probability, forgot what it was, but the question was something like this:

"Imagine you have a box containing an infinite amount of marbles, with each marble being one of N different colors. If you keep drawing marbles until you have at least one marble of each color, throwing away all the marbles you drew after this and starting over, how many will you draw on average each time?"

My personal intuition is that it's the Nth triangular number, but I'm not sure how I would go around proving that or if this is even correct. 172.112.210.32 ( talk) 17:56, 8 October 2022 (UTC) reply

Experimentally, I find values that approximate the sequence

${\displaystyle {\frac {1}{0!}},{\frac {3}{1!}},{\frac {11}{2!}},{\frac {50}{3!}},{\frac {274}{4!}},...,}$

in which the numerators are a column in the matrix of unsigned Stirling numbers of the first kind (sequence A000254 in the OEIS).  -- Lambiam 20:58, 8 October 2022 (UTC) reply

Letting ${\displaystyle d_{n}}$ denote the ${\displaystyle n}$th value in that sequence, we have

${\displaystyle d_{n}=nH_{n},}$

in which ${\displaystyle H_{n}}$ is the ${\displaystyle n}$th harmonic number.  -- Lambiam 21:36, 8 October 2022 (UTC) reply

The expected value of a sum of random variables equals the sum of their expected values. Let ${\displaystyle m}$ stand for the number of missing colours in the basket holding the marbles already drawn. Initially the basket is empty, so all colours are missing, which means that ${\displaystyle m=n.}$ You stop as soon ${\displaystyle m}$ reaches zero. The expected number of draws to go from ${\displaystyle m=n}$ to ${\displaystyle m=0}$ is the sum of the expected numbers of draws needed to go from ${\displaystyle m=k}$ to ${\displaystyle m=k{-}1,}$ for ${\displaystyle k=n,n{-}1,...,1.}$ The probability of drawing one of the ${\displaystyle k}$ missing colours among the ${\displaystyle n}$ possible colours is ${\displaystyle {\frac {k}{n}}.}$ So on average ${\displaystyle {\frac {n}{k}}}$ draws are needed to go from ${\displaystyle m=k}$ to ${\displaystyle m=k{-}1.}$ Summing this over ${\displaystyle k}$ yields the formula ${\displaystyle d_{n}=nH_{n}.}$  -- Lambiam 00:24, 9 October 2022 (UTC) reply

This is called the coupon collector's problem. 66.44.22.126 ( talk) 14:52, 9 October 2022 (UTC) reply

I never knew the problem had a name. 172.112.210.32 ( talk) 16:23, 9 October 2022 (UTC) reply