Exercise 1.40

Question

There are n balls in a jar, labeled with the numbers 1, 2, . . . , n. A total of k balls are
drawn, one by one with replacement, to obtain a sequence of numbers.
ewline
(a) What is the probability that the sequence obtained is strictly increasing?
ewline
(b) What is the probability that the sequence obtained is increasing (but not necessarily
strictly increasing, i.e., there can be repetitions)?

fifthist x · Accepted Answer

\begin{enumerate}[label=(\alph*)]
\item Counting strictly increasing sequences of $k$ numbers amounts to counting 
the number of ways to select $k$ elements out of the $n$, since for any such 
selection, there is exactly one increasing ordering. Thus, the answer is 
$$\frac{\binom{n}{k}}{n^k}$$

\item The problem can be thought of sampling with replacement where order 
doesn't matter, since there is only one non decreasing ordering of a given 
sequence of $k$ numbers. Thus, the answer is
$$\frac{\binom{n-1+k}{k}}{n^k}$$

\end{enumerate}

Exercise 1.40

Answers

Comments

Exercise 1.40

Answers

Comments

Add answer