0

Possible Duplicate:
Throw a die $N$ times, observe results are a monotonic sequence. What is probability that all 6 numbers occur in the sequence?

A $6$-sided die is thrown N times and the results are observed to form a monotonic sequence. What is the probability that every possible number occurs at least once in the sequence?

Community
  • 1
fpghost
  • 259

1 Answers1

2

Hint: Calculate how many monotonic sequences there are that "use" only $k$ numbers.

How many surjective and non-decreasing sequences of length $n$ of elements in $\{1, \ldots, k\}$ are there? If $(a_1, \ldots, a_n)$ is such a sequence, then $a_1=1$, $a_n=k$ and there must be exactly $k-1$ different $i$, $1\le i\le n-1$ with $a_{i+1}=a_i+1$. Thus the number of such sequences is $n-1\choose k-1$.

How many non-decreasing sequences of length $n$ of elements in $\{1, \ldots, 6\}$ with exactly $k$ different numbers are there? We can choose $k$ out of 6 numbers and then have $n-1\choose k-1$ sequences as in the previous paragraph. Hence the number of such sequences is ${6\choose k}\cdot {n-1\choose k-1}$.

The conditional probability of throwing a sequence containing all 6 numbers, given that the sequence is nondecresing is therefore $$p=\frac{n-1\choose 5}{{6\choose 1}{n-1\choose 0}+{6\choose 2}{n-1\choose 1}+{6\choose 3}{n-1\choose 2}+{6\choose 4}{n-1\choose 3}+{6\choose 5}{n-1\choose 4}+{6\choose 6}{n-1\choose 5}} \\ =\frac{\frac{1}{120} n^5 - \frac{1}{8} n^4 + \frac{17}{24} n^3 - \frac{15}{8} n^2 + \frac{137}{60} n - 1 }{ \frac{1}{120} n^5 + \frac{1}{8} n^4 + \frac{17}{24} n^3 + \frac{15}{8} n^2 + \frac{137}{60} n + 1 }\\ =1-30\cdot\frac{n^4 + 15 n^2 + 8 }{n^5 + 15 n^4 + 85 n^3 + 225 n^2 + 274 n + 120 } ,$$ which converges $\to1$ as $n\to\infty$.

Hagen von Eitzen
  • 374,180
  • If N=1,monoseqs is 6, N=2:21, N=3:56, N=4:126..?

    The way I get this is write out a table like:

    N=1: LHC| RHC {1,6},{1,5}{1,4}{1,3}{1,2}{1,1} N=2: LHC| RHC {1,6} {2,5},{3,4}{4,3},{5,2},{6,1} N=3: LHC| RHC {1,6},{3,5},{6,4},{10,3},{15,2},{21,1} then multiply the LHC by RHC and add up. The RHC always runs 6 down 1(if seq ends 1 seeds 6 more if inc N by 1) since and the LHC entry can be obtained from the previous N-1 table by adding up the corresponding entry in the LHC and those in the cells directly above , e.g. for N=3 my third row 6 in the LHC is obtained from the N=2 table by adding 3+2+1.

     – fpghost Sep 20 '12 at 16:58
  • Since some sequences are common to both increasing and decreasing monotonic sequences, shouldn't both be considered ? – true blue anil Sep 21 '12 at 05:17
  • Also, for the final expression, I'm getting the polynomial in the denominator to be identical to that in the numerator except that all the coefficients are positive. – true blue anil Sep 21 '12 at 08:39
  • I've finally understood the answer in the other thread and that answer converges to 1 as n->infty, so not sure why this result does not? – fpghost Sep 21 '12 at 09:36
  • @fpghost: There seems to have been a mistake in the polynomial expansion or me copying the coefficients. After running the binomials through gp again, th eresut is like in th eother (more elegant) thread. – Hagen von Eitzen Sep 24 '12 at 20:08