1,621 views
4 votes
4 votes

A random permutation π of set[n] = {1, 2, …, n} can be represent by a directed graph on n vertices with directed arc (i, πi) where πi is the ith entry in the permutation. Observe that the resulting graph is just a collection of disjoint cycles.
What is the expected length of the cycle containing vertex 1?

  1.   n(n-1)/2n
  2.   (n+1)/2n
  3.   ((n-1))/2
  4.   ((n+1))/2

/pls explain the question 

2 Answers

Best answer
8 votes
8 votes

​​​​Expected value =  sum of all possible values each multiplied by the probality of its occurence.

In any directed graph , possible length of cycle will be = $1$ , $2$ , $3$ , $4$ .... $(N - 1)$ , $N$    

Because maximum length cycle may have N nodes  , and length will be N.

Now expected value = $1$ * probality(cycle_length = $1$)  + $2$ * probality(cycle_length =$2$) + .... + $N$   * probality(cycle_length = $N$ )

Now probality of cycle length = $1$  will be $\frac{1}{N}$ , because

($1->1 , 2->2 , 3->3 ..... N->N$)   (self loop total $N$ values out of which $(1->1)$ count )  

Now probality of cycle length = $2$ will also be $\frac{1}{N}$

Because ,  total posiible cycle will be = $N * (N-1)$      ( First node may have $N$ choices   , and second may have $N - 1$ choices )

Number of favourable cases will be = $1 * (N-1)$    ( one place is fixed for $1$ and second may have $N - 1$ ) choices

probability of cycle length = 2  = $\frac{1*(N-1)}{N*(N-1)}$  

Similalry for L length cycle =   $\frac{(N-1)*(N-2) *....* (N-L+1)}{N*(N-1)*(N-2) *....* (N-L+1)} = \frac{1}{N}$

Means for any length cycle probality will be $\frac{1}{N}$.

Now expected value =  $1 * \frac{1}{N} + 2 * \frac{1}{N} + 3 * \frac{1}{N}  ..... (N-1)* \frac{1}{N}$ + N * \frac{1}{N}$

                              =   $\frac{1}{N} ( 1 + 2 + 3 + 4 + 5 ....  (N-1) + N ) $

                              =   $\frac{N+1}{2}$

Option 4 is the correct answer.     

edited by
5 votes
5 votes

What is the expected length of the cycle containing vertex 1?

We need to count cycles containing vertex $1$ only.

  • For example $3$ length cycle in the permutation of {$1,2,3,4,5,6$}

  • This approach is generic and we can visualize that no of digraphs such that vertex $1$ in included in a $2$ length cycle will be = $5*4! = 5!$ again.
  • For $k$ , $k>0$ length cycle containing vertex $1$ no of such diagraphs is always = $(n-1)!$ where n is the no of elements as given in the question.
  • Total diagraphs possible = Total permutations = $\large n!$
  • So, we have equal probability of $k$ length cycle diagraphs where $k$ can be $1,2,3,4,5,...n$ and the probability is = $\large \frac{(n-1)!}{n!}$.

$$\begin{align*} &\text{We know :} E = \sum_{k=1}^{n}k.P(k) \\ &\Rightarrow E = P(k).\sum_{k=1}^{n}k \\ &\Rightarrow E = \left [ {\color{red}{\frac{(n-1)!}{n!}}} \right ] . \left [ {\color{blue}{\frac{n(n+1)}{2}}} \right ] \\ &\Rightarrow E = {\large \bf \color{red}{\frac{n+1}{2}}} \end{align*}$$ 

edited by

Related questions

0 votes
0 votes
2 answers
3
anonymous asked Mar 26, 2016
1,002 views
If two teams A and B play a best-of-five series, and if team A has a 1/4 chance of winning any game (and team B has 3/4 chance of winning any game), then what is the expe...
2 votes
2 votes
1 answer
4
Sahil Gupta asked Nov 25, 2014
1,855 views
What is expected value of the sum of the numbers appearing on two fair dice when they are rolled given that the sum of these numbers is at least nine. That is, what is E(...