このページについて

概要:このページでは頭を体操します。

親ページ:このページの親ページは未定です。

目次

ランダムウォークを雛形とする問題

階段の棒人間君

棒人間君が魔の7段階段の5段目にいます。
棒人間君は毎回コインを投げて、表が出れば上に一段登り、裏が出れば下に
一段下がります。7段目にたどり着けばクリア、生きて帰れます。
逆に1段目まで降りてしまったらゲームオーバー、死にます。
さて、この棒人間君が生還できる確率は? もちろんコインの裏表は
1/2の確率で等しく出るものとし、階段の途中でやめることはできないものとします。

SUGIYAMA Shunsuke?の考えた答え

4段目スタートだと生死の確率はどっちもa math image。5段目からの生存確率は1段目からの死亡確率に等しい。6段目からの生存確率は2段目からの死亡確率に等しい。

解をa math imageとして定式化すればよいんじゃないのか?

まず幸運にも最短で生存確定の場合:a math image

次に、4段目に行く確率はa math imageです。そして、ここから生存する確率はa math image。じゃぁ、一回目のコイン投げで6段目に行ってしまったあとの生存確率は?一回目のコイン投げで6段目にいく確率はa math imageです。 そのあとの生存確率は未知なのか。これを未知だとすると、これをa math imageとおいて二本の式をつくらないと解けないわけか(未知数が2個になっちゃうから)。それはなさそうだ。数式は一本でいけるはず、というか1本じゃないならエレガントじゃない。

未知じゃないなら既知か?というと、別に既知でなくてもOK。a math imageに依存する関数として表現できれば数式を一本で済ませられる。すると、6段目からの生存確率は、1)一発で表を出して7段目に到着するか、2)裏を出して5段目、つまりもとの位置にもどってそこから確率a math imageで生存するか、のどちらかになる。

つまり、a math image

ああこれで解けるわ。最初にいきなり考えた「まず幸運にも最短で生存確定の場合:a math image」なんて、考える必要なかったことに気がついた。でもこれが解答へのヒントになったけど。要するに、5段目スタートからは確率a math imageで6段目か4段目にいくしかないので、6段目に行った後の展開と、4段目に行った後の展開の二つだけを(もともとのa math imageをつかって表現してやって)考えらればよかったんだね。

a math image

を解いて、生存確率はa math image

Reference

参考書籍

  • ビルゲイツの面接試験

リンク


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2013-10-27 (日) 18:11:57 (1456d)