Generate 15 random letters , what is the probability we can spell MISSISSIPPI?

Question

Suppose 15 characters are generated one by one, what is the probability we can rearrange the characters to spell MISSISSIPPI?

My answer was

$${15\choose 11}\times{11! \over 4!4!2!1!}\times{26^{-15}}.$$

Just wanted to clarify if this was correct. This is because we have the multinomial coefficient corresponding to the number of ordered sequences associated with the multi-set of MISSISSIPPI and 15C11 different ways of selecting where to place these letters.

Answer 1

I would approach this problem via inclusion-exclusion based on the events:

• $M$: we have strictly fewer than $1$ M selected

• $I$: we have strictly fewer than $4$ I's selected

• $S$: we have strictly fewer than $4$ S's selected

• $P$: we have strictly fewer than $2$ P's selected

The probability of failure then is $Pr(M\cup I\cup S\cup P) = Pr(M)+Pr(I)+Pr(S)+Pr(P)-Pr(M\cap I)-Pr(M\cap S)-Pr(M\cap P)-Pr(I\cap S)-\dots+\dots-Pr(M\cap I\cap S\cap P)$

You should be able to calculate each of $Pr(M),Pr(M\cap I),Pr(M\cap I\cap S),\dots$ and complete the calculations that way, though this will be rather tedious to do as you will have to potentially use case-work on the exact number of I's and S's appearing, etc...

For example, $Pr(M\cap I)$ is the probability no M's and at most $3$ I's were used. Breaking into cases based on the number of I's used we have $Pr(M\cap I) = \binom{15}{0}\left(\frac{24}{26}\right)^{15} + \binom{15}{1}\left(\frac{1}{26}\right)\left(\frac{24}{26}\right)^{14}+\dots+\binom{15}{3}\left(\frac{1}{26}\right)^{3}\left(\frac{24}{26}\right)^{12}$

Doing it like this though, you might be breaking $M\cap I\cap S\cap P$ into $32$ events, which is incredibly tedious.

Answer 2

This was supposed to be a comment but it got too long.

You (at least) also need to count the remaining 4 unknown letters which are allowed to be whatever. $26^4$ without respect to placement.

Then as Tony says also if you among these four unknown get an extra $M$ then switching placement of this random $M$ with a prescribed $M$ counts as two cases but should only count as one.

Maybe it is easier to allow any other letter than $MSPI$, $(26-4)^4=22^4$ for a first estimate and then treat the Tony cases separately.

Answer 3

The probability you want is the probability that your $15$ randomly chosen letters contain at least $4$ Is, at least $4$ Ss, at least $2$ Ps, and at least one M—that is, $$ \sum_\limits{j_1=1}^{5}\sum_\limits{j_2=2}^{7-j_1}\sum_\limits{j_3=4}^{11-j_1-j_2}\,\sum_\limits{j_4=4}^{15-\sum_\limits{i=1}^3 j_i}\frac{22^{15-\sum_\limits{i=1}^4 j_i}}{26^{15}}{15\choose j_1\,j_2\, j_3\, j_4\,(15-\sum_\limits{i=1}^4 j_i)\,}\ . $$