Expectation of 2^(Cycle Length)
Source: Mailed to me by Sudeep Kamath (EECS PhD Student, UC Berkeley, EE IITB 2008 Alumnus), Taken from Anand Sarwate (Postdoc at UC San Diego, PhD from UC Berkeley)
Problem:
Hint:
1) There is no high funda group theory/number theory involved. I could solve this in 15 minutes \m/ \m/
2) After you are done, you might want to read this (*Spoiler Alert*)
Solution:
Hint posted by Nikhil Garg (CSE, IIT Delhi third year undergraduate student) in comments! Solution posted by Kalyan in comments! Kalyan's comment explained in detail by me in comments! A simpler solution posted by Gaurav Sinha (chera) (CSE IITK 1996 Alumnus, Indian Revenue Service) in comments!
Problem:
Given a permutation p of length n, let c(p) be the number of cycles in p. Suppose p is drawn uniformly from the set of all permutations. Show that
Expectation of 2 raised to the power of number of cycles is n+1, i.e E[2^c(p)]=(n+1)
Hint:
1) There is no high funda group theory/number theory involved. I could solve this in 15 minutes \m/ \m/
2) After you are done, you might want to read this (*Spoiler Alert*)
Solution:
Hint posted by Nikhil Garg (CSE, IIT Delhi third year undergraduate student) in comments! Solution posted by Kalyan in comments! Kalyan's comment explained in detail by me in comments! A simpler solution posted by Gaurav Sinha (chera) (CSE IITK 1996 Alumnus, Indian Revenue Service) in comments!
Follows trivially from definition of Stirling number of first kind and inversion rules between ordinary powers & rising powers ! < 5 mins ! \m/
ReplyDeleteIf only I could imagine that people know about properties of Stirling numbers of first kind! :P
ReplyDeletedoes not it follow from induction?
ReplyDeletebasically we have to prove that summation(p=1 to n!)2^c(p)= (n+1)!
2 cases arise
case 1:
wlog assume 1st n-1 nos are being permuted and the nth one is fixed.then there are (n-1)! such permutations and in each no of cycles increases by 1 only.So it contributes 2(n!).
case 2:
Now let n be permuted to 1 and rest as they are. Here the no of permutations are same as the (n-1)th case and their are n such cases. hence (n-1)*n!.
=>total=(n+1)!
@kalyan. You are correct!
ReplyDeleteLet the number of permutations of n numbers with m cycles be f(n,m)
So, P(sigma has m cycles) = f(n,m)/n!
So, TPT (Sigma over m) 2^m*f(n,m)/n! = n+1
TPT (Sigma over m) 2^mf(n,m) = (n+1)!
We know that f(n,m)=(n-1)*f(n-1,m)+f(n-1,m-1)
Using induction over n for hypothesis (Sigma over m) 2^mf(n,m) = (n+1)!
Base case: n=1, LHS=RHS=2
n+1 case: Directly follows from the recurrence
Hence, proved.
and as pointed by Nikhil, follows directly from Stirling Numbers of First Kind property: Wiki Page (Unsigned Stirling numbers of the first kind (put x=2!)
ReplyDeletesimilar solution using induction.
ReplyDeletefix and consider an arbitrary element A.
its easily seen that probability that A goes in a cycle of length k = 1/n.
conditional expectation given that A goes in a cycle of length k = 2* E(n-k)
so E(n)= sigma (1/n)*2*E(n-k)
=sigma (1/n)*2*(n-k+1)
=(1/n)*2*n*(n+1)/2
=n+1.
@chera. (Gaurav)
ReplyDeletePlease elaborate on "its easily seen that probability that A goes in a cycle of length k = 1/n"
@pratik
ReplyDeleteif A is an arbitrary element,a cycle of length k having A can be written as (A x1 x2...x(k-1))
So no. of such cycles =
C(n-1,k-1)*(k-1)!
=(n-1)!/(n-k)!
given a cycle of length k, remaining (n-k) elements can be permuted in (n-k)! ways.
so total no. of permutations is (n-1)!. so probability = 1/n i.e. independent of k. seems counter intuitive.
that looks correct. thanks
ReplyDeleteI once saw a beautiful combinatorial proof for the above claim of Chera. I'll prove that probability 1 is in cycle of length k is 1/N for all k in [1..N] and for any other element same result holds by swapping 1 & that element.
ReplyDeleteNow take any permutation, decompose it into product of cycles, rotate all cycles so that least element of cycle is in right most position, and order cycles on this least element. Now just write down all cycles one after the another. This is a permutation of 1..N
Also given any permutation of 1..N its easy to create a cycle form of a different permutation by reversing process - elements till 1 go in first cycle, then elements till least remaining element go in 2nd cycle and so on.
So this is a bijection in any cycle representation and all permutations. So P[ 1 is in cycle of length K] = P[ Kth element in permutation is 1 ] = 1 / N
Hence proved :)