Author |
Topic: Random Permutations & Binomial Parity (Read 1532 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Random Permutations & Binomial Parity
« on: Oct 8th, 2002, 10:18pm » |
 Quote  Modify
|
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 Xn be the number of heads in n tosses of a coin with probability of heads p. Let En be the probability that Xn is even. Give a formula expressing En in terms of En-1.
|
| « Last Edit: Oct 8th, 2002, 10:19pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
 |
Re: Random Permutations & Binomial Parity
« Reply #1 on: Oct 8th, 2002, 10:26pm » |
Quote Modify
|
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 
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Jonathan_the_Red
Junior Member
Gender:
Posts: 102
|
|
Re: Random Permutations & Binomial Parity
« Reply #2 on: Oct 9th, 2002, 11:15am » |
Quote Modify
|
on Oct 8th, 2002, 10:18pm, william wu wrote:
(9 points) Let the random variable Xn be the number of heads in n tosses of a coin with probability of heads p. Let En be the probability that Xn is even. Give a formula expressing En in terms of En-1.
|
|
edit: hidden by color
E0 = 1
En = En-1 + p - 2En-1p
|
| « Last Edit: Oct 9th, 2002, 12:46pm by Jonathan_the_Red » |
IP Logged |
My arcade cabinet
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Random Permutations & Binomial Parity
« Reply #4 on: Oct 9th, 2002, 10:14pm » |
Quote Modify
|
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.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print