Author |
Topic: hidden signaling (Read 2971 times) |
|
amia
Newbie
Posts: 19
|
 |
hidden signaling
« on: May 9th, 2005, 1:02am » |
 Quote  Modify
|
3 friends play a game. Abe tosses a coin many times and writes down the results (head/tail). Berry receives this paper but Carry can not see it. Each round Berry and Carry write down their bet for the next coin toss and hand it to him. He opens the envelopes and reads them out out loud and say if they are correct. If both guesses were correct they win otherwise they lose. Naturally Berry knows the "expected" results but has no means to send this information to Carry other than through his guesses which are read out loud. What is the best strategy that they can devise and what their probability of success?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: hidden signaling
« Reply #1 on: May 9th, 2005, 7:20am » |
Quote Modify
|
It's easy enough to get half right. For every two results Berry says the second one twice, so Carry knows the second one, and can guess for the first. (Which for a fair coin should give about 75% 62.5% even).
I suspect they may do better though.
|
| « Last Edit: May 9th, 2005, 10:00am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: hidden signaling
« Reply #2 on: May 9th, 2005, 7:58am » |
Quote Modify
|
on May 9th, 2005, 7:20am, towr wrote:It's easy enough to get half right. For every two results Berry says the second one twice, so Carry knows the second one, and can guess for the first. (Which for a fair coin should give about 75% even).
I suspect they may do better though. |
|
I make it 62.5% on a fair coin with that strategy - odd flips are only possible to score on if they match the following flip (B only "guesses" right if the two coins match, and C only guesses right by chance)
The following gives the same expected score:
The first "guess" by B in each group of 4 is the majority symbol of the following triplet. You are then guaranteed 2 of the 4, and the other two each come in 1 time in 4 independently. However, it's possible to improve the odds by having B use the known loss occuring in 3 of 4 triplets to signal for the following triplet, only having to use an extra toss for signalling the next triplet one time in 4 - meaning that over 4 triplets, you use 13 tosses and get 9 sure-fire wins, 3 sure fire losses and 1 25% chance, making 9.25/13=37/52 or about 71%
|
|
IP Logged |
|
|
|
amia
Newbie
Posts: 19
|
|
Re: hidden signaling
« Reply #3 on: May 9th, 2005, 9:27pm » |
Quote Modify
|
Hint: Nice job so far but you can do better than those two strategies.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling
« Reply #4 on: May 9th, 2005, 9:38pm » |
Quote Modify
|
Nice algorithm! I originally suspected that there was some sort of entropic argument that would prevent A from disseminating more information than he was giving up with wrong guesses, and so the maximum average number of correct guesses would never be more than 1.5n (which would mean the answer couldn't be more than 75%). But it looks like rmsgrey's algorithm yeilds an average of 20.5n/13 = 1.577n correct guesses! So that theory goes out the window. But it seems like this should be a rather fundamental problem in information theory.
I was thinking about an algorithm where A's first guess would indicate the (n/2+1)st and (n/2+2)nd coin flip if they were the same, otherwise it would indicate the second coin flip. But calculating the expected value looks tricky.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: hidden signaling
« Reply #5 on: May 10th, 2005, 1:10am » |
Quote Modify
|
I have a slight improvement on rsgrey's idea.
Instead of always using the first flip to signal the majority, they could agree that by default they vote H. If indeed the next result is H, they take the point and restart. Only when Berry knows the flip will be F, he uses his vote to signal the majority for the next 3 flips. This brings the success rate to 10/14, or 71.41% (instead of rmsgrey's 71.15%).
One simplification I thought of is that when a majority of X has been signalled, followed by 2 X's, the 3rd flip is just a wild guess. So they might as well get back to the "initial flip" state. Funnily, it doesn't change anything after my improvement, and even degrades rmsgrey's version.
By the way, I also have the feeling 75% could be reached. 50% is chance, the remaining 50% being split into 25% signalling and 25% using the signal.
|
| « Last Edit: May 10th, 2005, 1:13am by Grimbal » |
IP Logged |
|
|
|
amia
Newbie
Posts: 19
|
|
Re: hidden signaling
« Reply #6 on: May 10th, 2005, 1:52am » |
Quote Modify
|
Nice progress, I reached 74% but the teortical limit is roughly 83% (the problem is how to reach it). I was told that it is achievable to reach 75% and 80%. If you will ask, I will post my solution to 0.74 but I want to give it some time first.
|
|
IP Logged |
|
|
|
asterex
Guest
|
One tweak, if the list is long enough, would be to have A analyze the entire list before they start. Instead of signalling that T means you guess TTT and H means you guess HHH, you would choose whichever two triplets occur most frequently. So T may mean guess TTH and H means HHT.
A would then use his first three guesses to tell B which pattern to follow.
Then there is the option of deliberately guessing wrong even though you know B is going to guess right, when losing one point here will gain more points. For example, in my previous strategy, A could look for subsections that have predominately one pattern. And whenever he deliberately misguesses, it means we're starting over and my next 3 guesses will give you the predominant pattern. (Or it means switch to the next pair of patterns in sequence; TTH/HHT switches to THT/HTH. A second misguess would switch to THH/HTT or TTT/HHH...)
Strategies where you analyze the whole list or alter your strategy midstream, will probably be best, but the probabilities can only be determined by a monte carlo simulation, which I don't have time to do
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling
« Reply #8 on: May 10th, 2005, 5:55pm » |
Quote Modify
|
It looks like the strategy the I was talking about has an upper bound of 70%, so no improvement there.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling
« Reply #9 on: May 10th, 2005, 11:48pm » |
Quote Modify
|
I believe this is an upper bound of about 89%:
The entropy of the guesses that A gives, plus the entropy of the deviation of B's guesses from the correct answer, must be at least the entropy of the actual string, which is n log 2. If A deviates from the correct answer with average proportion c, then the entropy of A's guesses is -nc log c - (1 - c) log (1 - c). Similarly, the entropy of the deviation of B's guesses is -nd log d - (1 - d) log (1 - d), where d is the average proportion of B's deviation. So we have
nc log c - (1 - c) log (1 - c) + -nd log d - (1 - d) log (1 - d) >= n log 2.
Since the overlap cannot be greater than min (c,d), we get an upper bound by setting c = d. That yields .1100279 < 1 - c < .8899721
I would be very impressed to see an 80% solution! Right now it is looking impossible.
|
| « Last Edit: May 10th, 2005, 11:52pm by Deedlit » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: hidden signaling
« Reply #10 on: May 11th, 2005, 1:14am » |
Quote Modify
|
This interesting problem reminded me about Guessing Cards Suit problem. Of course, there are essential differences, but probably some ideas may be used here as well...
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: hidden signaling
« Reply #11 on: May 12th, 2005, 8:32am » |
Quote Modify
|
I think I have a strategy which achieves >80% for long sequences! The key realization was that B can signal one of three states with a miss, not just two: B misses, C misses, or both miss.
For instance, assuming both B and C already know C's next three guesses, B can use this to code the following three guesses in the current three guesses, with at most one miss, as follows (let X indicate a correct guess; A, B and C indicate the odd man out on a miss):
XXX = HHH
AXX = HHT
BXX = HTH
CXX = HTT
XAX = THH
XBX = THT
XCX = TTH
XXA = TTT
That would even still leave codes XXB and XXC free for some sort of meta-signaling. This code, which I'll designate [1,3] (misses at most 1 guess signaling 3) gets 70.83% percent correct after the first three guesses. (2 of 3 7/8 of the time + 3 of 3 1/8 of the time.)
So, for eaxmple, if A's sequence were HTHHHTTTH, B could use the following strategy:
1) Break the sequence into groups of three; HTH HHT TTH
2) Working backwards from the end of the sequence, the final group is TTH, which is coded as XCX so B wants C to be wrong for the second guess of the previous group. So B needs C to guess HTT for the second-to-last group, which is coded CXX, and so on. B needs to feed C a correct guess for codes X and B, and an incorrect guess for codes A and C.
3) Use the first group to directly signal the second group. On average they will get 1/4 of these correct through pure chance.
So in our example, B would first "guess" HTT, feeding the next group to C. In the next group, B "guesses" HHT, generating the pattern XCX, which codes TTH for C's next group. Finally B "guesses" TTH, getting the last group entirely correct.
For greater accuracy, the scheme can be arbitrarily extended by allowing more misses in each group, for example a [2,8] coding could look like
XXXXXXXX = HHHHHHHH
AXXXXXXX = HHHHHHHT
BXXXXXXX = HHHHHHTH
CXXXXXXX = HHHHHHTT
XAXXXXXX = HHHHHTHH
...
XXXXXXXC = HHHHTTHH
AAXXXXXX = HHHHTTHT
ABXXXXXX = HHHHTTTH
ACXXXXXX = HHHHTTTT
BAXXXXXX = HHHTHHHH
...
AXAXXXXX = HHHTHTTH
...
XXXXXBCX = TTTTTTTT
This coding is 76.27% correct with 92% of the codes used. A [20,101] coding is 80.28% correct with 99.9991% of the codes used.
I haven't yet calculated the limit of the efficiency of this method, but through quick experimentation it's somewhere upwards of 80.5%
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling
« Reply #12 on: May 12th, 2005, 9:11am » |
Quote Modify
|
Beautiful! In the limit we get the answer from
- x log x - (1-x) log (1-x) + (1-x) log 3 = log 2.
Solving this gives x = 0.81071. However, it's not obvious to me that this is an actual maximum, so it's worth checking as many cases as you can!
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: hidden signaling
« Reply #13 on: May 12th, 2005, 11:53am » |
Quote Modify
|
A minor tweek: we can do slightly better by using the "unused" codes to signal longer sequences when they occur and taking the extra correct guess, e.g. for [1,3] code
...
XCX = TTHH
XXA = TTHT
XXB = TTTH
XXC = TTTT
which gives you a "free" correct guess 1/4 of the time for an overall probablilty of 72.92%
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
asterex
Guest
|
How would that work, since you have to code backwards? If I understand the method correctly, that will change all subsequent triplets, which would change what code you're supposed to use here in the first place.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: hidden signaling
« Reply #15 on: May 12th, 2005, 1:40pm » |
Quote Modify
|
Hmm, forgot about that backwards part.  I think if you let it add the symbol *before* the group instead of after, then it works; e.g.
XCX = HTTH
XXA = TTTH
XXB = HTTT
XXC = TTTT
A = THTHHHTTTH
B splits the last group, sees TTH, notices that's one of our special ones so looks back one more for TTTH, code as XXA so previous group (HHH) needs HHT.
A = THT HHH TTTH
B = HHT HHT TTTH
Going along, C guesses nnn, receives HHT; guesses HHT, receives XXA = TTTH; guesses TTTH.
A = THT HHH TTTH
B = HHT HHT TTTH
C = nnn HHT TTTH
S = *** XXA *XXX
If the sequence were longer, the next sequence would be coded in the last three of the four.
I think that works. 
--SMQ
Edit: fixed smiley problems
|
| « Last Edit: May 12th, 2005, 1:47pm by SMQ » |
IP Logged |
--SMQ
|
|
|
asterex
Guest
|
There's still the problem that, by changing the number of letters in each group, you might reach the beginning of the series and have 1 or 2 letters left over, not enough for a triplet. Not insurmountable, but wasting guesses at the beginning to make sure everyone is on the same track could also waste what little improvement in efficiency you've gained, unless the sequence is very long. (The same problem could come up in the original solution, but in that case you could pad the end with ghost flips to get a number divisible by 3. It's a little harder to pad the beginning).
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: hidden signaling
« Reply #17 on: May 12th, 2005, 3:06pm » |
Quote Modify
|
While it does cost a little in initial efficiency, it's not that much; in the case of our example, at most 3 flips; that will pay off if the sequence is longer than about 50 (one in four tripplets--12 flips--gains a fourth, three of those make up for the padding). That's not so awful to gain >2% efficiency in the long run.
Also, B could try recoding the sequence starting 1 or 2 from the end to see if those come out even. I think for larger groups than 3 B is "likely" to be able to choose the endpoint of the coding so as to keep the initial padding to just a few flips--probably worth it.
Deedit: [400,2105] is 81.0047% and growing very slowly, so I suspect your upper bound is accurate.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: hidden signaling
« Reply #18 on: May 12th, 2005, 7:12pm » |
Quote Modify
|
Since the problem statement specifies "many" coin flips, I've been assuming throughout that it's enough that any constant errors caused by missing a finite chunk once are negligible - only misses in the repeating portion count.
It's worth noting in passing that the current solution lacks an explicit "synching" mechanism to make sure the two guessers are counting form the same flip...
A simple one would be to start with a string of guesses of T followed by a single H, then start the coding - on average you get 50% of the T's - absolute worst case you use an entire cycle length of padding (when the signals could have started with the sequence if you weren't signalling a start)
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling
« Reply #19 on: May 12th, 2005, 7:31pm » |
Quote Modify
|
It's probably better for B to only encode longer sections a multiple of y times. This will generally lead to one extra section, giving about x ~ .2y extra misses. An inital offset will be of average length y/2, and with the strategy presented they will miss 75% of them, so that's an extra .375y on average.
Actually, I just realized that B can choose how many extra-long segments he wants to code, and when, after looking at the full sequence. C should have a deterministic strategy, so B will know in advance exactly how many correct answers any strategy will give. In general, if the initial offset is longer than about 4/15 y, then B is better off coding fewer extra-long segments to make the initial offset 1.
|
|
IP Logged |
|
|
|
asterex
Guest
|
Of course, if "many" means millions of flips, then you're better off using one of the longer, more efficient codes like [400,2105]. If our goal is maximum efficiency, then the only reason to use triplets is because the total sequence is too short to use a longer sequence. I don't know how long the sequence needs to be before [2.8] surpasses [1.3], but it might be before the synching problem has become moot.
|
|
IP Logged |
|
|
|
asterex
Guest
|
My own idea, by the way, on how to use the metasignals in shorter sequences was to keep everything in triplets, but increase the number of times you get to program XXX. You could say that XXX can either mean HHH or HHT or HTH. When you're encoding, if you come to an HHT or HTH, you try encoding it as XXX, and see if you come to an XXA before you hit an XXX. If so, then you encode that XXA as XXB or XXC. If not, you go back and encode the HHT or HTH normally.
When decoding, you treat all XXX as HHH, unless you get an XXB or XXC first.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling
« Reply #22 on: May 14th, 2005, 12:31am » |
Quote Modify
|
on May 13th, 2005, 5:30am, asterex wrote:Of course, if "many" means millions of flips, then you're better off using one of the longer, more efficient codes like [400,2105]. If our goal is maximum efficiency, then the only reason to use triplets is because the total sequence is too short to use a longer sequence. I don't know how long the sequence needs to be before [2.8] surpasses [1.3], but it might be before the synching problem has become moot.
|
|
SMQ's suggestion actually works for all strategies [x,y], unless a strategy is "perfect", i.e. no extra codes left over, which should be rare in the extreme! So just about all strategies get a small improvement.
|
| « Last Edit: May 14th, 2005, 1:13am by Deedlit » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling
« Reply #23 on: May 14th, 2005, 1:15am » |
Quote Modify
|
on May 12th, 2005, 11:53am, SMQ wrote:A minor tweek: we can do slightly better by using the "unused" codes to signal longer sequences when they occur and taking the extra correct guess, e.g. for [1,3] code
...
XCX = TTHH
XXA = TTHT
XXB = TTTH
XXC = TTTT
which gives you a "free" correct guess 1/4 of the time for an overall probablilty of 72.92%
--SMQ |
|
I'm getting an average of 19/8 correct guesses every 26/8 coin flips, for an average percentage of 73.077%.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling
« Reply #24 on: May 14th, 2005, 1:18am » |
Quote Modify
|
on May 13th, 2005, 6:07am, asterex wrote:My own idea, by the way, on how to use the metasignals in shorter sequences was to keep everything in triplets, but increase the number of times you get to program XXX. You could say that XXX can either mean HHH or HHT or HTH. When you're encoding, if you come to an HHT or HTH, you try encoding it as XXX, and see if you come to an XXA before you hit an XXX. If so, then you encode that XXA as XXB or XXC. If not, you go back and encode the HHT or HTH normally.
When decoding, you treat all XXX as HHH, unless you get an XXB or XXC first. |
|
I assume you want to keep coding up changes in the meaning of XXX; in this case, the average percentage is 35/48 = 72.917%, or a little less than SMQ's improvement.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove