Probability Question
in [Math]
|
Prev: the rational way of discovering the proof of Infinitude of Twin Primes #5.14 Correcting Math
Next: Meaning, Presuppositions, Truth-relevance, Goedel's Theorem and the Liar Paradox
From: mukesh tiwari on 11 Aug 2010 05:06 Hello all , I am just trying to solve a problem and stuck on http://projecteuler.net/index.php?section=problems&id=121. To solve this problem, i am generating the whole tree but it grows quite fast [factorial ] with level and till level 15 its almost impossible enumerate. Here is sketch of solution which i figured out. First turn there are two balls [B,R] , second level [B,R,R] and number of branches are 6, for third level [B,R,R,R] and branches are 24 and for fourth level [B,R,R,R,R] and branch are 120. Now to win in four turn , the number of blue ball chose must be more than red so winning condition is in all four turn i chose all the 4 blue or 3 blue and 1 red. I counted and got there are 11 turn in which number of blue balls are more than red but this method is not applicable to 15 level since 15! is too large to bruteforce. Kindly give me some hint in right direction as i am trying to learn probability. Thank you
From: achille on 11 Aug 2010 07:40
On Aug 11, 5:06 pm, mukesh tiwari <mukeshtiwari.ii...(a)gmail.com> wrote: > Hello all , > I am just trying to solve a problem and stuck onhttp://projecteuler.net/index.php?section=problems&id=121. To solve > this problem, i am generating the whole tree but it grows quite fast > [factorial ] with level and till level 15 its almost impossible > enumerate. Here is sketch of solution which i figured out. First turn > there are two balls [B,R] , second level [B,R,R] and number of > branches are 6, for third level [B,R,R,R] and branches are 24 and for > fourth level [B,R,R,R,R] and branch are 120. Now to win in four > turn , > the number of blue ball chose must be more than red so winning > condition is in all four turn i chose all the 4 blue or 3 blue and > 1 red. I counted and got there are 11 turn in which number of blue > balls are more than red but this method is not applicable to 15 level > since 15! is too large to bruteforce. Kindly give me some hint in > right direction as i am trying to learn probability. > Thank you One way to deal with this is to encode the possible configurations into a polynomial and read off the probabilities from the coefficients of the polynomial. In the i-th round, you have i red balls and 1 blue ball, The probability to get a red ball is i/(i+1) and the blue one 1/(i+1). Now associate a factor 1 if you picked a red ball, x if you picked the blue ball You obtain a factor (i + x)/(i + 1) for the i-th round. Now multiplying these factor for i = 1..n togather \prod_{i=1..n} (i + x)/(i + 1). If you have picked the blue ball say in round 2 and 4, there will be a correspond term: 1/(1+1) x/(2+1) 1/(3+1) x/(4+1) 1/(5+1) ... in the expansion of above product. This correspondence is 1-to-1 and hence the coefficient of x^k in this polynomial is precisely the probability to pick out the blue ball k times out of n round! For example, consider the n=4 case, we get \prod_{i=1..4} (i+x)/(i+1) = 1/5 + (5/12)x + (7/24)x^2 + (1/12)x^3 + (1/120)x^4 So the probability to get more blue than red is 1/12 + 1/120 = 11/120. n=15 is pretty small, you can either expand the product by hand, throw the product to a computer algebra system or write a little program to expand the product. BTW, the probability I get for n=15, k>=8 is 9219406943/20922789888000 I hope this will be useful for you as a benchmark. |