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