失敗しえない Kelly 戦略

 (win-vector.com)
3 ポイント 投稿者 GN⁺ 2024-12-20 | 1件のコメント | WhatsAppで共有
  • 52枚デッキの色分布を追跡し続ける Next Card Bet では、Kelly 戦略は通常の高分散な性質とは異なり、初期資金 $1 を常に約 $9.08 で終える
  • ベットのルールは単純で、残りの赤カード r と黒カード b が等しければ休み、より多く残っている色に現在資金の |r - b| / (r + b) を賭ける
  • Python でシャッフルしたデッキ 10,000 個を実行しても、最終資金は 9.081329549427776〜9.081329549427803 の範囲に収まり、最後のカードだけに賭ける 2倍戦略 より大きな利益を変動なしで生む
  • 証明では、可能な赤/黒の並び (52 choose 26) = 495,918,532,948,104 通りに初期資金を均等配分し、実際のデッキと一致した下位戦略ひとつだけが 52 回連続で 2 倍になるポートフォリオを構成する
  • このポートフォリオの総資金の変化が Kelly 戦略の保守的パターンと一致するため、通常は損失もありうる Kelly 戦略がこのゲームでは 分散 0 の戦略になる

Next Card Bet のルールと直感

  • Kelly bet allocation strategy は、ギャンブル状況で情報や偏りを活用してベット比率を決める方式
  • 一般的な Kelly 戦略は 攻撃的で高分散な戦略 として知られており、Kelly 比率より大きく賭けると破産リスクが高まる可能性がある
  • Peter Winkler の Mathematical Puzzles に登場する「Next Card Bet」では、この戦略がリスクなしで分散 0 として機能する
  • ゲームは標準的な 52 枚デッキから始まる
    • 赤カード 26 枚と黒カード 26 枚が入っている
    • デッキをシャッフルした後、カードを 1 枚ずつ公開し、公開したカードは戻さない
    • プレイヤーは次のカードが赤か黒かについて、現在資金の任意の比率を賭けられる
    • 配当は 1:1 で、初期資金は $1
  • すでに出たカードを数えれば、見えていないデッキに残っている色の枚数が分かる
    • 最後のカードまで賭けずにいれば、残り 1 枚の色は確実に分かる
    • この単純な戦略なら、最後のカードに全額を賭けて資金を安全に 2倍 にできる

Kelly ベット比率

  • Kelly 戦略は、最終資金の対数の期待値を最大化するベットを選ぶ
  • 残っている赤カード数を r、黒カード数を b とし、r > b なら赤が出る確率は r / (r + b) である
  • 期待対数資金は次の式を基準に最大化される
    • P[draw red] * log(1 + bet_fraction) + P[draw black] * log(1 - bet_fraction)
  • この式の導関数が 0 になる点で、ベット比率は (r - b) / (r + b) になる
  • 戦略全体としては、残り 2 色の差分だけリスクを取る
    • r = b なら賭けない
    • r > b なら現在資金の |r - b| / (r + b) の比率を “red” に賭ける
    • b > r なら現在資金の |r - b| / (r + b) の比率を “black” に賭ける

Python シミュレーション結果

  • Python の例では run_bets(is_red) 関数で Kelly 戦略を実行する
    • stake を 1.0 で開始する
    • 各カードごとに残りの赤カード数と黒カード数を更新する
    • より多く残っている色に abs(n_red_remaining - n_black_remaining) / (n_red_remaining + n_black_remaining) の比率だけ賭ける
    • 予想が当たればそのベット額は 2 倍で戻り、外れれば失う
  • 乱数生成器には np.random.default_rng(2024) を使う
  • 52 枚中 26 枚が赤であるデッキを 10,000 回生成した結果、値は事実上同じところに集まった
    • 最小値: 9.081329549427776
    • 最大値: 9.081329549427803
  • 結果の差は 1e-8 未満で、すべての実行で初期資金の約 9.08倍 の利益を生んだ
  • 9.08倍の利益は、最後のカードだけに賭けて安全に 2 倍を得る戦略よりはるかに大きい

分散 0 を作るポートフォリオの証明

  • 赤カードと黒カードの可能な並び数は (52 choose 26) = 495,918,532,948,104 通り
  • 適切にシャッフルされたデッキでは、これらの赤/黒配列がすべて等確率で現れるという標準的な結果を使う
  • ポートフォリオ戦略では、可能なすべての赤/黒配列をそれぞれ 1 つの下位戦略とする
    • 各配列の下位戦略に、初期資金の 1 / (52 choose 26) を割り当てる
    • 下位戦略はそれぞれ自分の資金だけを管理し、相互に再配分しない
    • 各下位戦略は、自分に割り当てられた配列が実際のデッキだと仮定し、各カードで全額をその色に賭ける
  • 実際のデッキと異なるすべての下位戦略は、いずれかの時点で外れたカードに全額を賭けて破産する
  • 実際のデッキと完全に一致する 1 つの下位戦略だけが 52 枚すべてを当て、2^52倍 になる
  • したがって、ポートフォリオ全体の最終利益はカード順に関係なく常に同じ値になる
    • $1 / (52 choose 26) * 2^52
    • 約 $9.08

ポートフォリオと Kelly 戦略の同一性

  • ポートフォリオでまだ破産していない下位戦略は、次のカードを赤または黒と予測している
  • 残りカードが赤 r 枚、黒 b 枚のとき、下位戦略の予測比率は残り色の比率に従う
  • 次のカードが公開されると、外れた予測グループは破産し、当たったグループの資金は 2 倍になる
  • このときポートフォリオ全体の資金変化は、|r - b| / (r + b) を多く残っている色に賭ける Kelly 戦略の保守的パターン と正確に一致する
  • Kelly 戦略が分散 0 になるのは、それ自体が分散 0 のポートフォリオ戦略と同じように動くためである

一般的な Kelly 戦略との違い

  • Kelly 戦略は通常、破産を避けながら資金対数の期待成長率を最大化する
  • しかし一般的な Kelly 戦略は、それ以外の多くを保証するわけではなく、実際に損をすることもあり、通常は 高分散 である
  • このカードゲームでは、損失が出てもデッキの色分布がさらに不均衡になり、その後の条件がより有利になる
  • ベットを十分小さくすれば、外れたベットで失った資本を、その後に大きくなった優位性が相殺する
  • この構造は、A/B テストのような問題における 探索と活用 の段階を思い起こさせる

参考資料

関連記事

1件のコメント

 
GN⁺ 2024-12-20
Hacker News のコメント

  • この戦略が常に成り立つには、賭け金を無限に細かく分割できる必要がある
    たとえばデッキの上のほうに赤いカード26枚が固まっていると、初期の $1.00 の賭け金はいったん 0.000000134 まで減り、その後 9.08 まで戻ることになる

    • 最初の賭け金が $1e12 なら、最悪の場合でも致命的な丸め誤差を避けられる。ここには人生の教訓があるのかもしれない
    • よい指摘。試してみたところ、このシステムは賭け金の量子化や丸めに非常に敏感だった
      期待値はおおむね正しい位置に来るが、分散が急速に大きくなる。そのため、この重要なケース以外でも全般的にかなり不安定だ
    • 離散的な賭け金の場合についての続きのメモをここに追加した: https://win-vector.com/2024/12/21/kelly-betting-with-discret...
      $1 のベットで $8.08 の利益を保証する動的計画法の戦略が知られている。Kelly 戦略を単純に丸めるやり方ではこの結果は出ない
    • たいていはこの点に行き着く。コイントスを、非常に長い期間にわたるすべての投げとして扱う必要があり、戦略がそのまま機能するには一度もスキップしてはいけない
      一度抜けると、利益の出る連続区間や大きな利益を生む特定の一回を逃してしまう。価格対時間のチャートを Renko チャートのように描いてみると、どの商品チャートにも似た見た目になる
      現実の株式/暗号資産/外国為替取引では、ほぼすべての取引を行わなければならないという意味で、そうしないと戦略の性能は落ちる。実験中にコインを替えないのと同じように、取引でも銘柄を替えたり取引を逃したりしてはならず、非常に長く続ける必要がある
      言うまでもなく途方もない一貫性が必要で、金がかかるとストレスも大きい。毎日繰り返すと精神的・身体的な消耗が大きく、長く続けるのは難しい
    • その対になる反対側は、無限の資金があれば Martingale は失敗しないと言うのと同じだ

  • Kelly に関する興味深い脇道として Proebsting のパラドックスがある
    確率論における Proebsting のパラドックスは、Kelly 基準が破産につながり得ることを示すように見える論証である。数学的には解決可能だが、特に投資で Kelly を実際に適用する際に興味深い問題を提起する。Edward O. Thorp が2008年に初めて論じ、考案者である Todd Proebsting にちなんで名付けられた
    https://en.wikipedia.org/wiki/Proebsting%27s_paradox

    • 同じページを引用すると、このパラドックスを簡単に退ける方法は、Kelly が確率は変わらないと仮定している点を見ることだ
      つまり Kelly は、確率を知っていて、その確率が変わらないときに有効である
      確率が分からない、または変わり得るなら、正しいアプローチは Kelly より複雑であるべきだと思う

  • 美しい内容だが、ポートフォリオ論法は不要な回り道のように見える。帰納法で2行の証明ができる

    1. 基底ケースである (0,1) または (1,0) のペイオフは 2 である
    2. (r,b), r >= b の状態で $X を持ち、赤に (r-b)/(r+b) を賭けると、赤を引いて勝ったときのペイオフは X * (1+(r-b)/(r+b)) * 2^(r+b-1) / (r+b-1 choose r-1) = X * 2^(r+b) * r / ((r+b) * (r+b-1 choose r-1)) = X * 2^(r+b) / (r+b choose r) である
      同様に黒を引いて負けたときのペイオフは X * (1-(r-b)/(r+b)) * 2^(r+b-1) / (r+b-1 choose r) = X * 2^(r+b) * b / ((r+b) * (r+b-1 choose r)) = X * 2^(r+b) / (r+b choose r) である。QED
    • その帰納法による証明は、なぜ不要な回り道ではないのか？

  • Timothy Falcon の定量金融インタビュー本の問題 #14 に出てくるように、デッキからカードをめくっていき、いつ止めるかを決める非常によく似たカードゲームがある。赤は $1、黒は −$1 として数える
    Gwern がこれを説明し、最適停止戦略を検証するコードも書いている: https://gwern.net/problem-14

    • 標準的な金融の慣例に従うなら、黒が +$1、赤が -$1 であるべきだ。つまり「黒字」と「赤字」の慣例に合わせるべきだ

  • 10代のころ、カードカウンティングでデッキにより多く残っている色を当てれば、常に半分より多く当てられることを発見した
    https://en.wikipedia.org/wiki/TRS-80_Model_100
    でシミュレーションを書き、一度も失敗しなかった。最近また思い出して Python スクリプトで3000万回回したが、やはり失敗しなかった
    これを何に使えるか考えて、(i) 賭け、(ii) マジックを思いついたが、どちらもあまり有望ではなかった
    賭けなら相手の $10 に対して $1000 を賭けられるかもしれないが、大きな利益を出す道ではないし、ミスをしたり騙されたりすると大金を失いかねない。考え直すと、パーレー（parlay）の形に組み直すほうがよいのかもしれない
    マジックとしては遅すぎる。「超心理学者たちは立派なゼナー・カードで予知能力を安定して証明できなかったが、私は毎回証明できるプロトコルを作った！」というようなセリフも作ったが、十分に面白くないと判断した。デッキ1組を全部めくるのに時間がかかり、奇跡のようにも見えず、p=0.01 で帰無仮説を棄却するには7回連続でやる必要がある。舞台を支配する力がもっとある人なら可能かもしれないが、諦めた

    • これは私の好きなアルゴリズムを思い出させる。異なる項目がいくつあってもよいリストで、過半数要素が存在するなら、O(N) 時間・O(1) 空間で見つけられる
      ときどきこのアルゴリズムを導出してみろというパズルとして出すが、誰も解けなかった。私も解けなかった
      https://en.m.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority...
    • あり得るカードの並びが十分に多いので、疑似乱数の源が全体空間をきちんと走査できない問題を心配する必要があるかもしれない。その場合、シミュレーションは非常に誤解を招き得る
      エントロピーが十分でも、3000万回では確実に十分ではない

  • Kelly 基準は私の好きなゲーム理論の概念の一つで、特にポーカープレイヤーのようなプロのギャンブラーの資金管理でよく使われる
    財務と掛け金をどう管理すれば、過大なリスクや破産を避けながら着実に前へ進めるかを理解させる良い方法だが、その分野ではしばしば誤って適用される。Kelly は二値の結果を扱うので、結果が二値でない状況に適用すると、数学をどう見るかによって、ほぼ正しそうに見えつつ少しずれた結果になることがある

    • Kelly 基準はいろいろなギャンブルの形には優れているように見えるが、ポーカーは例外かもしれない
      ポーカーは他のプレイヤーを相手にするので、特定のチップ分布の効用は、単純な保有チップ数より複雑であるべき気がする
      ポーカープレイヤーではない
    • 「Kelly は二値の結果を扱う」というのは間違い。 https://entropicthoughts.com/the-misunderstood-kelly-criteri...
      Kelly 基準は、連続的で同時的で複雑な配分にもよく一般化される
      必要なのは、選択可能な行動の一覧と、各行動後の富の結果についての結合確率分布だけ。行動は連続的な結果を持つ複合的な行動でもよい
    • Kelly 基準が二値の結果を扱うという点は正しく、だからポーカーには合わない
      ポーカーでは勝敗が二値ではなく、勝つ金額や失う金額が異なるので、期待値を使う。大まかな期待値を計算した後は、分散計算機、たとえば https://www.primedope.com/poker-variance-calculator/ も併用して、長期的に一定のハンド数の間にどれくらいの頻度で、どれくらい稼げそうかを見る
    • ルーレットで色に賭けるやり方にもこれは通用するだろうか？
      勝ちも負けもしないことに多くの時間を費やしそうだ

  • もっと扱いやすい数字、たとえば黒2枚と赤2枚のデッキに縮小したほうが、よりよいデモになったはず
    1ターン目は r = b なので賭けない
    2ターン目は、1ターン目に出なかった色に 1/3 を賭ける
    3ターン目は、2ターン目で外したなら掛け金の 2/3 しか残っていないが、次の2枚の色が分かっているので毎回2倍にして、3ターン後には元の掛け金の 4/3 になる。当てていたなら掛け金は 4/3 だが、赤と黒が1枚ずつ残っているので、このターンは賭けない
    4ターン目は最後のカードの色が分かっているので、金を2倍にして元の掛け金の 8/3 になる
    そして読者に残す練習問題は最適性を証明することだが、かなり straightforward ではあるものの、短い証明があるとは思っていない

    • その通り。ただしカード4枚の例では、3ターン目に非自明な分岐が1つしかない
      だから4枚の例から始めた後、5枚と6枚の場合のツリーダイアグラムを見せると、なお扱いやすい数字なので一般の場合へ帰納する直感を養いやすい
    • 一般的な議論にはついていけたが、カードの順序に関係なく結果が正確に同じになる理由を納得するほどではなかった

  • 実際には、おもちゃの例よりもKelly の使用を難しくする要因が多い
    資金規模とは何か？ 保有現金か？ 総純資産か？ 流動純資産か？ 将来の労働所得か？
    資金規模によって複数の要因が入ってくる。たとえば資金が $100 で、それを全部失っても普通は大事にはならない。しかし資金が $1 million なら、それをリスクにさらすことにははるかにためらいが大きくなる
    期待値とは何か？ 分かっているのか？ 正常なのか？ ゲームは公正なのか？
    期待値の統計的特性に応じて、賭け金サイズのアプローチを大きく調整しなければならない。期待値を推定しかできず、詐欺師が多い領域、たとえばポーカーでは、大きな不確実性の下でベットサイズを決めなければならない
    どのような賭け金額を使えるのか？
    実際には連続的な賭け金額の範囲はない。通常は $5 から $500 まで、$5 または $25 刻みのような離散的な金額しか可能ではない。資金が低くなりすぎるとゲームから締め出され、高くなりすぎるとそれ以上は利益を最大化できない
    結局、プロのギャンブラーはこうした複雑さのために、ハーフ Kelly やクォーター Kelly で賭けることが多い

    • 実際には連続的な賭け金額を作れないだけでなく、ベットを置く権利そのものにも費用を払わなければならないことがある
      取引ではスプレッドと手数料、カジノのテーブルではレーキがある

  • 結果に分散がない点がとても見事。ただ、そのせいで、この問題の特殊な構造上、より高い期待収益を出す戦略があるはずのようにも感じる
    ここでKelly戦略が最適なのか知っていますか？

    • 期待値が最も高そうな気がする。カードが1色だけ残るまで全部めくってから、毎回全額を賭ける戦略を試したところ、100万回回して9.08になった
      最初はこれらの戦略はかなり違うと思っていたが、厳密にはそうでもない。Kelly戦略も1色だけ残れば同じ行動を取る。違いは、この戦略がそれ以前には何もしない点
      それでも両者は極端なケースのように感じる。1色だけ残ったときに全額を賭けるのは唯一正しい手で、結局その前に何をするかの問題になる。何もしないこととKellyだけが、唯一よさそうな戦略に見える
    • 最適とはどういう意味ですか？ より高い期待値のために破産リスクを受け入れられるという意味ですか？
    • 本では「合理的」と呼ぶ戦略集合について最適だと主張している
      ただし、その論証は分散0を示す証明ほど自然な流れではなかったので含めなかった。原文もポートフォリオ内のサブ戦略を「純粋戦略」と呼び、ゲーム理論的な証明を示唆していたように思う
    • このゲームでは、残りのデッキがすべて同じ色なら、その色に持ち金すべてを賭けるというルールだけ守れば、すべての戦略の期待値は同じ
    • Kelly基準こそが、この問題の独特な構造ゆえに、よりよいリターンを出す戦略である

  • この問題と解法はThomas Coverに由来するように見える
    この具体例は覚えていないが、Thomas Coverが教えた授業でKelly基準を学んだ。彼は私が最も好きだった先生の一人で、彼とのどんな議論も興味深く価値があった。RIP

    • 彼はこの分野でも興味深い論文を数多く残しており、その一部はKelly基準に関する本のかなりの部分を占めている