Conditional probablity on a derangement problem.

Question

Numbers from $1$ to $10$ are written on top. Their random permutation is written on the bottom. We consider success the case when there is a symbol $i$, under which there is $i$. What is the probability of success if $1$ is not under $1$?

As far as I understand, this is a conditional probability. Number of all permutations $$N = 10!$$ Number of derangements $$B = 10!\times (1 - 1/9! + 1/8!-1/7! + ...)$$ Number of permutations, with one shifted $$ A=9 \times 9!$$ Required probability $$ p = 1 - B/A.$$

Is my work correct?

Answer 1

This is the conditional probability, given the fact $1$ is not under $1$. The total case is $10!-9!=9\cdot 9!$. The probability equals

$$P=\frac{N_s}{9\cdot 9!}$$

Next, let's count the success cases $N_s$

Under the first digit $1$, it must be one of $2,3,\dots , 10$, totally nine subcases, hence by symmetry, $N_s=9N_2$, where $N_2$ is the cases when $2$ is under $1$.

$$\begin{align}&1,~~2,~~3,~~4,~~5,~~6,~~7,~~8,~~9,~~10\\ &2,~~?,~~?,~~?,~~?,~~?,~~~?,~~?,~~?,~~~?\end{align}$$

Let $A_k$ be the case when $k$ is under number $k$,

$$N_2=\#(A_3\cup A_4\cup\dots\cup A_{10})$$

By inclusion-exclusion principle,

$$\begin{align}N_2&=\#\left(\sum_i A_i-\sum_{i<j} A_i\cap A_j+\sum_{i<j<k} A_i\cap A_j\cap A_k\dots\right)\\ \\ &=\binom{8}{1}8!-\binom{8}{2}7!+\binom{8}{3}6!-\dots+\binom{8}{7}2!-\binom{8}{8}1!\end{align}$$

Plug in and we get:

$$P=\frac{1}{9!}\left(\binom{8}{1}8!-\binom{8}{2}7!+\binom{8}{3}6!-\dots+\binom{8}{7}2!-\binom{8}{8}1!\right)$$

Answer 2

First of all some notations. Let $S$ be the symmetric group on the standard set with $n$ elements, specifically $\{1,2,3,\dots,n\}$. It has $n!$ elements. We are interested in the case $n=10$, but notation is simpler when using a general $n$. Denote by $S_k$ the subset of $S$ of all permutations $s$ with a $k$-match, i.e. with $s(k)=k$.

Let $S'_1$ be the complement, the set with a $k$-mismatch.

The winning event for the initial game is $A=S_1\cup S_2\cup\dots\cup S_n$, the event of either a $1$-match, or a $2$-match, ... , or an $n$-match.

But now we restrict to $S'_1$. We need the conditional probability $$ \Bbb P(A|S'_1)=\frac{|A\cap S'_1|}{|S'_1|}\ . $$ The denominator is clear, we have $|S'_1|=|S|-|S_1|=n!-(n-1)!=(n-1)\cdot (n-1)!$ - what about the numerator?

---

First solution (working from the scratch): We have $$ \begin{aligned} A\cap S'_1 &= \underbrace{(S_1\cap S'_1)}_{\emptyset}\cup \underbrace{(S_2\cap S'_1)}_{B_2}\cup \underbrace{(S_3\cap S'_1)}_{B_3}\cup\dots\cup \underbrace{(S_n\cap S'_1)}_{B_n} \\ &=B_2\cup B_3\cup\dots\cup B_n\ . \end{aligned} $$ It is useful to denote by $B_{jk}=B_{\{j,k\}}$ the intersection $B_j\cap B_k$, by $B_{jkl}=B_{\{j,k,l\}}$ the intersection $B_j\cap B_k\cap B_j$, and so on, by $B_J$ the intersection of all $B_j$ for an index $j$ running in the set $J$, a subset of $\{2,3,\dots,n\}$. Then the inclusion-exclusion principle gives the number of elements of the union of the $B_j$-sets in terms of the numbers $|B_J|$. If $J$ has $s$ elements, $1\not\in J$, then $B_J$ collects all permutations with a match at each $j\in J$, so there are other $(n-s)$ symbols to be permuted, constrained to the fact that $1$ is a mismatch, so we count $(n-s)!-(n-s-1)!$ possibilities.

And there are $\binom{n-1}{s}=\frac{(n-1)!}{s!(n-s-1)!}$ possibilities for such a $J$. $$ \begin{aligned} |A\cap S'_1| &=|B_2\cup B_3\cup\dots\cup B_n| \\ &=\sum_{j}|B_j| - \sum_{j<k}|B_{jk}| + \sum_{J\ :\ |J|=3}|B_J| -\dots +(-1)^{n-2}\sum_{J\ :\ |J|=n-1}|B_J| \\ &=\sum_{1\le s\le n-1}(-1)^{s-1}\sum_{J\ :\ |J|=s}|B_J| \\ &=\sum_{1\le s\le n-1}(-1)^{s-1} ((n-s)!-(n-s-1)!) \cdot\frac{(n-1)!}{s!(n-s-1)!} \\ &=(n-1)! \sum_{1\le s\le n-1}(-1)^{s-1} \frac{(n-s)-1}{s!} \\ &=(n-1)! \sum_{1\le s\le n-1}(-1)^{s-1} \left( \frac{n-1}{s!} - \frac{s}{s!} \right) \\ &= (n-1)\cdot (n-1)! \sum_{1\le s\le n-1} \frac{(-1)^{s-1}}{s!} - (n-1)! \sum_{1\le s\le n-1} \frac{(-1)^{s-1}}{(s-1)!} \\ &= (n-1)\cdot (n-1)! \sum_{1\le s\le n-1} \frac{(-1)^{s-1}}{s!} + (n-1)! \sum_{0\le s\le n-2} \frac{(-1)^{s-1}}{s!} \\ &=(n-1)! \left( -\frac 1{0!} +\frac {\bbox[lightblue]{n}}{1!} -\frac {\bbox[lightblue]{n}}{2!} +\frac {\bbox[lightblue]{n}}{3!} -\dots +(-1)^{n-3} \frac {\bbox[lightblue]{n}}{(n-2)!} \right) + \frac {(-1)^{n-2}}{(n-1)!} \ . \end{aligned} $$ The wanted probability is thus in general obtained by dividing the above by $|S_1'|=(n-1)(n-1)!$: $$ \begin{aligned} &\frac 1{n-1} \left( -\frac 1{0!} +\frac {\bbox[lightblue]{n}}{1!} -\frac {\bbox[lightblue]{n}}{2!} +\frac {\bbox[lightblue]{n}}{3!} -\dots +(-1)^{n-3} \frac {\bbox[lightblue]{n}}{(n-2)!} \right) + \frac {(-1)^{n-2}}{(n-1)!} \\ &= 1- \frac {\bbox[lightblue]{n}}{n-1} \left( \frac 1{0!} -\frac 1{1!} +\frac 1{2!} -\frac 1{3!} +\dots + \frac {(-1)^{n-2}}{(n-2)!} + \frac {(-1)^{n-1}}{(n-1)!} \right) - \frac {(-1)^{n-1}}{(n-1)!} \\ &= 1- \frac {\bbox[lightblue]{n}}{n-1} \left( \frac 1{0!} -\frac 1{1!} +\frac 1{2!} -\frac 1{3!} +\dots + \frac {(-1)^{n-2}}{(n-2)!} + \frac {(-1)^{n-1}}{(n-1)!} + \frac {(-1)^n}{n!} \right) \ . \end{aligned} $$

So for the case $n=10$ we have explicitly: $$ 1- \frac {10}9 \left( \color{gray}{ \frac 1{0!} -\frac 1{1!}} +\frac 1{2!} -\frac 1{3!} +\frac 1{4!} -\frac 1{5!} +\frac 1{6!} -\frac 1{7!} +\frac 1{8!} -\frac 1{9!} +\frac 1{10!} \right) \ . $$

---

Second solution: Given the above formula, there must be a simpler solution, when taking the formula for the probability of a derangement for granted: $$ \Bbb P(A') = \color{gray}{ \frac 1{0!} -\frac 1{1!}} +\frac 1{2!} -\frac 1{3!} +\dots +\frac {(-1)^n}{n!}\ . $$ Here, $A'$ is the losing set, the complement of $A=S_1\cup S_2\cup\dots\cup S_n$ in the set of all $n!$ permutations $S$, the set of permutations without a fixed point, the set of derangements.

So there are $$n! \cdot \Bbb P(A') $$ derangements. Of course, this set $A'$ is contained in $S_1'$. So the probability of losing conditioned by the event $S'_1$ (of a mismatch in $1$) is: $$ \begin{aligned} \Bbb P(A'|S'_1) &=\frac{|A'\cap S_1'|}{|S_1'|} =\frac{|A'|}{|S_1'|} =\frac{n!\cdot \Bbb P(A')}{(n-1)\cdot (n-1)!} \\ &=\frac{n\cdot (n-1)!\cdot \Bbb P(A')}{(n-1)\cdot (n-1)!} =\frac{n}{n-1}\cdot \Bbb P(A')\ . \end{aligned} $$ I suppose that this expression was also that fraction $B/A$ from the question, however a closer look at $B$ which starts with $10!\times(1-1/9!+1/8!-1/7!+\dots)$ shows something different. (And the dots are unclear, where do we stop, at $1!$, at $0!$.) But un essence, going this way is a good quick idea.

---

Computer check:

• Pari/gp pedestrian Code:

  {prob(n) =
   local(ind, p, good, all);
   good = 0; all = 0;
   for(ind=1, n!,
       p = numtoperm(n, ind);
       if( p[1] - 1,
           all += 1;
           if( prod(k=1, n, p[k] - k), , good +=1 )));
   good / all;}
  

  Then calling prob(10) we get:

  ? prob(10)
  %34 = 23839/40320
  

• Sage pedestrian code:

  n = 10
  all  = 0    # count of all possible cases
  good = 0    # count of all good / winning cases
  
  for p in Permutations(n):
      if p(1) == 1:    continue
      flag = sum([1 if p(k) == k else 0 for k in [1..n]])
      all += 1
      if flag:    good += 1
  
  print(f'The wanted probability is: {good/all}')
  

  This gives after some time:

  The wanted probability is: 23839/40320
  

  The computed formula leads to the same number:

• Sage:

    sage: 1 - 10/9 * sum([(-1)^s/factorial(s) for s in [0..10]])
    23839/40320
  

• Pari/gp code:

    ? {p(n) = 1 - n/(n-1) * sum(s=0, n, (-1)^s / s!);}
    ? p(10)
    %40 = 23839/40320