cf: 確率DP・期待値DP

偏差（平均からの差）を考える

• ICPC 2023 横浜 B 問題
  • https://youtu.be/5LdrFxifW54?si=tfy8qcEdmRxqJ9-a&t=10567
  • 平均値が4/7 の場合 [0,1,1,0,1,1] を [-4/7, 3/7, 3/7, -4/7, 3/7, 3/7] と考える。さらに扱いやすさのために、それぞれ7倍して、[-4, 3, ,3 -4, 3, 3] を考える

期待値典型

$X$ を $1$ から $m$ までの値を取る確率変数とする。このとき、以下が成り立つ。

$$ \mathbb{E}[X] = \sum_{j = 1}^m P(X\geq j) $$

証明: $X = \sum_{j=1}^m 1[X \geq j]$ と考えて期待値の線形性を使う

参照: 寄与・主客転倒

• 古い証明

期待値の線形性

• 独立でなくても使える。
• 0か1の値をとる確率変数と合わせて使われる
• 問題例
  • 二項分布の期待値
  • ランダムに席替えをするとき、座席が変わらない人の人数の期待値は？
  • 1×Nのマス目に白か黒を同確率で塗る。色ごとの連結成分の数の期待値は？
  • ガチャコンプまで繰り返すときの回数の期待値は？

期待値・中央値を求める最適化問題

• 期待値は次の関数を最小化する: $f(x) = \sum_{i=1}^n (x - a_i)^2$