期待値の頻度圧縮と加法的ポテンシャル

概要

種類名に関する対称性を使い、高次元の期待残り費用を頻度別関数の和へ分離する。一種類の一段方程式を自己ループも含めて解き、終端で定数を較正する。

全体状態が巨大でも、種類名を交換して遷移が変わらず、一種類の周辺遷移が現在個数jだけで決まるなら、Φ(state)=Σ_c g(count_c)という形を試す。周辺過程同士が独立である必要はなく、条件付き期待値の線形性を使う。各項の期待ドリフトを合わせて一操作分の費用にし、終端でΦを較正する。

ABC249 Exではg(j)=1/N+Σ_k P[j][k]g(k)を0≤j<Nについて課す。固定色から選ぶ個数sの確率q_s=C(j,s)/2^jと、他色の選択数の平均(N−j)/2を使い、α_s=(s+(N−j)/2)/Nとする。q_0=2^(−j)、q_(s+1)=q_s(j−s)/(s+1)を逆元表で生成する。P[j][j−s+1]へq_sα_s、P[j][j−s]へq_s(1−α_s)を加えれば一行O(j+1)で作れる。増加先が高々j+1でP[j][j+1]=(N−j)/(N·2^(j+1))≠0なので、g(0)=0からg(j+1)=(g(j)−1/N−Σ_{k≤j}P[j][k]g(k))/P[j][j+1]を順に解く。全行を保存せず一行ずつ処理すれば時間O(N²)、空間O(N)。存在しない色も個数0として含め、初期頻度和から単色終端のg(N)を引く。

吸収時間を解く一般の巨大連立方程式から、対称性による頻度圧縮、一段方程式の疎な依存、終端での定数調整へ分けて考える。二項係数・畳み込みは周辺分布P[j][k]を計算する補助工程であり、組合せ構造を母関数で符号化する問題としては扱わない。

考え方

大きな確率状態を直接持つ前に、累積費用を一手ごとの期待寄与へ分ける。状態関数Φの期待増分が簡単なら、始終点の差や停止時刻の和から期待値を導ける。

符号を固定すると、一手費用c(s)に対しΦ(s)−E[Φ(S_next)|s]=c(s)を満たす関数を探す。全ての終端でΦ=Cという同じ定数なら、H(s)=Φ(s)−CはH(終端)=0かつH(s)=c(s)+E[H(S_next)|s]となり、期待残り費用の一段方程式になる。停止時刻τまで足すと途中のΦが消え、有限状態でΦが有界、かつE[τ]<∞などの条件の下でE[Σ_{t<τ}c(S_t)]=Φ(S_0)−C。終端ごとのΦが異なる場合はE[Φ(S_τ)]が残るので、定数一個を引くだけでは済まない。

ABC249 Exの式も、この減少量を一色あたり1/N、N色の和で1にしたものである。g(0)=0から未知の次項を求める具体式は、g(j+1)=((1−P[j][j])g(j)−1/N−Σ_{k<j}P[j][k]g(k))/P[j][j+1]。増加先がj+1までなので右辺は既知値だけとなる。消えた色も含むN色のうち終端は一色がN、他は0だからC=g(N)+(N−1)g(0)=g(N)。初期頻度和からg(N)を引く理由はこの終端較正にある。

成立条件と計算量

停止時間を含む議論では有限期待時間や有界性など、式の交換を正当化する条件を確認する。期待寄与を求める費用と必要な集計状態数を評価する。独立性がなくても期待値の線形性は使える。

問題一覧

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

前提・学習成果・出典

習得対象の目安: 橙色(2400–2799)。対称性と線形性で期待値を頻度別関数の和に分離し、終端条件まで較正する。

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

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

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-additive-expectation-potential

期待値の頻度圧縮と加法的ポテンシャル

習得する技能

  • 対称な確率過程の期待費用を頻度別関数の和へ分離し、自己ループを含む一段方程式と終端の較正から吸収までの期待費用を求められる。

前提と範囲

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

直接の前提単元: 確率過程・期待値DP。

このUnitを直接前提とする単元: なし。

確率・期待値DPで得た考え方と実装を再利用し、期待値の頻度圧縮と加法的ポテンシャルの発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • 期待値の頻度圧縮と加法的ポテンシャルの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠