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

博文

选麦穗的数值试验 精选

已有 4981 次阅读 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

上一篇:浮体平衡等价于重心与浮心的距离达到极值
下一篇:恒常与变化: 历史地理中的长度单位

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

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

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-9-21 08:18

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部