From Newsgroup: comp.programming
ram@zedat.fu-berlin.de (Stefan Ram) writes:
If one assumes that the penultimate dish can be anything, it is
better than 0.5 in half of the cases, in such a case, one would
That was a comma splice; it should read: "... cases; in ...".
I wrote a small Python program to compare this with the strategy you >mentioned. The result is that the strategy given above fares better
by a factor of 1.2146 if every dish's quality is randomly between 0
... or some value near 1.2146
and 1. But the traditional strategy you gave fares better by a factor >between 0.8 and 0.99 when the quality of all the dishes is a priori >restricted to some range [a,b], where a < b and 0 <= a <= 1, at least
for three such cases I looked at.
Here's that Python program:
# Python 3.8
import itertools
import random
last_dish = 4
def calculate_thresholds_for_the_dynamic_method():
global threshold
threshold =[ None ]*( last_dish + 1 )
for position in range( last_dish, -1, -1 ):
if position == last_dish:
expectation_value = 0.5
else:
expectation_value_if_chosen =( 1 + expectation_value )/ 2
probability_of_choice =( 1 - expectation_value )
expectation_value = \
expectation_value_if_chosen * probability_of_choice + \
expectation_value *( 1 - probability_of_choice )
threshold[ position ]= expectation_value
def generation_of_five_random_numbers():
global numbers
numbers = []
for _ in range( last_dish + 1 ):
numbers.append( random.random() )
def traditional_strategy():
seen = []
for dish in range( last_dish + 1 ):
number = numbers[ dish ]
if dish in[ 0, 1 ]:
seen.append( number )
elif dish in[ 2, 3 ]:
if number > max( seen ):
return dish
seen.append( number )
else: return dish
def dynamic_strategy():
for dish in range( last_dish + 1 ):
number = numbers[ dish ]
if number > threshold[ dish ]: return dish
if dish == last_dish: return dish
def compare_both_strategies_using_the_expectation_value():
calculate_thresholds_for_the_dynamic_method()
traditional_total = 0
dynamic_total = 0
for i in itertools.count():
generation_of_five_random_numbers()
traditional_result = numbers[ traditional_strategy() ]
dynamic_result = numbers[ dynamic_strategy() ]
traditional_total += traditional_result
dynamic_total += dynamic_result
if not( i % 100000 ):
print( f'{dynamic_total/traditional_total=:.5}' )
def compare_both_strategies_using_finding_the_best():
calculate_thresholds_for_the_dynamic_method()
traditional_count = 0
dynamic_total = 0
for i in itertools.count():
generation_of_five_random_numbers()
traditional_result = numbers[ traditional_strategy() ]
dynamic_result = numbers[ dynamic_strategy() ]
if traditional_result == max( numbers ): traditional_total += 1
if dynamic_result == max( numbers ): dynamic_total += 1
if not( i % 100000 ):
print( f'{dynamic_total/traditional_total=:.5}' )
compare_both_strategies_using_the_expectation_value()
.
--- Synchronet 3.20a-Linux NewsLink 1.113