0
$\begingroup$

I'm trying to figure out the probability of achieving every possible permutation in a set for x number of random re-arrangements.

For example, for a set of 3 objects that get randomly re-arranged in their order each turn and there are x turns how can I figure out the probability that every permutation will come up?

Please note that the set member order matters - hence why I'm thinking about permutations.

$\endgroup$
  • $\begingroup$ this is just a version of the Coupon Collector's Problem. You are looking for $n!$ coupons and making uniform draws with replacement from the list. $\endgroup$ – lulu Sep 8 '16 at 17:25
  • $\begingroup$ Thanks for the reference @lulu. Unfortunately, that page is quite intimidating. What's the probability of seeing all permutations of 3 objects over 20 random re-arrangements? $\endgroup$ – user5508297 Sep 8 '16 at 17:40
  • 1
    $\begingroup$ Maybe this article is better reading. The expected number of draws to see $6$ coupons is $14.7$, so $20$ should have a high probability. People usually refer to expected value in this context, because getting the exact probabilities for a specific number of draws is very messy (generally done with a computer). $\endgroup$ – lulu Sep 8 '16 at 17:54
0
$\begingroup$

Most direct approach is by Inclusion-Exclusion. That is, we start with $1$, then subtract the probability of missing at any given permutation, then add back the probability of missing any given pair, subtract the probability of missing any given triple, and so on. That is to say that your answer, $P$, is given by $$P=1-\sum_{i=1}^5(-1)^{i+1}\binom 6i \left(\frac {6-i}6\right)^{20}\sim 0.847987541$$

As a quick sanity check: the probability of missing a given permutation is, of course $\left( \frac 56\right)^{20}$. If you neglect the chance of missing two or more permutations then your answer would be $$1- 6\times \left( \frac 56\right)^{20}\sim 0.84349568$$ which is pretty much our value.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.