wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> hidden signaling II
        
(Message started by: amia on May 31^st, 2005, 1:40am)

Title: hidden signaling II
Post by amia on May 31^st, 2005, 1:40am

In continuance to "hidden signaling" (that was solved with the optimal solution - success ~81% i.e., earning ~$0.62 per coin flip). I was analyzing two variations of the problem.

variation 1- Berry and Carry can pre determine 50% of their guesses in which they can double the stakes. What are the limit and the strategy then? (so far I reached a strategy of earning $0.75 per flip and I am sure that $1.13 can not be reached). What would you suggest?

variation 2- Abe has a biased coin with odds 2:1 in favor of "heads". They play the same game with the biased coin but with fair odds (they win $2 if they guess correctly "tails" and lose $2 if they are mistaken regarding "heads"). What are their strategy and chances then?

Title: Re: hidden signaling II
Post by Deedlit on May 31^st, 2005, 3:46am

on 05/31/05 at 01:40:16, amia wrote:

variation 1- Berry and Carry can pre determine 50% of their guesses in which they can double the stakes. What are the limit and the strategy then? (so far I reached a strategy of earning $0.75 per flip and I am sure that $1.13 can not be reached). What would you suggest?

The first thing I would suggest is to use SMQ's family of solutions and just double the stakes at random. This earns about .93213 dollars per flip in the limit. Of course, we can pick the codes more wisely knowing that half the flips are double value, but it won't change the limit. However, as before, there's no proof that we can't beat the limit with a particular case. Time for more computer crunching. :(

Doing the same with your strategy earns 75 cents per flip, so I'm guessing that's what you're talking about above. :)

Quote:

variation 2- Abe has a biased coin with odds 2:1 in favor of "heads". They play the same game with the biased coin but with fair odds (they win $2 if they guess correctly "tails" and lose $2 if they are mistaken regarding "heads"). What are their strategy and chances then?

The description isn't entirely clear; does this mean we get 2:1 odds if we bet on tails, and 1:2 odds if we bet on heads?

Title: Re: hidden signaling II
Post by amia on May 31^st, 2005, 4:19am

1) The question is if we could somehow increase odds by trying the "double bets" to occur more in winning.

2) The intention is to maintain a fair bet even with the biased coin and to see if it would change matters. Naturally, for that purpose, the betting odds should be opposite to the probability odds.

Title: Re: hidden signaling II
Post by Deedlit on Jun 1^st, 2005, 10:54pm

on 05/31/05 at 04:19:00, amia wrote:

1) The question is if we could somehow increase odds by trying the "double bets" to occur more in winning.

Well, SMQ's basic strategy doesn't seem to be able to do any better. I'm leaning towards there not being any improvement, but I'm not sure yet.

Title: Re: hidden signaling II
Post by amia on Jun 2^nd, 2005, 1:36am

me too :(
I can gurentee 100% double stakes winnings but with lower winning probability in total. This is since SMQ success rate is allready high so there is only 19% chance of double stakes loss as it is.

How about the biased coin? Any ideas there?

Title: Re: hidden signaling II
Post by Deedlit on Jun 2^nd, 2005, 6:33pm

I've been flip-flopping on that one - I'll see if I can devote some time to this later.

Title: Re: hidden signaling II
Post by Deedlit on Jun 5^th, 2005, 2:28am

Some numerical results:

Taking c to be the proportion of correct guesses when the stakes are normal, and d to be the proportion when the stakes are doubled, and letting

Ent(x) = - x log (x) - (1 - x) log (1 - x) + (1 - x) log (3)

the same reasoning as the original case gives:

Ent(c) + Ent(d) >= 2 log (2)

Maximizing c + 2d based on that constraint yields:

c = 0.659858
d = 0.918634
c + 2d = 2.497127

which gives an expected payoff of 0.997127.

The question is how to come up with a strategy which gives those values of c and d.

Title: Re: hidden signaling II
Post by amia on Jun 5^th, 2005, 3:57am

on 06/05/05 at 02:28:31, Deedlit wrote:

I am a little rusty on Entropy calculations so I didn't fully followed your argument. However, the end result of your calculation did not seem correct.
If c is the probability of succesful bet and d of double bet, isn't the expected payoff at
c = 0.659858
d = 0.918634
should be $1.2456 per flip?

I will try to figure out how to reach these numbers (or something close).

Can you also tell the biased coin theoretic limit from similar equation?

Title: Re: hidden signaling II
Post by Deedlit on Jun 5^th, 2005, 2:16pm

on 06/05/05 at 03:57:41, amia wrote:

When the stakes are normal, the average payoff is 2 * 0.659858 - 1 = 0.319716. When the stakes are doubled the average payoff is 2 * ( 2 * .918634 - 1 ) = 1.67536. So the average payoff is (0.319716 + 1.67536) / 2 = 0.997127.

The argument is similar to the argument from the paper. Let A_i, B_i, C_i be the ith flip / guess of A, B, and C, respectively. Let F_i be the sigma-algebra generated by A_t, B_t, C_t for t <= i. Let h (A | B) be the entropy of random variable A, given knowledge of B. Let p₀₀, p₀₁, p₁₀, p₁₁ be the probabilities for whether B or C guess the ith flip correctly (for example, p₀₁ is the probability that B guesses incorrectly, and C guesses correctly.). Then,

h (A_i, B_i, C_i | F _i-1) = - p₀₀ log p₀₀ - p₀₁ log p₀₁ - p₁₀ log p₁₀ - p₁₁ log p₁₁.

Since the function f(x) = - x log x is concave, we can use Jensen's inequality ( f of the average of the x_i is greater than or equal to the average of the f(x_i) ) on the first three random variables, and get

h (A_i, B_i, C_i| F_i-1) = h (A_i, B_i | F_i-1) <= 3 ( - [(1 - p₁₁) / 3] log [(1 - p₁₁) / 3] ) - p₁₁ log p₁₁
= - (1 - p₁₁) log (1 - p₁₁) - p₁₁ log p₁₁ + (1 - p₁₁) log 3
= Ent (p₁₁).

Taking the expected value over all possible F_i-1, we get

h (A_i, B_i| A₁, B₁, ..., A_i-1, B_i-1) <= E_A (Ent (p₁₁) )

and summing over all t from 1 to i gives

h (A₁, B₁, A₂, B₂, ... A_i, B_i) <= Sum _t=1ⁱ E_A(Ent (p₁₁^t)),

where now p₁₁^t is the probability of B and C both being right at time t, and the expectation is taken over the probability distribution for A's coin flips. Since the B_i depend on the full sequence A_i,

h(A₁, A₂, ..., A_n) = h (A₁, B₁, A₂, B₂, ... A_n, B_n) <= Sum _t=1ⁿ E_A (Ent (p₁₁^t)).

Let C be the set of times in which there are single stakes, and D be the set of times in which there are double stakes. Then

h(A₁, A₂, ..., A_n) <= Sum_{t in C} E_A (Ent (p₁₁^t)) + Sum _{t in D}E_A (Ent (p₁₁^t))
= n/2 [ (2/n) Sum _{t in C} E_A (Ent (p₁₁^t)) + (2/n) Sum _{t in D} E_A (Ent (p₁₁^t)) ]
Applying Jensen's inequality twice to Ent, we get

h(A₁, A₂, ..., A_n) <= n/2 [ (2/n) Sum_{t in C}Ent ( E_A (p₁₁^t)) + (2/n) Sum _{t in D}Ent (E_A (p₁₁^t)) ]
<= n/2 [Ent ((2/n) Sum _{t in C}(E_A (p₁₁^t)) ) + Ent ((2/n) Sum _{t in D} (E_A(p₁₁^t)) )

and the above averages we previously defined as c and d, respectively. So,

h(A₁, A₂, ..., A_n) <= n/2 (Ent (c) + Ent (d) )

and the average per flip is [Ent (c) + Ent (d)] / 2.

Title: Re: hidden signaling II
Post by Deedlit on Jun 5^th, 2005, 3:09pm

It turns out that finding a strategy that gets arbitrarily close to the above is straightforward.

First, let's make a modificaton to SMQ's strategy that will have a little more generality. (There may be a way to do this that is closer to SMQ's strategy, but I haven't really thought about it.) We let n be the number of coin flips and d be the size of a block. Instead of requiring that C's misses occur at a particular subset of block i, we instead assume that C's misses occur arbitrarily, but are limited to the same number (if we want B and C to guess correctly with proportion p, then C should miss no more than about (2/3) (1-p) d guesses.) This reduces the number of messages we can send; setting x = [(1/3)(1-p) d], then SMQ's strategy allows for d! / [(x!)³ (d - 3x)! ] messages, whereas we now have only C(d - 2x, x) C (2x, x) = [(2x)! (d - 2x)!] / [(x!)³ (d - 3x)! ] messages to send. So we've lost a factor of C(d, 2x). So, we cannot instruct C to guess any sequence of guesses we want on the next block; we must choose a subset of proportion 1 / C(d, 2x). It is possible to choose such a subset such that every sequence of coin flips differs in at most about 2x places from some element of the subset. Since this was all we needed, the strategy works, and no reverse construction is required.

The advantage of this modification is that we can accomodate different probability distributions.

Now, for that double stake strategy; since we get to choose, let's have the stakes be single during the first half of the coin flips, and double during the second half. We use the above construction, with p = 0.659858 for the first half, and p = 0.918634 for the second. In the first half, we have more messages at our disposal then we need; we use this extra information to specify C's strategy farther and farther ahead, until eventually we start specifying C's strategy for the second half as well. Once the second half starts, we start losing information, until we lose our entire gain by the end of the sequence.

Put another way, C's instructions for the first half requires y bits per block, while B's messages can give y + x bits per block. In the second half, C's instructions require z + x bits per block, while B's messages can give out z bits per block. Putting all the message bits in a string, we get

y x y x y x ... y x c c c ... c

and the instruction bits form

y y y ... y c x c x c x ... c

B simply lengthens the string as it goes, and C picks up bits to retrieve its instructions. Our values were chosen so that B has just enough in total to give out all of C's instructions.

Note that, even if the double stakes times were chosen at random, rather than by choice, we could achieve the same result in the limit. The reason is the same as we talked about in the other thread; the largest deficit of information ever reached is of order the square root of n, so that loss goes away as n goes to infinity.

Another interesting question is: what if C gets to choose, during the game, when the stakes are to be doubled? I believe the answer is still the same, but I'll have to think about it.

Title: Re: hidden signaling II
Post by amia on Jun 8^th, 2005, 12:23am

Deedlit: Thanks for the detailed explaination :)