Re: Real tough problem.....pls try...

In <44ac481b$0$4015$9a6e19ea@xxxxxxxxxxxxxxxxxxxx> Chris <spam_me_not@xxxxxxxxxx> writes:

arun.madras@xxxxxxxxx wrote:
You have 100 to start with and 10 bets to make. Each bet turns on the
result of a coin flip. The oracle will tell you which way the coin will
fall, but may lie on just one occasion and may do so after seeing your
bet for that flip. Placing an x dollar bet will return 2x dollars if
the oracle is correct, 0 dollars if wrong. Come up with the strategy
which ensures you the largest possible amount (that is, the strategy
which whose worst-case scenario is as good as possible).

What is the significance of the fact that the Oracle may lie after
seeing your bet? Does the Oracle want to hurt you or help you? Or is the
Oracle's choice about when to lie entirely random?

And what do you mean "may lie"? Is it possible that the Oracle won't lie
at all?

I agree, the problem spec is unclear about "after seeing your bet".
If one's bets are to be "assisted" by the oracle, then the
oracle must make its pronouncements prior to the bet, not after.
Perhaps he means that one must declare the bet amount, wait for
the oracle to speak, and then decide between heads or tails?
Also, are fractional bet amounts permitted? Zero bets ok?

In any case, it's clear that after the oracle has lied once, one
can "bet the house" on each subsequent flip, doubling the stake.
Prior to a lie, one must withhold some amount in order to survive
the loss incurred on a lie. If that fraction is X in (0,1), then on
a lie one is left with fraction X of one's bank, otherwise with 2-X.
So the best result for the player consists in choosing suitable X,
given the worst-case future return available at each step.

Consider the situation where there are N rounds left, and the oracle
has not yet lied. If N = 1, one should bet nothing, since in the
worst case one will then lose and have no further chance to recover.
For N = 2, one should bet 1/3 of one's bank, either getting a return
of 4/3, or losing and then doubling on the last bet to achieve 4/3.
For N = 3, bet 1/2, winning for an ultimate return 3/2 * 4/3 = 2, or
losing and doubling twice to achieve exactly the same (worst) return.
For N = 4, bet 3/5, for an ultimate return of 16/5.
....
For N = 10, bet 9/11, for an ultimate return of 1024/11.

Generalising, bet the fraction 1 - 2/(N+1) when N rounds are left,
for an ultimate return (multiplier) of 2^N/(N+1) over the entire
sequence of bets. Of course, this must turn into some clumsy
approximation if only integer bet values are permitted.

David

.

Relevant Pages

  • Re: Real tough problem.....pls try...
    ... initial amount eventually leaving u 2^N-2 times the initial amount. ... The oracle will tell you which way the coin will ... What is the significance of the fact that the Oracle may lie after ... a lie one is left with fraction X of one's bank, ...
    (comp.theory)
  • Re: Real tough problem.....pls try...
    ... result of a coin flip. ... The oracle will tell you which way the coin will ... but may lie on just one occasion and may do so after seeing your ... What is the significance of the fact that the Oracle may lie after seeing your bet? ...
    (comp.theory)
  • Re: Tech building
    ... There are whole domains of problems which lie ... outside what is calculable by a Turing Machine. ... The mechanisms are ... My backbrain says a QM is equivalent to a TM plus an oracle, ...
    (rec.arts.sf.composition)
  • Re: Real tough problem.....pls try...
    ... result of a coin flip. ... The oracle will tell you which way the coin will ... but may lie on just one occasion and may do so after seeing your ...
    (comp.theory)