前言
在日常生活中，有許需要做選擇的時刻。有時候我們說：「那時候我決定得太匆促了，如果我多等些時候才作決定，情形就要好得多。」但有時候我們又說：「那時候我猶豫太久，如果我即時果斷，也不致拖到後來的地步。」本文將就或然率論的觀點，討論在幾種特殊情況下，如何作最佳的選擇。
問題的開始
我們首先看看摘麥穗的故事。故事梗概是這樣的；一個小女孩同她舅舅在麥田畔散步，這舅舅對小女孩說：「現在我希望妳在定完這片麥田時，摘那枝最大的麥穗給我。妳只許摘一次，而且不許回頭去摘。」這小女孩走著看著。始終覺得前面有更大的麥穗，一直捨不得用去這惟一的機會。快走完麥田的時候，她才發現大麥穗都已過去了，前面都是些小的，後悔不已。故事的最後是這位舅舅的一套人生哲學的教訓。我們的問題是，這個小女孩應當怎樣去摘，才最可能摘到那串最大的麥穗？與此問題類似的問題很多，我們舉幾個例子。
（一）某公司招考工作人員，每天考一個人，現有五十人報考。考完的當天老闆就得決定用不用這個人，如果不用他，他即拂袖而去，此去不回。問題是；如何取得那最好的申請者。
（二）某城有二十間房子出租，某甲希望租到那間最理想的房子，但在看房子之前，他無法知道房子的好壞。假定他看了房子，他就立刻得決定租不租，不租就被別人租去了。問題是；他將如何去看房子以期租到那間最理想的？
（三）老師分二十個蘋果給二十個小朋友。蘋果在袋子裏看不見大小。現在你在最前面，老師每拿出一個蘋果之後都先問你要不要，如果你不要，她就把蘋果給別人。假定你只能要一次，你如何最可能的要到那個最大的蘋果？
問題之一
為了簡化許多不必要的名詞，以上的問題可以想成一個袋子裏有N個球。每個球上有它半徑的數目。假定半徑都不相同，大小我們不知道。我們每次隨便取一個球出來，看了半徑之後就得決定要不要。如果要，取球就此停止。如果不要，再往下取，但不准再回頭要原先的球。這樣下去，直到N個球取完為止。我們的目的是取到那個最大半徑的球。（註一）
在此我們定球的等級為；最大球為N等，次大球為N-1等，……，最小的球為1等。
當我們取出第一球時，我們看見它的半徑是r1，但不知它的等級。現在有二個選擇。一是我們就要了它，二是我們不要它，取下一個看看。如果我們要了它，我們拿到最大球的機會顯然是1/N。
如果我們不要它，我們看到了第二個球的半徑是r2。我們又有二個選擇，要不要它？如果我們就要這第二個球，我們拿到最大球的機會仍是1/N。但仔細一想，如果第二個球的半徑比第一球小，我們要它也沒有用，因它顯然不是最大的，我們不如往下拿。因此當我們拿到第二球時，我們的選擇是：
1.如果r2
3.如果r2>r1，我們仍然往下拿，那就是說我們在任何情形下，不拿前面兩個球。
同理，當我們看到第三球的半徑r3時，我們的選擇是：
1.如果r3
3.如果r3>max(r1,r2)﹐我們仍然住下拿，那就是說，在任何情形下，我們不拿前面三個球。
如此，我們的一般規則是：
1.在任何情形下，不拿前面s-1個球。
2.從s球開始，凡拿到一個球大於max(r1,r2,……,rs-1)的，即取之。如果一直拿不到，那表示最大球在前s-1球之中，只好承認失敗。
現在我們以四球為例，看看情形如何。我們以1,2,3,4表示球的等級，表一表示它們的出場序。根據排列的算法，共有4!＝24種出場的情形，根據隨便取的假定，每種出場序有同樣發生的可能性1/24。
按照上述的規則，若s＝1，就是我們就要第一個，我們有6種排列法可以拿到最大的（即第四列的全部），因此我們拿到最大球的或然率是6/24。若s＝2，則凡打＊號的出場序，我們都可拿到最大的球，其或然率為11/24。若s＝3，則凡打。號的出場序，我們都可以拿到最大球，其或然率為10/24。若s＝4，則只有以4結尾的排列才可以使我們拿到最大的球，其或然率為6/24。
由此可見拿到最大球最好的方法是令s＝2，也就是說越過第一球，從第二球開始選大於第一球的那個球。
對一般N而言，我們若從第S球開始比較，我們拿到最大球的或然率是（註二）：
PN(s)=(s-1)/N〔1/(s-1)+1/s+1/(s+1)+…+1/(N-1)〕
從上式中，我們不難代入所有的s＝1,2,……，N找出能使PN(s)最大的s，我們用s*表示。表二中有許多s*的值。
從表二中顯示出，當球數愈多時，即使我們用最好的方法，找到最大球的機會仍會減小。這並不難想見，因為球多了，那惟一最大的就難找了。根據理論上的推算（註三），這或然率並不趨近於零，而趨近於e-1。這裏的e是自然對數的底，約等於2.72。因此我們看到，因此種猜法猜對的或然率永遠大於1/3。當球數很多的時候，這是一件不容易想到的事實。同時我們也可以推演出當N很大時，最佳值s*略等於Ne-1（註三）。我們不用看表二，只要把球數N除以2.72，即可大約找到我們開始要球的位置了。
問題之二
在摘麥穗問題中，如果我們把條件放寬一點，允許小女孩先摘一枝，然後可以再換一次，選擇的方法又如何呢？我們不難想像這種騎馬找馬的辦法在日常生活中是很常見的。不過換的次數不能太多，否則一直找大的換下去，一定可以換到最大的那個。我們假定只能換一次。
仍然回到拿球的問題上來。現在我們允許猜球者換一次。首先我們也許會想到先取第一個，然後等一段時間，然後再看大的換。根據問題之一同樣的推理，我們可以看出先取第一個的方法並不見得最好，因為第一個是最大球的或然率只有1/N。我們得先等一下才取第一個球。第一個球取出之後，我們再等一下，看到更大的球就換。第一球取出之後要等多久才換，因N而異。我們定 R(t,s)為下列的取球法：
1.先越過t-1個球，在任何情形下都不取。
2.從t球開始，凡有比max(r1,r2,……,rt-1)大的，取之。
3.從s球開始，凡有比max(r1,r2,……,rs-1)大的球，換之。如果在t與s-1之間未取球，則在s之後，仍可換一次。
在R（t,s）中，若s＝t＋1，則表示取過第一球之後，立刻就可以換。這個問題在計算上比問題之一複雜很多，我們不把公式列出來。表三中顯示出最好的t,s使我們容易拿到那個最大的球。
從表三我們可以看出，我們拿到最大球的或然率始終大於1/2。所以如果拿球換球換得得法，我們找到最大球的機會比找不到的機會還大。
仔細看表三中的s*，我們會發現它與表二中的s*相同。我們看出現在的方法只是不使在開始時越過的球太多。
問題之三
在前面二個問題中，目標都在最大的那個麥穗上。如果最大的麥穗在前面我們越過的地方，我們就什麼都不要了。這種「寧為玉碎」的辦法，有時並不可取。在例（一）、（二）、（三）中，公司總得找一個人，我們總要住房子，孩子總要吃蘋果，最好的幸運不是人人都有，我們如何退而求其次盡可能選出最好的人選，房子，與蘋果呢？
再用袋子裏拿球的例子來說，假定我們拿到最小的球可得1分，次小的球可得2分，……，最大的球得N分，我們只能選一次，不准回頭選，但必須選一個，我們如何選才可以得到高分呢？
顯然的，如果我們隨便取一個球，或就取第一個球，我們得分的期望值是
（1＋2＋3＋……＋N）/N＝（N＋1）/2.
如果有一百個球，隨便取的話，得分的期望值是50.5，但如果根據理論推出最好的取法，我們可以使得分的期望值高達97.4。解決這個問題的公式與演算相當的複雜，但我們並不難推出解決此問題的方向。
我們既要越過第一球，同理我們也可以越過前面若干個球。假定球數N＝10，假定我們越過前三球。如果第四球的分數比前三球都高，我們自然取它（否則我們就定為越過前四球了）。如果它分數低，我們拿第五球，等等，如果我們拿到第八球，還未遇到分數高的球，我們就得小心了，因為所剩的機會已經不多，第八球的分數即使不很高，如果「像樣」的話，我們就可以要了。例如第八球是已拿球中分數位第二位的，我們就該取下了。如果第八球實在很小，我們不妨再試第九球，但條件更得降低了。如果第九球在前面九個球中位第六位以上就值得要了，因為最後一球的期望值（屆時你非要不可）只有5.5。
因此，問題之三的取法是
1.先越過若干球，一定不取。
2.此後每取一球，看它在前面已取出球中所佔的等級與它後面尚有多少球作一取捨。
對一般N而言，表格過於繁瑣，我們只舉N＝4為例，看最佳的取法如何。N＝4時最佳取法是：
1.越過第一球，一定不取。
2.若第二球比第一球大，取之，否則取第三球。
3.若第三球在前面三球（一、二、三，三球）中位第二位以上，取之。否則取第四球。
如此取法的得分期望值為3.125，比隨便取的2.5 大了不少。對一般大N而言，最初越過的球數約等於N/3與問題之一的N/e差不太多。由公式演算出的最佳取法，得分的期望值始終大於N-3，也就是說我們平均可取得第四大的球，當球很多的時候這是一個不容易直覺到的事情。
問題之四
摘麥穗問題還可以用到交男女朋友上去。實際上，這個問題在許多數學或統計雜誌上就是以「選美問題」或「婚姻問題」發表的。我們借用童話裏的白馬王子與森林公主來討論此問題的另一發展。
森林公主住在巫婆家裏，巫婆有三個女兒。有一天王子到巫婆家門前來帶公主走。他不認得誰是公主誰是巫婆的女兒，但他知道公主是最漂亮的。（巫婆女兒也不太醜，否則就太容易猜了。）猜的方式與問題一樣，女孩子一個個出來，前門出來後門進去，王子得立刻下決心帶不帶她走，不准回頭帶。王子的目的是認出公主。到目前為止與問題之一完全一樣。現在另加的條件是，巫婆有權安排公主出場的次序，她不希望王子認出公主。
假定王子足智多謀，而巫婆卻也鬼計多端，二個都是絕頂聰明的人。現在看：照問題之一的解法，王子最好的選擇法就是越過第一位出場的女孩子，從第二位開始比較，帶比第一位漂亮的回家。但巫婆她也知道問題之一的辦法，她把公主放在第一位，王子不就失敗了嗎？但王子的智力不弱，他也會想到這點，猜第一位不就準成功了嗎？但巫婆亦非無能之輩，她把公主換到第二位就是了，……如此勾心鬥角，到了認人的時刻，王子當怎樣認，巫婆當怎樣排，才可以造成自己最有利的戰略呢？
首先很明顯的一點是雙方好的戰略都不是固定的而是或然的。換言之，若巫婆最好的方法是把公主放在第幾位出場，王子亦可同樣推出這個位置，結果一猜即中，可見巫婆無固定排法。另方面，如果王子最好的方法是1. 帶走第一位，或惟一其他的選擇2. 不帶第一位，巫婆都可以使他失敗。因此他的猜法也不是固定的。或然的戰略是這樣的：巫婆以或然率把公主排在第一位， p2,p3,p4﹐把公主放在第二、三、四的位置。到時候臨時抽籤或丟骰子（以上述的或然率）安排公主的位置。王子可以算出巫婆的分配法p1,p2,p3,p4﹐但卻無法確定籤或骰子的決定。如果我們用si表示王子越過前面ｉ個女孩子的猜法，則王子好的戰略也是以p1,p2,p3,p4﹐（不一定與巫婆的相同）的或然率採取s0,s1,s2,與s3的方法。
我們以x表示王子的戰略，y表示巫婆的戰略，p(x, y)表示在此兩戰略下，王子猜出公主的或然率。王子希望p（x,y）愈大愈好，而巫婆希望p（x,y）愈小愈好。因王子與巫婆都極聰明，假定他們都找到了他們的最佳戰略x*與y*。那麼x*與y*該有下面的性質：（註四）
1.如果王子不用最佳戰略x*，而巫婆用她的最佳戰略y*，那麼王子成功的機會必然比他用最佳戰略時小，也就是說，對任何王子的戰略x,
p(x,y*)≤p(x*,y*)。
2.同理，如果巫婆不用她最佳戰略y*，而王子用他最佳戰略x*，那麼王子成功的機會會比巫婆用y*時大，也就是，對任何巫婆的戰略y,
p(x*,y)≥p(x*,y*)。
如果兩個都不用最佳戰略說？那麼兩個笨蛋在一起，什麼怪事都可能發生，我們不必為他們傷腦筋。
如何求出滿足1式與2式的x*與y*是遊戲論（Game Theory）中的基本問題，往往要用電子計算機硬找。但本問題的答案並不複雜。
假定巫婆可以隨意安排這四個女孩的位置。巫婆最佳的方法是同以1/4的或然率安排下面任何一種出場序；
1234, 2341, 3412, 4123,
式中1,2,3,4分別表示女孩子漂亮的程度，4代表公主。王子最佳的猜法是隨便猜，他成功的或然率是0.25（註五）。
假定巫婆只可以安排公主的次序，三個女兒不受指揮爭先恐後的亂排，那麼巫婆最佳戰略y*是：
以6/17, 3/17, 2/17, 6/17的或然率把公主排在第一、二、三、四位置上。
而王子的最佳戰略x*是
以6/17, 6/17, 3/17, 2/17的或然率用s0,s1,s2﹐與s3的猜法。（si在前面定義過，即先越過ｉ個女孩的方法。）
在這種情形下，王子猜對的或然率是0.533，比0.25（王子不用心計隨便猜）大，但比0.458（巫婆不用心計隨便排）小。雙方用計，皆有所獲，巫婆以較大的或然率把公主放在頭尾，很合乎我們的直覺。
對一般N而言，如果某人可以安排全部的出場序，他可以使猜者猜對的或然率減至1/N。但如果他只有權安排最好的（或最好的只有權決定自己隱藏的位置），那麼當雙方都用最佳戰略時，猜者猜對的或然率約為1/ （㏒N＋1.6）。由此可見，若有人（聰明人）在出場次序上用計，當N很大的時候幾乎無法猜到最好的。
尾語
本文到此結束，似乎意猶未盡。部分好奇的讀者一定會問：「這些數目到底怎麼算出來的？」筆者很抱歉無法簡化公式而把它們一一列出。本文的目的只是希望把停止論（Stopping Rules）與遊戲論（Game Theory）介紹給科月的讀者。這兩門學問在近代工業管理，產品控制，及戰術戰略（真的打仗）上都有相當大的貢獻。文尾有三篇參考文獻，可以找到大部分的公式及演算。
註一：在麥穗問題中，我們應知道小女孩可以走多長的麥田，或大約的麥穗數目。
參考文獻：
J. Gilbert; F. Mosteller: Recognizing the Maximum of a Sequence. J. of the Am-erican Statistical Asso. (Vol.61) 1966 p.35-73.
Y. S. Chow, etc.: Optimal Selection Based on Rank. Isreal J. of Math. (Vol.2)1964 p.81-90.
D. Y. Lindley: Dynamic Programming and Decision Theory. Applied Stctistias(Vol.10)1961 p.39-51.
没有评论:
发表评论