Skip to content

Latest commit

 

History

History
38 lines (29 loc) · 1.14 KB

expected_value.md

File metadata and controls

38 lines (29 loc) · 1.14 KB

Topics:

  • Probability
  • Expected Value problems
    • Indicator RV
    • Linearity of Expectations
    • Expected Value of product of RV
    • Independence
    • Markov Chains
    • Head Tail problems
    • Dice Throw
    • Puzzles
  • Contribution Technique
  • Power Technique
  • Symmetry
  • Conditional Expectation

Ref: Expected Value Problems.pdf

Random Walk problems:

  • try going one step and see what's the expected number of steps.
  • try out a recurrence relation.
  • if there is a game where it ends if you reach -a or b, and you start from 0. Expected number of moves = ab.
  • in general expected value problems seem difficult, try to make some observations to make it tractable instead of applying math directly.
  • try symmetry
  • also be aware of the contribution technique.

Trick 1

  • Expected value across integers = Sum .. i * P[i] = Sum ... P[>=i]

Problems to practise:

https://atcoder.jp/contests/abc280/tasks/abc280_e https://atcoder.jp/contests/dp/tasks/dp_j https://atcoder.jp/contests/abc314/tasks/abc314_f