wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Random Permutations & Binomial Parity
        
(Message started by: william wu on Oct 8^th, 2002, 10:18pm)

Title: Random Permutations & Binomial Parity
Post by william wu on Oct 8^th, 2002, 10:18pm

Took a midterm today in Karp's discrete probability / randomized algorithms class. Solutions came out afterwards. I missed the following questions, and I don't know how they solutions were arrived at; perhaps someone could explain. I could just wait till tomorrow to ask the TA, but my curiosity is eating me alive, and response time on this forum is pretty good.

RANDOM PERMUTATION

(9 points) What is the probability that a random permutation of ten elements has exactly 3 cycles: one of length 5, one of length 3 and one of length 2? Hint: count the permutations with the specified property, then divide by 10!

Binomial Parity Problem

(9 points) Let the random variable X_n be the number of heads in n tosses of a coin with probability of heads p. Let E_n be the probability that X_n is even. Give a formula expressing E_n in terms of E_n-1.

Title: Re: Random Permutations & Binomial Parity
Post by william wu on Oct 8^th, 2002, 10:26pm

ok i just figured out what i did wrong with the Binomial Parity Problem ... dumb error. of course you're still welcome to do it if you like :)

Title: Re: Random Permutations & Binomial Parity
Post by Jonathan_the_Red on Oct 9^th, 2002, 11:15am

on 10/08/02 at 22:18:03, william wu wrote:

(9 points) Let the random variable X_n be the number of heads in n tosses of a coin with probability of heads p. Let E_n be the probability that X_n is even. Give a formula expressing E_n in terms of E_n-1.

edit: hidden by color

E₀ = 1
E_n = E_n-1 + p - 2E_n-1p

Title: Re: Random Permutations & Binomial Parity
Post by william wu on Oct 9^th, 2002, 12:35pm

jonathan: yea, that's right.

random permutation answer:

1/30

Title: Re: Random Permutations & Binomial Parity
Post by TimMann on Oct 9^th, 2002, 10:14pm

Are you still looking for the reasoning for the random permutation answer? Here it is, hidden by color.

Write the permutation in cycles as (x x x x x)(x x x)(x x). If the x's are replaced by numbers from 1 to 10, how many distinct permutations are generated? Cyclically permuting the numbers within a cycle doesn't change the permutation, but any other change does. There are 5 ways to cyclically permute the elements within the first cycle, 3 within the second, and 2 within the third, so of the 10! possible assignments of x's, 1/(5*3*2) are distinct. I.e., there are 10!/30 permutations with this cycle structure. So over all the 10! permutations, (10!/30)/10! = 1/30 of them have the specified structure.

Title: Re: Random Permutations & Binomial Parity
Post by william wu on Oct 27^th, 2002, 3:28pm

I figured it out by then, but thanks anyways Tim! Much appreciated.

BTW, the most heavily weighted problem on the test, which most people got blasted by, was just the bachelor's dilemma in disguise. And I had heard it already! God I love this site 8)

( bachelor's dilemma: http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#bachelorsDilemma )