Wikipedia:Reference desk/Archives/Mathematics/2022 October 8

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 8

Question from a YouTube video

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)

Experimentally, I find values that approximate the sequence

${\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)

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

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

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

The expected value of a sum of random variables equals the sum of their expected values. Let $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 $m=n.$ You stop as soon $m$ reaches zero. The expected number of draws to go from $m=n$ to $m=0$ is the sum of the expected numbers of draws needed to go from $m=k$ to $m=k{-}1,$ for $k=n,n{-}1,...,1.$ The probability of drawing one of the $k$ missing colours among the $n$ possible colours is ${\frac {k}{n}}.$ So on average ${\frac {n}{k}}$ draws are needed to go from $m=k$ to $m=k{-}1.$ Summing this over $k$ yields the formula $d_{n}=nH_{n}.$  --Lambiam 00:24, 9 October 2022 (UTC)

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

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