Author |
Topic: hidden signaling II (Read 632 times) |
|
amia
Newbie
Posts: 19
|
 |
hidden signaling II
« on: May 31st, 2005, 1:40am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling II
« Reply #1 on: May 31st, 2005, 3:46am » |
Quote Modify
|
on May 31st, 2005, 1:40am, 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?
|
|
IP Logged |
|
|
|
amia
Newbie
Posts: 19
|
|
Re: hidden signaling II
« Reply #2 on: May 31st, 2005, 4:19am » |
Quote Modify
|
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.
|
| « Last Edit: May 31st, 2005, 4:21am by amia » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling II
« Reply #3 on: Jun 1st, 2005, 10:54pm » |
Quote Modify
|
on May 31st, 2005, 4:19am, 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.
|
| « Last Edit: Jun 1st, 2005, 11:53pm by Deedlit » |
IP Logged |
|
|
|
amia
Newbie
Posts: 19
|
|
Re: hidden signaling II
« Reply #4 on: Jun 2nd, 2005, 1:36am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling II
« Reply #5 on: Jun 2nd, 2005, 6:33pm » |
Quote Modify
|
I've been flip-flopping on that one - I'll see if I can devote some time to this later.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling II
« Reply #6 on: Jun 5th, 2005, 2:28am » |
Quote Modify
|
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.
|
| « Last Edit: Jun 5th, 2005, 2:29am by Deedlit » |
IP Logged |
|
|
|
amia
Newbie
Posts: 19
|
|
Re: hidden signaling II
« Reply #7 on: Jun 5th, 2005, 3:57am » |
Quote Modify
|
on Jun 5th, 2005, 2:28am, Deedlit wrote: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.
|
|
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?
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling II
« Reply #8 on: Jun 5th, 2005, 2:16pm » |
Quote Modify
|
on Jun 5th, 2005, 3:57am, amia 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?
|
|
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 Ai, Bi, Ci be the ith flip / guess of A, B, and C, respectively. Let Fi be the sigma-algebra generated by At, Bt, Ct for t <= i. Let h (A | B) be the entropy of random variable A, given knowledge of B. Let p00, p01, p10, p11 be the probabilities for whether B or C guess the ith flip correctly (for example, p01 is the probability that B guesses incorrectly, and C guesses correctly.). Then,
h (Ai, Bi, Ci | F i-1) = - p00 log p00 - p01 log p01 - p10 log p10 - p11 log p11.
Since the function f(x) = - x log x is concave, we can use Jensen's inequality ( f of the average of the xi is greater than or equal to the average of the f(xi) ) on the first three random variables, and get
h (Ai, Bi, Ci | Fi-1) = h (Ai, Bi | Fi-1) <= 3 ( - [(1 - p11) / 3] log [(1 - p11) / 3] ) - p11 log p11
= - (1 - p11) log (1 - p11) - p11 log p11 + (1 - p11) log 3
= Ent (p11).
Taking the expected value over all possible Fi-1, we get
h (Ai, Bi | A1, B1, ..., Ai-1, Bi-1) <= EA (Ent (p11) )
and summing over all t from 1 to i gives
h (A1, B1, A2, B2, ... Ai, Bi) <= Sum t=1i EA (Ent (p11t)),
where now p11t 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 Bi depend on the full sequence Ai,
h(A1, A2, ..., An) = h (A1, B1, A2, B2, ... An, Bn) <= Sum t=1n EA (Ent (p11t)).
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(A1, A2, ..., An) <= Sum t in C EA (Ent (p11t)) + Sum t in D EA (Ent (p11t))
= n/2 [ (2/n) Sum t in C EA (Ent (p11t)) + (2/n) Sum t in D EA (Ent (p11t)) ]
Applying Jensen's inequality twice to Ent, we get
h(A1, A2, ..., An) <= n/2 [ (2/n) Sum t in C Ent ( EA (p11t)) + (2/n) Sum t in D Ent (EA (p11t)) ]
<= n/2 [Ent ((2/n) Sum t in C (EA (p11t)) ) + Ent ((2/n) Sum t in D (EA(p11t)) )
and the above averages we previously defined as c and d, respectively. So,
h(A1, A2, ..., An) <= n/2 (Ent (c) + Ent (d) )
and the average per flip is [Ent (c) + Ent (d)] / 2.
|
| « Last Edit: Jun 5th, 2005, 3:25pm by Deedlit » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling II
« Reply #9 on: Jun 5th, 2005, 3:09pm » |
Quote Modify
|
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!)3 (d - 3x)! ] messages, whereas we now have only C(d - 2x, x) C (2x, x) = [(2x)! (d - 2x)!] / [(x!)3 (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.
|
|
IP Logged |
|
|
|
amia
Newbie
Posts: 19
|
|
Re: hidden signaling II
« Reply #10 on: Jun 8th, 2005, 12:23am » |
Quote Modify
|
Deedlit: Thanks for the detailed explaination
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print