期待値 - yuuk1's Digital Garden

# 期待値 Navigation: [[index]] | [[overview]] ## 定義標本空間 S 上の確率変数([[確率変数]]を参照) R の期待値(expectation、平均・average とも呼ぶ)は Ex[R] := Σ_{ω∈S} R(ω)·Pr[ω] と定義される。各値をその確率で重み付けした「平均」値であり、確率変数が実際にその値を取るとは限らない(公平な6面サイコロの期待値は3.5だが、誰も3.5の目を期待して振るわけではない)。同値な定義として、range(R) の値ごとに項をまとめ直すと Ex[R] = Σ_{x∈range(R)} x·Pr[R=x] が得られる(定理18.4.3)。この形は標本空間ではなく確率変数の分布のみに依存するため、実用上はこちらの方が計算に便利なことが多い。指示確率変数 I_A の期待値は対応する事象の確率に等しい: Ex[I_A] = Pr[A](補題18.4.2)。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 18 Random Variables]] §18.4, §18.4.3-§18.4.4) 事象 A のもとでの**条件付き期待値**は Ex[R|A] := Σ_r r·Pr[R=r|A] と定義される。標本空間 S の分割 A1, A2, ... について**全期待値の法則(Law of Total Expectation)** Ex[R] = Σᵢ Ex[R|Ai]·Pr[Ai] が成り立ち、複雑な期待値の計算を場合分けして単純化する道具になる。この法則を使うと、各ステップで独立に確率 p で失敗するシステムの最初の失敗までのステップ数 C の期待値が Ex[C] = 1/p(**故障までの平均時間、Mean Time to Failure**の公式)と導かれる。C のような分布は幾何分布(geometric distribution)と呼ばれる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 18 Random Variables]] §18.4.5-§18.4.6) **期待値の線形性(Linearity of Expectation)**: 任意の確率変数 R1,...,Rk と定数 a1,...,ak について Ex[Σᵢ aᵢRᵢ] = Σᵢ aᵢ Ex[Rᵢ] が成り立つ(定理18.5.1・定理18.5.2・系18.5.3)。証明は標本空間上の和の定義(式18.2)を分配則で分解するだけの短いものだが、**この定理は確率変数間の独立性を一切要求しない**という点が本章全体の核心である。これは、複雑な確率変数を(互いに独立とは限らない)指示確率変数の和として分解し、線形性で個々の期待値(=対応する事象の確率)の和に帰着させるという強力な計算テクニックを可能にする。事象 A1,...,An が起こる個数の期待値は Σᵢ Pr[Aᵢ](定理18.5.4)であり、この方法で導かれる。応用例として、n人が帽子をランダムに受け取るとき自分の帽子を受け取る人数の期待値が1になること(帽子チェック問題)、n種類の景品を全種類集めるまでの期待回数が n·Hn ≈ n·ln(n) になること(クーポン収集問題、Hn は調和数)、二項分布の期待値が pn になることが、いずれも独立性の確認なしに導かれる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 18 Random Variables]] §18.5, §18.5.2-§18.5.4) 期待値の線形性を**可算無限個**の確率変数へ拡張するには、Σᵢ Ex[|Ri|] が収束するという絶対収束条件が必要である(定理18.5.5)。この条件を満たさずに線形性を適用すると誤った結論に至りうる。ルーレットの倍賭け戦略(負けるたびに賭け金を倍にし勝った時点でやめる)は、各回の期待利得が0であるにもかかわらず「確実に一定額勝つ」ように見えるパラドックスを生むが、これは各賭け金の絶対値の期待値の和が発散するために線形性の適用条件が満たされていないことに起因する誤謬である。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 18 Random Variables]] §18.5.5-§18.5.7) 和とは異なり、**積の期待値は一般には期待値の積に等しくない**(Ex[R·R]≠Ex[R]·Ex[R] の反例がサイコロの目で示される)。ただし R1, R2 が独立であれば Ex[R1·R2] = Ex[R1]·Ex[R2](定理18.5.6)が成り立ち、相互独立な確率変数の集合へも一般化される。この意味で、期待値の**和**は無条件に線形だが、期待値の**積**は独立性を要求する非対称な性質を持つ。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 18 Random Variables]] §18.5.8) ## 横断的知見 - 期待値の線形性(第18章)は確率変数間の**独立性を一切要求しない**のに対し、[[分散]]の加法性 Var[R+S]=Var[R]+Var[S](第19章)は(相互独立性までは不要だが)**対独立性を必須とする**。この非対称性は証明の構造そのものに由来する: 期待値の線形性は標本空間上の和の並べ替え(分配則)だけで成り立つのに対し、分散の加法性の証明は独立変数の積の期待値の乗法性 Ex[RS]=Ex[R]Ex[S](§18.5.8、これ自体が独立性を要求する)を経由して交差項を消す必要があるためである。R=S(完全に従属)のとき Var[R+R]=4Var[R]≠2Var[R] となり加法性が破れる具体例が、この非対称性を裏付ける。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 18 Random Variables]] §18.5, [[@2015__MIT__Mathematics for Computer Science - Chapter 19 Deviation from the Mean]] §19.3.4) - 期待値の線形性の証明技法(標本空間上の和の並べ替え)は、集中不等式の証明では直接の主役ではない。マルコフの不等式・チェビシェフの不等式・チェルノフ限界はいずれも「Rの適切な非負関数にマルコフの不等式を適用する」という一貫した技法で証明され、期待値の線形性は主にチェルノフ限界の証明で独立変数の積の期待値を展開する際の補助的な道具として現れるにとどまる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 18 Random Variables]] §18.5, [[@2015__MIT__Mathematics for Computer Science - Chapter 19 Deviation from the Mean]] §19.1-§19.2, §19.6.6) - **期待値の線形性が独立性を要求しないという主張は、計算機性能解析の実務書でも同じ形の公式として独立に確認できる**: MCS第18章はこの非対称性(期待値の和は無条件に線形、分散の和は独立性が必要)を証明付きで導くが、Jain(第12章 §12.1)も同じ非対称性を、k個の確率変数の重み付き和について「期待値の和は独立性を仮定せず成り立つが、分散の和が成り立つのは独立変数に限る」という公式としてそのまま述べる。証明の掘り下げでは前者(MCS)が勝るが、性能測定の実務(複数リソースの合計処理時間の期待値など)にこの規則が直接使われる文脈を後者(Jain)が補う。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 18 Random Variables]] §18.5, [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 12 Summarizing Measured Data]] §12.1) ## 未解決の問い - 倍賭け戦略のパラドックス(§18.5.6-§18.5.7)は「無限の資金があれば公正な賭けで確実に勝てる」という結果を導くが、有限の資金制約のもとでの定量的な議論(必要な資金と勝率の関係)は本章では扱われていない。 - 第19章 §19.7 は「確率変数がそれまでの最大値を更新するまでの待ち時間の期待値は無限大になりうる」という例(コイン投げの連続裏記録更新ゲーム)を示すが、これは期待値の線形性ではなく条件付き期待値による直接計算(Ex[R] = Σ_k Ex[R|T=k]・Pr[T=k])に基づく。期待値が無限大になる現象と期待値の線形性(有限和・可算無限和での絶対収束条件、§18.5.5)との関係は追記の余地がある。 ## 関連 - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 18 Random Variables]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 19 Deviation from the Mean]] / [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 12 Summarizing Measured Data]] - 概念: [[確率変数]](期待値はこの上に定義される統計量)、[[二項分布]](期待値 pn の導出例)、[[誕生日原理]](クーポン収集問題の期待値公式が誕生日の網羅問題にも適用される)、[[分散]](期待値の上に定義される二次の統計量。加法性に必要な独立性の水準が期待値の線形性と非対称)、[[要約統計量の選定]](算術平均・幾何平均・調和平均を測定データの実務でどう使い分けるかの規則) ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 18 §18.4-§18.5, Chapter 19 §19.3.4. - Raj Jain, *The Art of Computer Systems Performance Analysis*, John Wiley & Sons, 1991, Chapter 12 §12.1(和の期待値・分散の非対称性の実務的な公式化)。