e10-optimal-stopping.sagews

3+4

7

#reminder about list slicing
L=[0,0,1,1,0,1,0,0,1,1]
L[:2]
sum(L[:2])
sum(L[:5])

[0, 0] 0 2

#the simplified problem: first you flip T,H, then what should you do?
#generate lots (500) flips
#also calculate #of heads/number of flips
flips = [0,1]
for i in [1..500]:
    flips.append(randint(0,1))
#now we have the flips, lets gerate the outsomes (winnings) in stop after k flips
outcomes = [n(sum(flips[:k])/k, digits = 3) for k in [1..len(flips)]]

flips[:20]
outcomes[:20]
max(outcomes)

[0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1] [0.000, 0.500, 0.667, 0.500, 0.400, 0.500, 0.571, 0.625, 0.667, 0.700, 0.727, 0.750, 0.692, 0.643, 0.600, 0.625, 0.647, 0.611, 0.579, 0.600] 0.750

#repeat many times, we'll record the best outcome, and then average
experiments = 100
total = 0
for j in [1..experiments]:
    flips = [0,1]
    for i in [1..500]:
        flips.append(randint(0,1))
    #now we have the flips, lets gerate the outsomes (winnings) in stop after k flips
    outcomes = [n(sum(flips[:k])/k, digits = 3) for k in [1..len(flips)]]
    best = max(outcomes)
    total = total + best
total/experiments

0.677

#suggests that if we start with t,H we should keep flipping!
#many unanswered questions: we still need a stopping strategy
#what should do after the kth flip?!?!?!??!?!?!??!

#write general code where we can vary (1) the initial sequence of flips (2) the number of flips and (3) the number of experiments
def optimal_stopping_value(flips, number_of_flips, experiments):

    total = 0
    for j in [1..experiments]:

        for i in [1..number_of_flips]:
            flips.append(randint(0,1))
        #now we have the flips, lets gerate the outsomes (winnings) in stop after k flips
        outcomes = [sum(flips[:k])/k for k in [1..len(flips)]]
        best = max(outcomes)
        total = total + best
    return n(total/experiments, digits=3)

#case: T,H, 500 flips, 100 experiments
optimal_stopping_value([0,1], 500, 100)

def optimal_stopping_value(initial_flips, number_of_flips, experiments):
    total = 0
    for j in [1..experiments]:
        flips = initial_flips + [randint(0,1) for i in range(number_of_flips)]
        temp = 0
        maxx = 0
        for k in range(len(flips)):
            temp = temp + flips[k]
            if temp/(k+1) > maxx:
                maxx = temp/(k+1)
        total = total + maxx
    return total/experiments

optimal_stopping_value([0,1],200,200)

70781201016675462384831232006459/107174838508235194734073551715200

n(_)

0.660427410032782

#testing as we vary the number of extra flips
#keeping number of experiments fixed at 200
data_flips = [optimal_stopping_value([0,1],i,200) for i in [1..300]]

scatter_plot([(i+1,data_flips[i]) for i in range(len(data_flips))])

#testing as we vary the number of experiments
#keeping number of flips fixed at 200
data_experiments = [optimal_stopping_value([0,1],200,i) for i in [1..300]]

scatter_plot([(i+1,data_flips[i]) for i in range(len(data_experiments))])

optimal_stopping_value([0,1],1000,1000)

1894748634878756102938236799303409801438276605035650675471371490040630983701347103990669685081489221280309/2836329732955260579874042391633186173846928597865704577159661659222014389471659631207150287535680528000000

n(_)

0.668028337066635