尤明庆的博客分享 http://blog.sciencenet.cn/u/youmingqing 何苦来哉?心不忍耳!

博文

选麦穗的数值试验 精选

已有 3820 次阅读 2020-1-13 18:45 |个人分类:教学|系统分类:科普集锦| 数值试验, 选麦穗

0    在学院工作群看到教师选岗的条件,真是有趣呢;又想到选麦穗问题:100个麦穗中选取一个,逐个观察而决定是否选取;选后不得更换!

我曾在博文说了,“观察前37个确定极大值而选取其后出现的更大者(37% 规),有37%的可能会落空。……. 倘若看了75个都不能满意,看到第76个时知道已过了3/4、只剩下1/4的历程。您想,既然麦穗随机排列,最好的或许已不能取得;眼前的这个若能进入前三名,大约就是剩余的25个中最好的。在可选中选出可能的最好,才是切实可行的生活态度。怎能说不比前面的都好就不要呢,那是贪婪啊!”

改完两门课程的试卷,离放假还有几天,也就再说几句。 

1   计算机可以模拟选择过程。利用Qbasic 程序在100个(0, 1)之间的随机数进行相应试验。其中B 表示37个中最大,D 是选取,C 100 个中的最大;J 是在总计100个数中的大小排序,L 是出现的序号;0 表示未能选取。下表是前30次的试验结果。 maisu B.jpg

容易知道,只要排序第一不出现在前37个,则选择总能完成,但未必能选到最佳者;若前37个出现的极大值总排序第二,则一定能取得最佳者。从上表还可以看到,数据较少时并无统计规律可言,如排序第一出现在99100 位各两次,且各有一次被取到呢。 

2  考察数M 当然可以调整,下图是M =15~45时各进行10000 次试验取得的排序1~4 数量;排序5以上的次数较少,以实心圆点合并给出。蓝线是选取到最佳者的近似期望值 10000* (M/100)*Ln (100/M) ;弃取的期望值 10000*(M/100)

 maisu C.jpg

就取到最佳者的次数而言,考察数M 25~45 之间差别不大,或者说概率函数xlnx x = 1/e 达到极大值 1/e =0.3679,但极值点附近变化并不显著—— x = 0.250.5 时概率均为0.3466,与极值1/e之差为0.0213,即仅降低了5.8%。从上图看到,该差别与试验10000次的数据波动相当;另一方面,采用较小的M 可以有更多的成功机会,且M = 25时取得前三的几率是70%,而M = 37时只有62%

据此可以做出判断:仅能选择一次且以最优者为目标,可以先考察25% 而后选择出现的更好者。若以排序前三为目标可采取其他策略,如观察前M1确定极大值B1,其后选择出现的更大者至M2;确定前M2 已出现的次大者B2,以后优于B2 即可选取。下图是M1=20~35时的结果。M1=25~30 时的结果较好,考虑到弃选的数量,M2 50左右较好。

 maisu E.jpg

 最佳者在前M1 且次佳者在前 M2,则上述过程将出现弃选,概率为(M1/100)* (M2/100)。对于M1=25、M2=50 弃选的概率为12.5%,取得前三的概率约为68%;若考察25个后仅选更好者,则前三的概率约70%,但弃选则高达25%。

 3   当然可以考察M1 个后分3个层次选取:选择优于已出现的第一、第二、第三者。下表是总计10000次试验的选取者在100个麦穗中的排序情况。表中给出观察 25或37后选取更大者的结果作为参考。

 maisu D.jpg

4  通常所说的37% 规则并不是实际的最优策略:获得最优的期望确实达到最大的37% ,但也有37% 的可能一直等到最后而无可选择。概率极值点附近变化较小,而选择1万次的结果仍存在波动。就此而言,应该依据具体目标采取不同的策略,略述如下。

(1)   若目标是取得第一,则可提前至从第26个开始选择出现的最优者。

(2)  若目标为取得前三,则从第26个开始选择最优者,从51个开始选择最优或次优者,从76个开始选择进入前三者,但有3/32 的概率弃选,即10% 的可能到最后无可选择。

(3)  如果不准备弃选,则可以在 第21个、41个和61个采取上条方案;而若至80个麦穗时尚未选择,则应以剩余数量中可能的最优者为目标进行选择,如第81个若优于已出现的前4名、第91个优于已出现的前9名即可选取。

选择是权利,也需要珍惜呢,因为机会是稍纵即逝啊。此前在博文说过,若是看着第99个,也知道后面还有1个。您会怎么想呢?要是我,这个眼前的麦穗,只要在已展示的99个中排入前50位就行,超过半数就行;除非这个真是不好,才将全部的希望寄予最后。



http://blog.sciencenet.cn/blog-275648-1214062.html

上一篇:浮体平衡等价于重心与浮心的距离达到极值

19 姬扬 刘全慧 郑永军 杨正瓴 史晓雷 刘炜 应行仁 张晓良 黄永义 张忆文 杜学领 张江敏 谢力 武夷山 王从彦 王安良 杨学祥 张云 张鹰

该博文允许注册用户评论 请点击登录 评论 (5 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2020-1-29 06:48

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部