All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Guessing Game (Posted on 2014-05-16)
We decide to play the following game: An integer N will be randomly selected from the interval 0 - 100, inclusive. You try to guess N. After each guess, I tell you whether N is higher or lower than your guess.

If you successfully guess the integer, you win N dollars. Each guess costs you K dollars.

For each of the variants (a) and (b) below, what is the maximum value of K for which you'd be willing to play this game? Which strategy would you use to try to maximize your winnings in the long run?

(a) Once you start a round, you must continue until you guess N exactly.

(b) You may stop playing a round if you determine that N is too small to keep paying more money to guess N exactly. The money you've already spent on guesses is lost, but you may then start a new round with a new N.

 No Solution Yet Submitted by tomarken Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 different part b solution (VB program) | Comment 7 of 18 |
I'm getting the following expected values for different K in part b:

K   expected value
2  39.14851
3  34.25743
4  29.72277
5  25.54455
6  21.72277
7  18.15842
8  14.63366
9  11.32673
10   8.26733
11   5.45545
12   2.89109
13   0.57426
14  -1.49505
15  -3.46535
16  -5.43564
17  -7.40594
18  -9.34653
19  -11.13861
20  -12.77228

In the 13 dollar range:

13.00   0.57426
13.01   0.55257
13.02   0.53089
13.03   0.50921
13.04   0.48752
13.05   0.46584
13.06   0.44416
13.07   0.42248
13.08   0.40079
13.09   0.37911
13.10   0.35743
13.11   0.33574
13.12   0.31406
13.13   0.29238
13.14   0.27069
13.15   0.24901
13.16   0.22733
13.17   0.20564
13.18   0.18396
13.19   0.16228
13.20   0.14059
13.21   0.11941
13.22   0.09822
13.23   0.07703
13.24   0.05584
13.25   0.03465
13.26   0.01347
13.27  -0.00772
13.28  -0.02891
13.29  -0.05010
13.30  -0.07129
13.31  -0.09248
13.32  -0.11366
13.33  -0.13485
13.34  -0.15604
13.35  -0.17723
13.36  -0.19842
13.37  -0.21960
13.38  -0.24079
13.39  -0.26198
13.40  -0.28317
13.41  -0.30386
13.42  -0.32455
13.43  -0.34525
13.44  -0.36594
13.45  -0.38663
13.46  -0.40733
13.47  -0.42802
13.48  -0.44871
13.49  -0.46941
13.50  -0.49010
13.51  -0.51079
13.52  -0.53149
13.53  -0.55218
13.54  -0.57287
13.55  -0.59356
13.56  -0.61426
13.57  -0.63495
13.58  -0.65564
13.59  -0.67634
13.60  -0.69703
13.61  -0.71723
13.62  -0.73743
13.63  -0.75762
13.64  -0.77782
13.65  -0.79802
13.66  -0.81822
13.67  -0.83842
13.68  -0.85861
13.69  -0.87881
13.70  -0.89901
13.71  -0.91921
13.72  -0.93941
13.73  -0.95960
13.74  -0.97980
13.75  -1.00000
13.76  -1.02020
13.77  -1.04040
13.78  -1.06059
13.79  -1.08079
13.80  -1.10099
13.81  -1.12069
13.82  -1.14040
13.83  -1.16010
13.84  -1.17980
13.85  -1.19950
13.86  -1.21921
13.87  -1.23891
13.88  -1.25861
13.89  -1.27832
13.90  -1.29802
13.91  -1.31772
13.92  -1.33743
13.93  -1.35713
13.94  -1.37683
13.95  -1.39653
13.96  -1.41624
13.97  -1.43594
13.98  -1.45564
13.99  -1.47535
14.00  -1.49505

So I get 13.26 as the maximum with a positive expectation: about one and a third penny.

DefDbl A-Z
Dim crlf\$
Dim guess(100, 100), minbid(100, 100)
Dim expVal(100, 100), k

Function mform\$(x, t\$)
a\$ = Format\$(x, t\$)
If Len(a\$) < Len(t\$) Then a\$ = Space\$(Len(t\$) - Len(a\$)) & a\$
mform\$ = a\$
End Function

Text1.Text = ""
crlf\$ = Chr(13) + Chr(10)
Form1.Visible = True
DoEvents
For k = 13 To 14 Step 0.01
For span = 1 To 101
For start = 0 To 100
fin = start + span - 1
If fin <= 100 Then
If span = 1 Then
expVal(start, fin) = start - k
guess(start, fin) = start
minbid(start, fin) = start
Else
bestev = -999999
For firstcon = start To start + span - 1  ' first considered (stop if less)
For g = firstcon To start + span - 1   ' temporary consideration of guess
ev = g / span  ' hit it this guess
If g > firstcon Then ev = ev + ((g - firstcon) / span) * expVal(firstcon, g - 1)
' considers prob. of new subspan times expected value of that subspan, previously
' calculated as we're building bottom up
If g < start + span - 1 Then ev = ev + (((start + span - 1) - g) / span) * expVal(g + 1, start + span - 1)
' likewise for the subspan above the guess under consideration
ev = ev - k  ' pay the bill for the try
If ev > bestev Then ' consider only the guess that gives the highest expectation
bestev = ev: bestfirstcon = firstcon: bestg = g
End If
Next g
Next firstcon
guess(start, fin) = bestg
minbid(start, fin) = bestfirstcon
expVal(start, fin) = bestev
End If

End If
Next start
Next span
Text1.Text = Text1.Text & mform(k, "###.00  ") & mform(expVal(0, 100), "#0.00000") & crlf
DoEvents
Next k
End Sub

Strategy comes from a table of expected values, built from the bottom (range of only 1) up.

Edited on May 17, 2014, 4:28 pm
 Posted by Charlie on 2014-05-17 16:15:35

 Search: Search body:
Forums (0)