Does anyone know the distributions of those in the general case? We will need them to calculate, for example 'how many time in average do we need to roll a dice to get all six states'?
I've calculated that for cases 2, 3, 4 the probabilities to have all states shown in a 'k' tosses are (so 'k' - integer):
for 2: P(n=k) = 1/2^(k-1), k>1, expected tosses - 3.
for 3: P(n=k) = (2^(k-1)-2)/3^(k-1), k>2, expected tosses - 11/2.
for 4: P(n=k) = (3^(k-1)-3*2^(k-1)+3)/4^(k-1), k>3, expected tosses - 25/3.
P.S. Approximately expectations in those cases are Fibonacci numbers: 3, 5, 8. Interesting to see if it will continue further.
UPDATED: for 5: P(n=k) = 4^(k-1) - 4*3^(k-1)+2*3*2^(k-1)-4, for k>4, expected tosses - 137/12, approx. = 11.5... not fibonacci)) It is so strange to me that series with such members can sum to 1 - look at URL below for example: http://goo.gl/fUaOiM
It is possible to find characteristic function in general case. Later can place formulas here. Expression for expected tosses is:
n * ( 1 + 1/2 + 1/3 + ... + 1/n)
n * ( 1 + 1/2 + 1/3 + ... + 1/n)
But this series diverges, right? Or you missed something?
Tere is finit number of terms in parentheses. Formula reproduces your numbers:
for n = 2: 2*(1 + 1/2) = 3;
for n = 3: 3*(1 + 1/2 + 1/3) = 11/2;
for n = 4: 4*(1 + 1/2 + 1/3 + 1/4) = 25/3.
Thanks, great idea :) How did you notice that? Checked it for 5 and 6 - works!
The problem is exactly solvable. You can find characteristic function (CF). CF helps to find not only expectation but all moments.
See W.Feller "An introduction to Probability Theory and its Application" Vol. 1, 1968,
Chapter IX (Random variables; Expectations), Section 3 (Examples and Applications),
Example (d) Waiting time in sampling
This is called the coupon collector problem and has been extensively studied. I don't know about formulas for finite n, but if T_n is the time to "see" each of n states, then the well-known asymptotic results are:
* E[ T_n ] ~ n log n
* T_n / (n log n) -> 1 in probability
* T_n / n - log n converges in law to the Gumbel extreme value distribution.
The minimum number of tosses for n is 2^n+n-1
The Avergae (for n large enough) is 2^(Euler's gamma +nLn(2))
According to Havil Gamma's book.
- Badges
- Science topic
- Similar topics
- Mathematics
- Statistics
- Probability