一つ読むか、三つ読むか。
三つの情報源のうち、一つが正常な報告を見てから虚偽の値を返し得る。そのような観測モデルで、要求精度と失敗確率を満たすための最小観測費用を厳密に求めました。適応的な取得と乱数の利用を含むすべての許容戦略について、最悪時の期待費用の下界と、それを達成する計画が一致します。
最悪時の期待観測費用（費用単位）
許容失敗確率 δ
達成する観測計画 = 全戦略の下界
r₃ ≈ 0.2698546%r₁ ≈ 33.4233456%
線分の両端は、三つすべてを読む計画と、三つから一つを等確率で選ぶ計画です。許容失敗確率が5%のとき、最小の最悪時期待費用は約5.4293費用単位になります。
達成する費用が、理論の下限になる。
時刻4の値を、誤差1以内で推定したい。許容されるどの軌跡と攻撃に対しても、誤差が1を超える確率を5%以下に抑えるには、どこまで観測する必要があるでしょうか。
後期の観測を一つだけ買えば費用は2、三つすべてなら6です。この二つの買い方を適切な確率で選ぶと、期待費用はどの条件でも約5.4293になります。一方で、同じ精度を保証するすべての戦略に対して、その最悪時の期待費用が少なくともこの値になることを証明しました。
≈ 5.429303494829 費用単位
Q は標準正規分布の上側確率です。r₁ と r₃ は、それぞれ後期観測を一つ読む計画と三つ読む計画の最悪時の失敗確率を表します。
読む前に、選ぶ。
早期の観測は購入しません。最適な計画は、観測を始める前に二つの方法から一つを選びます。約14.2674%の確率で、三つの情報源から一つを等確率で選び、その後期の読取り値をそのまま推定値にします。残りの約85.7326%では、三つすべての後期観測を買い、中位数を出力します。
一つを等確率で選ぶ
費用2。選んだ情報源の読取り値を採用。
三つすべてを読む
費用6。三つの読取り値の中位数を採用。
5%は、この計画全体に課した失敗確率の上限です。計画を選ぶ確率を α とすると、両分岐を合わせた最悪時の失敗確率は αr₁ + (1 − α)r₃ = 0.05 になります。
すべての戦略と比較する。
比較の対象には、早期の読取り値を見て後期に買う観測を変える戦略も、途中で取得をやめる戦略も含まれます。取得後の推定値は、観測結果と推定器だけが知る乱数を使って決められます。
三つの後期観測を買った場合を考えます。虚偽の報告を返す情報源は、二つの正常な読取り値のうち、真値から遠いほうが三つの値の中央に来るように報告できます。この中央値が許容範囲のすぐ外側にあるとき、推定値をずらせば誤りを救えるかもしれません。しかし同じ規則が、もともと範囲内にあった値を外へ押し出す場合もあります。
証明では、許容範囲の境界から一定の距離までに入る確率を、ガウス分布の下で内側と外側に分けて比較しました。最悪の場合、推定値をずらして回避できる誤りの確率は、新たに生じる誤りの確率を上回りません。ここから任意のランダム化推定器のリスク下界が得られます。これを他の取得履歴の下界と合わせると、費用の下限が確定します。
モデルと検証
ここでの費用は、報告を取得するたびに支払うモデル上の単位で数えます。精度の条件は、許容されるそれぞれの軌跡と情報源の振る舞いについて課します。
| 情報源 | 三つのうち最大一つが虚偽の値を返し得ます。どの情報源かは、正常なノイズや取得側の乱数が決まる前に固定されます。 |
|---|---|
| 虚偽の報告 | 軌跡と同じ回の正常な報告を知ったうえで値を返せます。将来の正常なノイズと取得側の未公開の乱数は知り得ません。 |
| 正常な報告 | 採取時の真値に、互いに独立な平均0、標準偏差1/4のガウス雑音が加わります。 |
| 軌跡と目標 | 二つの時刻の間で値が変化する幅は、経過時間の1/4以下です。推定するのは時刻4の値 x(4) です。 |
| 精度 | 許容する絶対誤差は1。各許容世界で、絶対誤差が1を超える確率は5%以下です。 |
| 早期観測 E | 時刻1に採取し、時刻2に返ります。一件の費用は1です。 |
| 後期観測 L | 時刻3に採取し、時刻4に返ります。一件の費用は2です。 |
| 購入の順序 | Eの取得先はすべての報告に先立って選びます。Lの取得先はEの結果を見て決められますが、最初のLが返る前に全件を選んで支払います。 |
実数の読取り値を扱う連続的な戦略空間について、最適性を与えるのは数学的な証明です。プログラムによる再計算では、ガウス分布から得られる定数、有限の回帰テスト、早期観測を購入する各分岐の既存の証明書を検証しました。