最適停止問題・海辺の美女問題で３人選ぶなら？

質問

最適停止問題で、よく「２０人の女性から１人のみ」選ぶ問題がありますが
　ｎ人、ｍ番目、この人の全体の順位の平均を b(m,r)とすると
　b(m,r) ＝ r (n+1) / (m+1) より
◆はじめの５人はとにかく見送る。
◆６～１０人目は、それまでで１位(最高,最適)なら声をかける。
・・・となると思うのですが

【２０人から３人をOKしたい場合は、どのようになりますか】

■１人のみを選ぶつもりでも、最適ポリシー,平均期待値が４位以内になるのは存じているのですが
■最初から３位以内(３人)を選ぶつもりで算出したいのですが・・
■n-２ や m+2に、意味はありませんか？■ほぼ不可能ですか？
どなたか、ご指導くださいませm(__)m

回答No.7

MagicianKuma · ベストアンサー

No6です。（No1～No5ではありませんので）
＞これが最初から問題文の意味です！！ｗ
もう少し勉強した方がよいです。
質問には「２０人の女性から１人のみ」選ぶ問題がありますと提示されて、その答えが
はじめの５人はとにかく見送る・・・と書かれています。これは最良選択問題の解ではありません。順位最小化の解です。
最良選択問題(最良を選ぶ確率を最大にする)問題の解なら、7回見送りが解です。そもそも最良選択問題では期待値はでてきません。
私の提示した問題は3人まで選べる時の最良選択問題です。でもって答えは超難解です。次のURLが参考になるかも

http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1263-11.pdf

蛇足ですが、
No1～No5さんは数学カテではよくお見かけする方で、理解力・知見ともすばらしい人です。
なので、他人の理解能力を云々する前に、あなたの説明能力を振り返ってみられることをお勧めします。

回答No.6

MagicianKuma

やはり何を最適化するのかを質問者自らはっきりさせないと議論は進まないかと。。。
「２０人の女性から１人のみ」選ぶ問題の場合でも、
最良選択(第一順位のひとを選ぶ確率を最大にする戦略を求める・・・一番以外は無意味だと思う人向け）
とか順位最小化(選んだ候補者の順位の平均値を最小にする戦略）等々いろいろ考えられるのだから。

個人的には、3人まで選べるとして、3人のなかにベスト1の人が入る確率を最も大きくする戦略はなに？
という問題設定にしますな。

補足

やっとそこに辿り着いたんですか。。

＞3人まで選べるとして、3人のなかにベスト1の人が入る確率を最も大きくする戦略はなに？

これが最初から問題文の意味です！！ｗ
　やっと気付いたの・・というのは置いといて
この問題なら解けるのですか？

解けないなら 問題文の理解だけで６度のやりとりを必要したということですか..

回答No.5

stomachman

> ■Ｊとはなんですか？　せめて定義づけして下さい

「j個目のどんぐり」と書いてあります。おそらく「定義」の意味をお分かりでないんでしょう。

> 既存の「浜辺の美女」問題だと申し上げていますが。。

それを改変して3人にするというだけでは、何を最大化したいのかを決めてないのだから、問題が成立していない。
たったこれだけのことが通じないんじゃ、どうにも手に余ります。

補足

J個目のどんぐりと書いてありますね。既にアルゴリズムの中にｗ　問題文中に「J個目」と記載して、単一理解が可能な問題しか解いてこなかったんでしょうね。　そもそもアルゴリズムを教えてくださいという質問なのでしょうか？

＞何を最大化したいのかを決めてない

浜辺の美女問題は、何を最大化したいのか、決めていないのですか？
この話、シツコイですね。。
　改変前の１人でも、改変後の３人でも
　求めるものは同じのはずですが...　あなたに「美しさの最大値」などというと、またおかしなケチをつけるでしょうから、言いにくいです。

既存する問題に「問題が成立していない」なんて言葉、勘違いも甚だしいと思いますが。。

　問題解明できずで、それで他人の問題文を
　自分が解けないからと非難するのはいかがなものでしょう。

回答No.4

stomachman

ANo.3へのコメントについてです。

> 回収率が証明しています。

　数学カテゴリーなんで、「定理」や「証明」という用語は、数学における意味で解釈致します。そしてもちろん、経験則では証明にはなりません。
　問題設定が現実離れしていると、しばしば直感に反する解が出ます。つまり「馬の人気順とレースの結果は無相関」だなんてとんでもない問題設定をすると、余りにばかばかしい（けれども問題に対する解としては正しい）答が出るということです。

> そこまで反論する自信があるならせめて

　反論？ いえいえ、単に、手抜きしないで質問を明確になさるべきだ、と言ってるだけです。仰る所の「海辺の美女問題」すら、最も典型的な最適停止問題である「秘書問題」と評価基準がちょっと違うだけのバリエーションであり、しかし両者の解は全然異なります。なので、評価基準を明確にする必要があるということを説明した積もりなんですが、そこまで分かって戴けないとは予想外でした。

> ならばオリンピックで回答下さいょ。

　オリンピックの、例えば砲丸投げを考えるにしたって、選手がランダムな順番では出てきてくれやしません。やっぱりどんぐりの方が良いでしょう。
　「N, M, Hは既知の自然数である。どんぐりをランダムにN個拾う。ひとつ拾うたびに、そのどんぐりを既に拾ってあるどんぐりと背比べした上で、印をつけるか付けないかを決める。ただし、印を付けて良いのは高々M個である。N個拾い終わったとき、印を付けたどんぐりのうち、少なくともひとつの背の高さがN個中のH位以内になる確率が最大になるようにしたい」
というのなら問題ははっきりしています。

　アルゴリズムとして書くと、
(1) j=0として(2)へ。
(2) jを1増やす。j>Nならば終わり。さもなくば j個目のどんぐりを拾って(3)へ。
(3) j個目のどんぐりがこれまで拾ったj個のうちh(j,0)位以内なら、m=1とし、j個目のどんぐりに印を付けて(4)へ。さもなくば(2)へ。
(4) jを1増やす。j>Nならば終わり。さもなくば j個目のどんぐりを拾って(5)へ。
(5) 最後に印を付けたどんぐりがこれまで拾ったj個のうちh(j,m)位以内なら(4)へ。さもなくば、(6)へ。
(6) mを1増やす。m>Mなら(7)へ。さもなくばj個目のどんぐりに印を付けて(4)へ。
(7) 終わり。

　このアルゴリズムが終了した時点で
C: 「背の高さがN個中でH位以内のどんぐりに、どれも印が付いていない」
という状況が生じる場合は2通りある。まず、(2)で終わりになった場合、つまりひとつも印を付けないまま全部スルーした場合です。それから、(7)に到達して終わりになった場合、つまり、印を付けたM個のどんぐりがどれも(H+1)位以下になった場合です。（こういうことは、最適停止問題には出て来ない。評価基準がまるで違うので、問題の性質もかなり異なっているんです。）
　さて、このアルゴリズムには未定の部分、すなわち関数h(j,m)があります（もちろん、h(j,m)≦H, h(1,0)≦0であるべきだということは明らかですが）。これを調節して、Cが発生する確率を最小にしたい、というのが、問われるべき問題です。

　典型的な問題に比べてだいぶ難しくなったようですが、しかし「ならばオリンピックで回答下さいょ」程度の話に過ぎないんだから、解なんかどうでもいいですょね。ま、気が向いたら分析してみるかも知れません。無理せずにネ（藁

補足

■Ｊとはなんですか？　せめて定義づけして下さい

＞手抜きしないで質問を明確になさるべきだ
＞問題設定が現実離れしていると、しばしば直感に反する解が出ます。

既存の「浜辺の美女」問題だと申し上げていますが。。
　それで３人の場合は？と申し上げているのに、質問文が、不明確ですか。。超アキれますｗ

■百歩譲って、せめて解けないなら分かりますが、問題文は既に存在しています。
　あなたはそれにケチをつけているのですよｗ

非現実なのは、浜辺の美女の問題時点で、そんなこと当たり前なのに
あなたが、不明確と問題にケチをつけるので、現実論を申し上げただけですｗ
そうすると、今度は、あなたが否定しています。。。

第三者からみると、互いがまさに「どんぐり」でしょうね♪
ですが、私が質問者です。質問に正確に回答して下さらないから、このようになっていることぐらい理解できますよね♪

回答No.3

stomachman

ANo.4へのコメントについて。

> 想定通りの質問。

意味不明です。

> 期待値は競馬の回収率の話です。

あれま。競馬の話だったんですか。すると、人気順に馬を一頭ずつパドックに引き出す。で、一体、馬の何を見て何を判断するという話なんでしょうか？

> 期待値は競馬の回収率の話です。

　それぞれの馬が勝った時の賞金が決まっていないと計算になりません。オリンピックだの美女だの場合、賞金はどう決まると仰るんでしょう？

> 定理が無い質問

意味不明です。もしかして、「辻褄が合ってない質問」という意味で仰っている？質問が何なのか、補足によってますます混迷しているようで。

> 海辺の美女問題をはじめとする、最適停止問題はランダムが前提です。
> オリンピックも、競馬も、ランダムが前提です。

そうだったんですか。ということは、競馬の場合、馬の人気順とレースの結果は無相関であるという仮定を置くってことですね。しかし、人気が高いほど賞金は低いのですから、回収率を最大化するには、人気が低い順に選べばいいのは自明でしょう。

補足

競馬を人気で選ぶ。という質問が間違っていたようですね。ならばオリンピックで回答下さいょ。
ただし「競馬で人気が低い順に選べばいいのは自明」とのことですが　競馬は18頭立てですが、あなたは16,17,18人気を選ぶという論理。　過去１度も、その決着はありませんよ。。少なくとも「最適」ではないのは回収率が証明しています。

マジ話
浜辺の美女問題すら、そもそも御存知ないなら
本当にムリをなさらないで下さい。
もともと存在する定理にすら
　「美女」とは何を定義にして？　とケチをつけるタイプに見えますが。。

そこまで反論する自信があるならせめて
【ベストの質問形式とは、どういうものか具体的な提示してみて下さい♪】

回答No.2

stomachman

ANo.1へのコメントについてです。
　この話にはイロイロと数学の素養が必要ですね。

> 人気順

　ご質問の元になってる問題の場合には、チェックする順番と順位とがランダムに対応している、ということが前提になってる、ということがお分かりでないようです。

> オリンピックで[３位以内＝色に関係なくメダル]を取れる選手

　「選んだ3人の中に少なくとも1人メダルが取れる人が入っている確率を高くしたい」という意味なのか、それとも別の意味なのか。

> 期待値をなるべく高く求める

　一体何の期待値なんでしょうか。もしかして「期待値」の意味をご存じない？

補足

「選んだ3人の中に少なくとも1人メダルが取れる人が入っている確率を高くしたい」
想定通りの質問。　期待値は競馬の回収率の話です。
　定理が無い質問ですので、回答を導く条件など回答者の自由です。

海辺の美女問題をはじめとする、最適停止問題はランダムが前提です。
オリンピックも、競馬も、ランダムが前提です。

回答No.1

stomachman

どんぐりの背比べの話に致しましょう。これなら順位が明確ですから。さて、
何を最適化したいか明確にしないと、問題が成立しない。選んだどんぐり3つの順位をa<b<cとして、たとえば「aの期待値が最小になる選び方」とか、「c<nが保証されている選び方の中でnが最小の選び方」とか、「他の選び方に比べてc=3になる確率がもっとも高い選び方」とか、あるいは「c<10が保証されている選び方の中でa=1になる確率がもっとも高い選び方」とか、選び方の評価基準はほんとにイロイロあるわけで。

お礼

計算に期待値が関係しそうですね♪

補足

■オリンピックで[３位以内＝色に関係なくメダル]を取れる選手を、abcのような50音順に選手を順番にチェックして選ぶとしたら…
■競馬での３着以内にこれる馬を人気順に選び、期待値をなるべく高く求める
　のような言い回しで、なんとかなりませんか？