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次的试验结果。
容易知道,只要排序第一不出现在前37个,则选择总能完成,但未必能选到最佳者;若前37个出现的极大值总排序第二,则一定能取得最佳者。从上表还可以看到,数据较少时并无统计规律可言,如排序第一出现在99和100 位各两次,且各有一次被取到呢。
2 考察数M 当然可以调整,下图是M =15~45时各进行10000 次试验取得的排序1~4 数量;排序5以上的次数较少,以实心圆点●合并给出。蓝线是选取到最佳者的期望值近似值 10000* (M/100)*Ln (100/M) ;弃取的期望值 10000*(M/100)。
就取到最佳者的次数而言,考察数M在 25~45 之间差别不大,或者说概率函数 –xlnx 在x = 1/e 达到极大值 1/e =0.3679,但极值点附近变化并不显著—— x = 0.25和0.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左右较好。
最佳者在前M1 且次佳者在前 M2,则上述过程将出现弃选,概率为(M1/100)* (M2/100)。对于M1=25、M2=50 弃选的概率为12.5%,取得前三的概率约为68%;若考察25个后仅选更好者,则前三的概率约70%,但弃选则高达25%。
3 当然可以考察M1 个后分3个层次选取:选择优于已出现的第一、第二、第三者。下表是总计10000次试验的选取者在100个麦穗中的排序情况。表中给出观察 25或37后选取更大者的结果作为参考。