1
$\begingroup$

Let $S = S_{30}$, the set of permutations on $\{1,...,30\}$.

Suppose $A$ is the event: $\{\pi\in S_{30}: \pi(1) = 1\}$ and $B$ is the event $\{\pi\in S_{30}: \pi(2) < \pi(3)\}$.

I am asked to show that these events are independent.

Now $|A| = 29!$ and $|B| = (1+...+29)\times 28!$

Hence $|A|\times|B| = 29!\times 28! \times (1+...+29)$

However $|A\cap B| = (1+...+28)\times 27!$

So $P(A\cap B)< P(A)\times P(B)$.

So these events don't seem to be independent? What am I doing wrong?

$\endgroup$
  • $\begingroup$ @AdamHughes Thank you, I was thinking of something else. I've written an answer now. $\endgroup$ – DonAntonio Jun 6 '16 at 15:44
1
$\begingroup$

By definition: since $\;A\cong S_{29}\;$ :

$$P(A)=\frac{29!}{30!}=\frac1{30}$$ , whereas

$$B:=\{\pi\in S_n\;/\;\pi(2)<\pi(3)\}$$

and we can then count:

$$\begin{cases}\pi(3)=30\implies\pi(2)=1,2,...,29\\{}{}\\\pi(3)=29\implies\pi(2)=1,2,...,28\\\ldots\\\pi(3)=2\implies \pi(2)=1\end{cases}$$

For each option in each line we have $\;(n-2)!\;$ permutations, so all in all we have

$$28!\left(29+28+\ldots2+1\right)=28!\frac{29\cdot30}2=\frac{30!}2\implies$$

$$P(B)=\frac{\frac{30!}2}{30!}=\frac12$$

Finally: if $\;\pi\in A\cap B\;$ then

$$\begin{cases}\pi(1)=1,\,\pi(2)=2\implies \pi(3)=2,3,....,30\\{}\\\pi(1)=1,\,\pi(2)=3\implies \pi(3)=4,...,30\\\ldots\\{}\\\pi(1)=1,\,\pi(2)=29\implies \pi(3)=30\end{cases}$$

For each option above we have $\;27!\;$ permutations, so in total we have

$$27!\left(1+2+\ldots+28\right)=\frac{29!}2\implies P(A\cap B)=\frac{\frac{29!}2}{30!}=\frac1{60}=P(A)P(B)$$

and the events are independent

$\endgroup$
3
$\begingroup$

I assume that we are picking a permutation $\pi$ at random, with all permutations equally likely.

Let $A$ be the event $\pi(1)=1$ and $B$ the event $\pi(2)\lt \pi(3)$. To show independence, we show that $\Pr(B\mid A)=\Pr(B)$. This is clear, for by symmetry each is $\frac{1}{2}$.

$\endgroup$
  • $\begingroup$ Thanks for this explanation. May I ask where did I go wrong in my argument? $\endgroup$ – fosho Jun 6 '16 at 15:39
  • 1
    $\begingroup$ The calculations seem to be correct, but do not address the issue of independence. $\endgroup$ – André Nicolas Jun 6 '16 at 15:43
  • 1
    $\begingroup$ @McFry: At the time I wrote the comment, the OP made no reference to probability. $\endgroup$ – André Nicolas Jun 6 '16 at 16:02

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.