A bagel store sells six different kinds of bagels. Suppose you choose 15 bagels at random. What is the probability that your choice contains at least one bagel of each kind? If one of the bagels is Sesame, what is the probability that your choice contains at least three Sesame bagels?
My approach to the first problem was the equation $x_1+x_2+x_3+x_4+x_5+x_6=15, x_i \geq 1$ which is the same as $y_1+y_2+y_3+y_4+y_5+y_6=9, y_i \geq 0$ which has $ 14 \choose 9$ solutions. So that is 2002 solutions. And there are in total $22 \choose 15$ solutions to the equation without the restriction. So in a percentage, there is a $\frac{2002}{15504}$ or 12.9% we will get one of each kind.
For the second problem, I used the equation $x_1+x_2+x_3+x_4+x_5+x_6=15, x_1 \geq 3, x_i \geq 0, i \neq 1$. This gives $17 \choose 12$ solutions, which gives a $\frac{6188}{15504}$ or a 39% chance of getting a sesame bagel.
Is my approach for both of these right? (The percentages of these happening seem really high)
Best Answer
A Markovian matrices solution. I like this formalism because it gives more controls on the algorithm and leads to less faulty solutions in general.
To get one of each kind, we define $7$ states, from $0$ to $6$, related to the number of colors found. $k$ is the size of the sample, $k=15$ and $n$ the number of states. We start with $0$ colors. The 1st "throw" gives always a transition to the 1st color. At the next steps , the state stays unchanged or changes with the couple of probabilities $(\frac{s}{n} , \frac{n-s}{n})$. When it comes to $6$, it stays unchanged.
$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 \end {pmatrix} \times {\begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & {\frac{1}{n}} & {\frac{n-1}{n}} & 0 & 0 & 0 & 0 \\ 0 & 0 & {\frac{2}{n}} & {\frac{n-2}{n}} & 0 & 0 & 0 \\ 0 & 0 & 0 & {\frac{3}{n}} & {\frac{n-3}{n}} & 0 & 0 \\ 0 & 0 & 0 & 0 & {\frac{4}{n}} & {\frac{n-4}{n}} & 0 \\ 0 & 0 & 0 & 0 & 0 & {\frac{5}{n}} & {\frac{n-5}{n}} \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end {pmatrix}}^{k} =$ $\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 \end {pmatrix} \times {\begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & {\frac{1}{6}} & {\frac{5}{6}} & 0 & 0 & 0 & 0 \\ 0 & 0 & {\frac{2}{6}} & {\frac{4}{6}} & 0 & 0 & 0 \\ 0 & 0 & 0 & {\frac{3}{6}} & {\frac{3}{6}} & 0 & 0 \\ 0 & 0 & 0 & 0 & {\frac{4}{6}} & {\frac{2}{6}} & 0 \\ 0 & 0 & 0 & 0 & 0 & {\frac{5}{6}} & {\frac{1}{6}} \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end {pmatrix}}^{15} = $
$\begin{pmatrix} 0 & \frac{1}{78364164096} & \frac{27305}{26121388032} & \frac{11875505}{19591041024} & \frac{35296625}{1088391168} & \frac{43909775}{136048896} & \frac{233718485}{362797056} \end{pmatrix} =$
$\begin{pmatrix} 0. & 1.27609×10^{-11} & 1.04531×10^{-6} & 0.00060617 & 0.0324301 & 0.32275 & \color{blue}{0.644213} \end{pmatrix}$
computed here
Similarly to get 3 Sesames, we must build another matrix with 4 states, 0, 1 , 2 or at least 3 sesames. Now the probability of transition is always $\frac16$ and then the probability to stay is the complement to 1. We start with 0 Sesame.
$\begin{pmatrix} 1 & 0 & 0 & 0 \end {pmatrix} \times {\begin{pmatrix} {\frac{n-1}{n}} & {\frac{1}{n}} & 0 & 0 \\ 0 & {\frac{n-1}{n}} & {\frac{1}{n}} & 0 \\ 0 & 0 & {\frac{n-1}{n}} & {\frac{1}{n}} \\ 0 & 0 & 0 & 1 \end {pmatrix}}^{k} = $ $\begin{pmatrix} 1 & 0 & 0 & 0 \end {pmatrix} \times {\begin{pmatrix} {\frac{5}{6}} & {\frac{1}{6}} & 0 & 0 \\ 0 & {\frac{5}{6}} & {\frac{1}{6}} & 0 \\ 0 & 0 & {\frac{5}{6}} & {\frac{1}{6}} \\ 0 & 0 & 0 & 1 \end {pmatrix}}^{15} = $ $\begin{pmatrix}\frac{30517578125}{470184984576} & \frac{30517578125}{156728328192} & \frac{42724609375}{156728328192} & \frac{219940843951}{470184984576} \end{pmatrix} = $ $\begin{pmatrix}0.0649055 & 0.194716 & 0.272603 & \color{blue}{0.467775} \end{pmatrix}$
computed here