6
$\begingroup$

I performed an experiment in which an individual had to order 5 items (i.e. his "response" was something like $(3,2,1,4,5)$ or some other permutation). The correct ordering was $(1,2,3,4,5)$ and I want to know the probability of getting 1, 2, 3 or 5 of the numbers right by chance alone.

I know that the probability of getting all right by chance alone is $1/5!$, and I think that probability of getting 3 right is:

$ \frac{5 \choose 2}{5!} $

Because if you get 3 right you are just "swapping" two items from $(1,2,3,4,5)$. I am having difficulty to deduce the rest of the probabilities. I have written an R code that simulates the process, so I have an approximate answer. I just wanted to know how to do it by hand.

Thank you in advance!

  • 1
    I'm sorry, I don't follow. I don't think it would be correct to "generalize" in that way. The probability of getting 2 or 3 right would be the same because ${5 \choose 2} = {5 \choose 3}$, and I think that is not correct.2012-05-10

2 Answers 2

4

You calculated the probability of getting exactly $3$ right correctly, and of course the probability of getting all $5$ right. The probability of getting exactly $4$ right is clearly $0$. So we need only deal with the probabilities of $2$ right, $1$ right, and $0$ right.

A small comment about the number of permutations that have exactly $3$ right. Your analysis was good. I would, however, prefer to count as follows. There are $\binom{5}{3}$ ways to pick which three will be right. For each of these ways, we need to swap the other two, so the number is $\binom{5}{3}$. You chose instead the two items that would be swapped. Same count.

For exactly $2$ right, let us count the permutations that have exactly $2$ right. Which $2$ are right can be chosen is $\binom{5}{2}$ ways. For any such choice, that leaves three entries, say $a$, $b$, and $c$, that should be all wrong. Thus $a$ should be in one of positions $b$ or $c$. If $a$ is in position $b$, then $b$ must be in position $c$ (it cannot be in position $a$, for then $c$ would be forced into position $c$, which would make more than $2$ right). It follows that there are $\binom{5}{2}(2)$ permutations in which exactly $2$ are right.

For exactly $1$ right, the one that is right can be chosen in $\binom{5}{1}$ ways. That leaves $4$ items, which should all be in the wrong position. Where does $a$ go? There are $3$ possibilities, $b$, $c$, and $d$. The situation is symmetrical in $b$, $c$, and $d$, so we count the permutations that take $a$ to $b$, and multiply the result by $3$.

So suppose $a$ goes to position $b$. Maybe $b$ goes to $a$, in which case $c$ and $d$ must also get interchanged. This gives $1$ permutation. Or maybe $b$ goes to $c$ or $d$. We count the permutations that take $b$ to $c$, and multiply by $2$. So $a$ goes to $b$, and $b$ goes to $c$. Then $c$ must go to $d$, and $d$ must go to $a$. We conclude that there are $1+2$ allowed permutations such that $a$ goes to $b$. The total is therefore $\binom{5}{1}(3)(3)$.

For exactly $0$ right, we can use the same idea. However, it is easier to subtract the sum of the answers for $5$, $4$, $3$, $2$, and $1$ from $5!$.

Remark: We did crude counting, with essentially no theory. For numbers bigger than $5$, this could become very difficult. There is general theory that gives an answer. For details, look for example at the discussion of derangements in Wikipedia.

For any $m$, let $D_m$ be the number of derangements of a set $S_m$ of $m$ elements, that is, permutations of $S_m$ that leave no element fixed. (Wikipedia uses the notation $!m$ for $D_m$.) There are explicit expressions, and also nice recurrences, for $D_m$. The number of permutations of a set of $n$ elements that leave exactly $k$ elements fixed is then $\binom{n}{k}D_{n-k}$.

  • 0
    @JayD.: Oh, I forgot that reputation is required for upvoting! You'll probably have enough before long, anyway.2012-05-10
1

I just wanted to make the simple observation that since you are only looking at permuting a sequence of 5, the total number of permutations is 5!=120 which is small enough for complete enumeration. I am sure that most of you being mathematicians find doing this by brute force distasteful. But it does work as long as you systematically enumerate all 120. You can then inspect each one to see how many numbers are in their right place and then sum all cases with 1 and divide it by 120 to get the probability of one match. Do the same for 2,3 and 5. Aside from the obvious logic that if you match 4 the last one can only be in its right place you can also see this by noting that no case had exactly 4 matching their positions. I did not notice that this was mentioned in the answer above. I did the full enumeration and got 46/120 for 0 46/120 for 1 20/120 for 2 7/120 for 3 0/120 for 4 and 1/120 for 5.

  • 0
    Okay. It was not necessary but thanks.2012-05-13