I'm looking for a good source with deep theory and practice problems about probability, doesn't matter if it is too math involved, and I would prefer one that is ACM-ICPC training oriented.... thanks in advance..

# | User | Rating |
---|---|---|

1 | tourist | 3882 |

2 | maroonrk | 3539 |

3 | Benq | 3513 |

4 | MiracleFaFa | 3466 |

5 | ksun48 | 3462 |

6 | ecnerwala | 3446 |

7 | slime | 3428 |

8 | Um_nik | 3426 |

9 | jiangly | 3401 |

10 | greenheadstrange | 3393 |

# | User | Contrib. |
---|---|---|

1 | awoo | 192 |

2 | -is-this-fft- | 191 |

3 | Monogon | 184 |

4 | YouKn0wWho | 182 |

4 | Um_nik | 182 |

6 | antontrygubO_o | 171 |

7 | maroonrk | 169 |

8 | kostka | 165 |

9 | SecondThread | 164 |

9 | errorgorn | 164 |

I'm looking for a good source with deep theory and practice problems about probability, doesn't matter if it is too math involved, and I would prefer one that is ACM-ICPC training oriented.... thanks in advance..

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/24/2022 21:24:04 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I need help too!! Anyone? Also need help on game theory.

For game theory this is very helpful : www.math.ucla.edu/tom/Game_Theory/comb.pdf

It should be http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf, and indeed that link seems to be interesting...

ThankU ^_^

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=probabilities

I've read that topcoder article already, but it doesn't seem to be enough, at least for solving problems where you must deal with expectations on random variables...

What would be necessary to learn to solve this problem? http://www.codechef.com/ACMAMR12/problems/MINMAX

Nothing special , it just requires the basic definition of expected number and some about polynomial addition,multiplication and integration .

How do you get the polynomials? I was able to doing only with two variables, by integrating over areas, but for more variables I didn't know what to do.

I will try to explain my solution (though it seems more complex after I see others' solution.) Suppose you have to find the expected value of an expression ,say

M= Max(x_{1},x_{2})Then ,from the definition we have

Assume

M=x, then we have to find the probability that value ofMisx.This will be when one of

x_{1}ORx_{2}is equal tox, and the other has a value less thanx. SoHence ,

E[X] = 2 / 3 .This was the case of simple two variables.Now come to the general case , we want the probability of the operator at the root , such that value after that is

x.Consider this as a state F(node , {either 0,1,2}) , here 0 means that we have to find probability such that it has value equal to

x, 1 means to find less thanx, 2 means to find greater thanx. Now our answer is (root,0) .The transition for example is like :

Suppose expression is : MmxxMxx , then at the root we have Maximum(a,b) operator and we want prob for being equal ,so answer will be:

(F(root->left,0)*F(root->right,1) + F(root->left,1)*F(root->right,0)) . Here F(node,{0,1,2}) will be a polynomial.

This is because either left value will be equal to

xor right , and in either cases the other one will have value less thanx.For base case , if we have a leaf and we have to calculate F(leaf,0) then it is 1 , for F(leaf,1) it is x , for F(leaf,2) it is (1-x) .