/* Sultan's Dowry in Picat. https://mathworld.wolfram.com/SultansDowryProblem.html """ A sultan has granted a commoner a chance to marry one of his n daughters. The commoner will be presented with the daughters one at a time and, when each daughter is presented, the commoner will be told the daughter's dowry (which is fixed in advance). Upon being presented with a daughter, the commoner must immediately decide whether to accept or reject her (he is not allowed to return to a previously rejected daughter). However, the sultan will allow the marriage to take place only if the commoner picks the daughter with the overall highest dowry. Then what is the commoner's best strategy, assuming he knows nothing about the distribution of dowries (B. Elbows)? Since the commoner knows nothing about the distribution of the dowries, the best strategy is to wait until a certain number x of daughters have been presented, then pick the highest dowry thereafter. The exact number to skip is determined by the condition that the odds that the highest dowry has already been seen is just greater than the odds that it remains to be seen and that if it is seen it will be picked. ... The problem is most commonly stated with n = 100 daughters, which gives the result that the commoner should wait until he has seen 37 of the daughters, then pick the first daughter with a dowry that is bigger than any preceding one. With this strategy, his odds of choosing the daughter with the highest dowry are surprisingly high: about 37% (B. Elbows; Honsberger 1979, pp. 104-110, Mosteller 1987). """ Also see https://en.wikipedia.org/wiki/Secretary_problem The theoretical solution is 1/exp(1) ~ 37% (~0.36787944117144233). Cf my Gamble model gamble_sultans_dowry2.rkt This program was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import ppl_distributions, ppl_utils. import util. % import ordset. main => go. /* This model gives a little higher position (pct) than the theoretical value: about 45% (instead of the theoretical 37%). theoretical = 0.367879 var : skip pos Probabilities (truncated): 36: 0.0162867749790428 29: 0.0162468564129176 44: 0.0154884036565407 35: 0.0152488922597900 ......... 96: 0.0010778012853778 98: 0.0007185341902519 1: 0.0003193485290008 99: 0.0002794299628757 mean = 44.5929 Percentiles: (0.001 2) (0.01 4) (0.025 6) (0.05 9) (0.1 14) (0.25 26) (0.5 43) (0.75 62) (0.84 70) (0.9 77) (0.95 84) (0.975 88) (0.99 93) (0.999 97) (0.9999 99) (0.99999 99) HPD intervals: HPD interval (0.84): 9.00000000000000..74.00000000000000 Histogram (total 25051) 1: 8 # (0.000 / 0.000) 2: 75 ########### (0.003 / 0.003) 3: 105 ############### (0.004 / 0.008) 4: 135 #################### (0.005 / 0.013) 5: 162 ######################## (0.006 / 0.019) 6: 172 ######################### (0.007 / 0.026) 7: 192 ############################ (0.008 / 0.034) 8: 193 ############################ (0.008 / 0.042) 9: 218 ################################ (0.009 / 0.050) 10: 204 ############################## (0.008 / 0.058) 11: 264 ####################################### (0.011 / 0.069) 12: 236 ################################### (0.009 / 0.078) 13: 259 ###################################### (0.010 / 0.089) 14: 283 ########################################## (0.011 / 0.100) 15: 299 ############################################ (0.012 / 0.112) 16: 287 ########################################## (0.011 / 0.123) 17: 279 ######################################### (0.011 / 0.135) 18: 285 ########################################## (0.011 / 0.146) 19: 302 ############################################ (0.012 / 0.158) 20: 343 ################################################## (0.014 / 0.172) 21: 328 ################################################ (0.013 / 0.185) 22: 342 ################################################## (0.014 / 0.198) 23: 373 ####################################################### (0.015 / 0.213) 24: 354 #################################################### (0.014 / 0.227) 25: 356 #################################################### (0.014 / 0.242) 26: 344 ################################################### (0.014 / 0.255) 27: 334 ################################################# (0.013 / 0.269) 28: 349 ################################################### (0.014 / 0.283) 29: 407 ############################################################ (0.016 / 0.299) 30: 353 #################################################### (0.014 / 0.313) 31: 340 ################################################## (0.014 / 0.327) 32: 345 ################################################### (0.014 / 0.340) 33: 375 ####################################################### (0.015 / 0.355) 34: 355 #################################################### (0.014 / 0.369) 35: 382 ######################################################## (0.015 / 0.385) 36: 408 ############################################################ (0.016 / 0.401) 37: 370 ###################################################### (0.015 / 0.416) 38: 369 ###################################################### (0.015 / 0.431) 39: 373 ####################################################### (0.015 / 0.445) 40: 352 #################################################### (0.014 / 0.459) 41: 372 ####################################################### (0.015 / 0.474) 42: 319 ############################################### (0.013 / 0.487) 43: 376 ####################################################### (0.015 / 0.502) 44: 388 ######################################################### (0.015 / 0.518) 45: 341 ################################################## (0.014 / 0.531) 46: 339 ################################################## (0.014 / 0.545) 47: 351 #################################################### (0.014 / 0.559) 48: 320 ############################################### (0.013 / 0.571) 49: 343 ################################################## (0.014 / 0.585) 50: 334 ################################################# (0.013 / 0.598) 51: 331 ################################################# (0.013 / 0.612) 52: 341 ################################################## (0.014 / 0.625) 53: 325 ################################################ (0.013 / 0.638) 54: 346 ################################################### (0.014 / 0.652) 55: 348 ################################################### (0.014 / 0.666) 56: 331 ################################################# (0.013 / 0.679) 57: 321 ############################################### (0.013 / 0.692) 58: 367 ###################################################### (0.015 / 0.707) 59: 291 ########################################### (0.012 / 0.718) 60: 312 ############################################## (0.012 / 0.731) 61: 330 ################################################# (0.013 / 0.744) 62: 279 ######################################### (0.011 / 0.755) 63: 305 ############################################# (0.012 / 0.767) 64: 298 ############################################ (0.012 / 0.779) 65: 291 ########################################### (0.012 / 0.791) 66: 284 ########################################## (0.011 / 0.802) 67: 275 ######################################## (0.011 / 0.813) 68: 248 #################################### (0.010 / 0.823) 69: 286 ########################################## (0.011 / 0.834) 70: 250 ##################################### (0.010 / 0.844) 71: 268 ####################################### (0.011 / 0.855) 72: 233 ################################## (0.009 / 0.864) 73: 217 ################################ (0.009 / 0.873) 74: 224 ################################# (0.009 / 0.882) 75: 208 ############################### (0.008 / 0.890) 76: 195 ############################# (0.008 / 0.898) 77: 206 ############################## (0.008 / 0.906) 78: 199 ############################# (0.008 / 0.914) 79: 189 ############################ (0.008 / 0.922) 80: 180 ########################## (0.007 / 0.929) 81: 198 ############################# (0.008 / 0.937) 82: 162 ######################## (0.006 / 0.943) 83: 160 ######################## (0.006 / 0.950) 84: 156 ####################### (0.006 / 0.956) 85: 142 ##################### (0.006 / 0.962) 86: 137 #################### (0.005 / 0.967) 87: 106 ################ (0.004 / 0.971) 88: 107 ################ (0.004 / 0.976) 89: 104 ############### (0.004 / 0.980) 90: 103 ############### (0.004 / 0.984) 91: 69 ########## (0.003 / 0.987) 92: 71 ########## (0.003 / 0.989) 93: 69 ########## (0.003 / 0.992) 94: 63 ######### (0.003 / 0.995) 95: 46 ####### (0.002 / 0.997) 96: 27 #### (0.001 / 0.998) 97: 35 ##### (0.001 / 0.999) 98: 18 ### (0.001 / 1.000) 99: 7 # (0.000 / 1.000) */ go ?=> println(theoretical=(1/exp(1))), reset_store, run_model(10_000,$model,[show_probs_trunc,mean, show_percentiles, show_hpd_intervals,hpd_intervals=[0.84], show_histogram, histogram_limit=100 ]), nl, show_store_lengths,nl, % fail, nl. go => true. model() => N = 100, R = 1..N, % The position to skip over SkipPos = random_integer1(N), % Each princess has some random dowry (1..n) S = shuffle(R), % S = draw_without_replacement(R), MaxVal = S.max, BestBeforeSkip = cond(SkipPos==1, 1, max([S[I] : I in 1..SkipPos-1])), % The values after skip position that are larger than the best value before skip position Ds = [ S[I] : I in SkipPos..N, S[I] > SkipPos, S[I] > BestBeforeSkip], % Find the first value > best before skip position BestAfterSkip = cond(Ds.len > 0, Ds.first, 1), % Did we get the best dowry? P = check(BestAfterSkip == MaxVal), observe(P == true), if observed_ok then add("skip pos",SkipPos), % add("skip pct",(SkipPos / N)), % add("p",P), end.