理想の部屋を探す（秘書問題）

５章の秘書問題が面白かったので実際にpythonで確認してみた。

import random
from statistics import mean

def select(n,r):
   applicants = [random.randint(0, 100) for x in range(n)]
   candicate = max(applicants[0:r-1])

   if candicate == max(applicants):
     return 0
 
   selected = [s for s in applicants[r:] if s > candicate]
 
   if (len(selected) > 0) and (selected[0] == max(applicants)) :
     return 1
   else:
     return 0

print(mean([select(100,50) for i in range(10000)]))

成功確率は0.295くらいで本よりやや低い。選ぶ数のバラツキが大きければ（例えば、randint(0,1000)とか）成功確率は上がって0.34前後。

rを1から変化させながら成功率を取得する。

def r_means(n,r):
   return (r-1,mean([select(n,r) for i in range(2000)]))

rm = [r_means(100,i) for i in range(2,100)]
plt.scatter([x[0] for x in rm],[y[1] for y in rm])
plt.show()

本とはやや違い概ね28~33あたりにピークがある。僕のコードでは30%程度を見送ることで最適の解が得られるという結果。

その問題、数理モデルが解決します（浜田宏）