確率過程・期待値DP

概要

確率・期待値DP

確率遷移に対する期待値・分布・到達確率の再帰式を解く。

確率DPでは、分布・到達確率、期待費用、観測後の行動最適化を区別する。以下ではABC300 E、ABC263 E、ABC266 Eの式を用いて、その違いを示す。

ABC300 Eでは初期値1に公平なサイコロの目を掛け、Nへの到達確率を求める。目1を何回引いても成功事象は変わらない。次に1以外が出るまで待つと、2〜6のどの目も確率1/5である。待機が永遠に続く確率は0。

前向きにはp[1]=1とし、値vから2v,…,6vへ各p[v]/5を配る。Nに達した分を吸収し、Nを越えた分を失敗へ集める。未吸収・成功・失敗の総確率は1のまま。

後ろ向きにはq(N)=1,q(v)=0 (v>N)、q(v)=Σ_{d=2}^6 q(dv)/5。再帰先は真に増え、2,3,5の指数で表せる疎な状態だけをmemo化できる。

期待回数なら一試行の費用1を加えるが、到達確率には加えない。法上では5の逆元を用い、N=1や2,3,5以外の素因数を持つNを確認する。

ABC226 Hは連続分布への発展例。閾値xを固定し、各変数がx以上かの独立Bernoulli分布を成功個数DPで合成する。得た裾確率P(Y≥x)をxについて積分して期待値を得る。確率分布を作る工程と、裾確率から期待値を得る恒等式を分けて理解する。

入力: iからi,…,i+A_iへ等確率で移動し、N到達までの期待試行回数をE_iとする。終端はE_N=0。

一歩解析: E_i=1+(E_i+Σ_{j=i+1}^{i+A_i}E_j)/(A_i+1)。自己項を左へ移すとE_i=(A_i+1+ΣE_j)/A_i。費用1まで自己ループと一緒に消してはいけない。

A_i≥1なのでiを離れるまでの期待時間は有限。離れた後は位置が増えるため、後ろから順に解ける。suffix sumで連続区間の和を取れば全体O(N)。

境界: A_i=1ならE_i=2+E_{i+1}。一般に自己ループ確率p=1なら移項して割れず、正の費用を払う過程の期待時間は無限。

入力: 残りr回まで振れるとき、次の目を見る前の最適期待報酬をV_rとする。最後の1回は必ず採用するのでV_1=3.5。

r≥2では目dを観測してから停止か続行を選ぶ。停止はd、続行は独立な未来の最適値V_{r-1}。従ってV_r=(1/6)Σ_{d=1}^6 max(d,V_{r-1})。

max(E[d],V_{r-1})では、目を観測する前に一律に停止・続行を決めることになり別問題となる。V_2=4.25であり、3.5との差は観測情報の価値を表す。

残り回数が減るので後退帰納で最適性を証明できる。O(N)時間O(1)空間。最後の強制停止、同点でどちらを選んでも値が同じことを確認する。

ABC242 Exでは、異なる区間がk種類集まった段階に分ける。次の新種類までの期待待ち時間はM/(M−k)で、その段階まで被覆が終わっていない確率を掛けて足す。全被覆するk-subset数f(k)を別のDPで求めれば、期待値はΣ_{k=0}^{M−1}(1−f(k)/C(M,k))·M/(M−k)になる。

f(k)の計数は、区間を左端順に処理し、隙間なく覆ったprefixの右端rと選択数kを状態にする走査DPである。区間[L,R]を選ぶならL≤r+1を要求し、右端をmax(r,R)へ更新する。一度隙間を残すと後続の区間では埋められない。二つの独立区間の解を掛け合わせる区間DPではない。

考え方

確率分布を前へ伝えるDPと、将来費用の期待値を後ろから解く再帰を分ける。条件付きの次状態ごとの確率に評価を掛けて和を取り、確率が1へ合計されることを確認する。

二次の目的は平均だけで閉じない

E[X²]を求めるなら、一般に(E[X])²では足りず、対角E[X_i²]と異なる二項のE[X_iX_j]を分ける。独立な変数ならE[X_iX_j]=E[X_i]E[X_j]で、E[(ΣX_i)²]=(Σμ_i)²+Σ(E[X_i²]−μ_i²)。個別の二次モーメントからμ_i²を引く補正は、平均和の二乗が対角を既に含むためである。独立性がなければ2Σ_{i<j}Cov(X_i,X_j)も残る。

入力を整数点へ変換する場合、平均の分母をdで払えば二乗の倍率はd²となる。線形補正にもd²を掛け、最適化は元の大小関係を保つ整数で行ってから、法上の回答にd²の逆元を掛ける。途中で剰余へ減らして最大値を比較しない。

ランダム縮約などで独立性がない場合も、添字交換に対する対称性で全pairの相関が同じなら二つの集約値へ圧縮できる。全pair和と一pairの平均を分け、最初の操作の内部pair・外部とのpair・外部同士のpairを数え直して再帰の倍率を導く。確率の等しさは対称性、積への分離は独立性という別の根拠であり、混同しない。

成立条件と計算量

状態・遷移数に比例するのは依存が非循環の場合。自己loopはE=c+pE+…からEを解き、p=1を別に扱う。cycleのある複数状態には連立方程式などが必要。modで確率を表すなら分母の可逆性を確認する。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。一段先で条件分けし、確率・期待値の式と自己ループの移項を扱う。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 動的計画法。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-dp-stochastic

習得する技能

  • 意思決定時点で観測済みの情報を状態にし、行動の最適化と確率平均を正しい順序で組み合わせたBellman式を解ける。
  • 互いに排反な状態に確率を配り、遷移確率・吸収条件・総確率を保って分布や到達確率を計算できる。
  • 状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: 最小十分状態からDPを設計する。

このUnitを直接前提とする単元: 期待値の頻度圧縮と加法的ポテンシャル。

状態と遷移を定義できることを前提に、確率遷移から期待値・到達確率の方程式を立てる。

このUnitでは扱わないもの

  • 二人零和ゲームの勝敗・Grundy数。

根拠