高い確率で

数学において、高確率で発生するイベント（whpまたはWHPと略されることが多い）とは、その確率が特定の数nに依存し、 n が無限大に近づくにつれて 1 に近づくイベントのことです。つまり、 n を十分に大きくすることで、イベントが発生する確率を望みどおりに 1 に近づけることができます。

WHP という用語は、特にコンピュータ サイエンスの確率的アルゴリズムの分析で使用されます。たとえば、n個のノードを持つグラフ上の特定の確率的アルゴリズムを考えてみましょう。アルゴリズムが正しい答えを返す確率が である場合、ノードの数が非常に多い場合、アルゴリズムは 1 に非常に近い確率で正しいことになります。この事実は、アルゴリズムが正しい WHP であると簡単に表現されます。 ${\displaystyle 1-1/n}$

この用語が使用されている例をいくつか示します。

• ミラー・ラビン素数判定: 与えられた数nが素数か合成数かを判定する確率的アルゴリズム。nが合成数の場合、この判定ではn を合成 WHP として検出します。運が悪く、 nが素数であると判定される可能性もわずかにあります。しかし、異なるランダム化でこの判定を何度も実行することで、エラーの確率を無制限に減らすことができます。
• Freivalds アルゴリズム: 行列乗算を検証するためのランダム化アルゴリズム。決定論的アルゴリズム WHP よりも高速に実行されます。
• Treap : ランダム化されたバイナリ検索ツリー。その高さは対数 WHP です。Fusion treeは関連するデータ構造です。
• オンライン コード: ユーザーが元のメッセージ WHP を復元できるようにするランダム化されたコード。
• BQP : 正しい WHP である多項式時間量子アルゴリズムが存在する問題の複雑性クラス。
• おそらくほぼ正しい学習: 学習した関数の一般化誤差 WHP が低い機械学習のプロセス。
• ゴシップ プロトコル:各ノードで一定量のネットワーク リソースを使用し、単一障害点がないようにしながら、メッセージをクラスター全体に確実に配信するために分散システムで使用される通信プロトコル。

• ランダム化アルゴリズム
• ほぼ確実に

• Métivier, Y.; Robson, JM; Saheb-Djahromi, N.; Zemmari, A. (2010). 「最適なビット複雑度のランダム化分散 MIS アルゴリズム」.分散コンピューティング. 23 (5–6): 331. doi :10.1007/s00446-010-0121-5.
• 「分散コンピューティングの原理（講義 7）」（PDF）。ETH チューリッヒ。2015 年2 月 21 日閲覧。