|
||
Title: hidden signaling Post by amia on May 9th, 2005, 1:02am 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? |
||
Title: Re: hidden signaling Post by towr on May 9th, 2005, 7:20am 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 I suspect they may do better though. |
||
Title: Re: hidden signaling Post by rmsgrey on May 9th, 2005, 7:58am on 05/09/05 at 07:20:03, towr wrote:
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% |
||
Title: Re: hidden signaling Post by amia on May 9th, 2005, 9:27pm Hint: Nice job so far but you can do better than those two strategies. |
||
Title: Re: hidden signaling Post by Deedlit on May 9th, 2005, 9:38pm 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. |
||
Title: Re: hidden signaling Post by Grimbal on May 10th, 2005, 1:10am 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. |
||
Title: Re: hidden signaling Post by amia on May 10th, 2005, 1:52am 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. |
||
Title: Re: hidden signaling Post by asterex on May 10th, 2005, 8:30am 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 |
||
Title: Re: hidden signaling Post by Deedlit on May 10th, 2005, 5:55pm It looks like the strategy the I was talking about has an upper bound of 70%, so no improvement there. |
||
Title: Re: hidden signaling Post by Deedlit on May 10th, 2005, 11:48pm 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. |
||
Title: Re: hidden signaling Post by Barukh on May 11th, 2005, 1:14am This interesting problem reminded me about Guessing Cards Suit (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1080993419;start=0#0) problem. Of course, there are essential differences, but probably some ideas may be used here as well... |
||
Title: Re: hidden signaling Post by SMQ on May 12th, 2005, 8:32am I think I have a strategy which achieves >80% for long sequences! The key realization was that [hide]B can signal one of three states with a miss, not just two: B misses, C misses, or both miss.[/hide] 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 |
||
Title: Re: hidden signaling Post by Deedlit on May 12th, 2005, 9:11am 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! |
||
Title: Re: hidden signaling Post by SMQ on May 12th, 2005, 11:53am 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 |
||
Title: Re: hidden signaling Post by asterex on May 12th, 2005, 1:10pm 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. |
||
Title: Re: hidden signaling Post by SMQ on May 12th, 2005, 1:40pm 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 |
||
Title: Re: hidden signaling Post by asterex on May 12th, 2005, 2:18pm 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). |
||
Title: Re: hidden signaling Post by SMQ on May 12th, 2005, 3:06pm 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 |
||
Title: Re: hidden signaling Post by rmsgrey on May 12th, 2005, 7:12pm 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) |
||
Title: Re: hidden signaling Post by Deedlit on May 12th, 2005, 7:31pm 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. |
||
Title: Re: hidden signaling Post by asterex on May 13th, 2005, 5:30am 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. |
||
Title: Re: hidden signaling Post by asterex on May 13th, 2005, 6:07am 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. |
||
Title: Re: hidden signaling Post by Deedlit on May 14th, 2005, 12:31am on 05/13/05 at 05:30:08, asterex wrote:
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. |
||
Title: Re: hidden signaling Post by Deedlit on May 14th, 2005, 1:15am on 05/12/05 at 11:53:25, SMQ wrote:
I'm getting an average of 19/8 correct guesses every 26/8 coin flips, for an average percentage of 73.077%. |
||
Title: Re: hidden signaling Post by Deedlit on May 14th, 2005, 1:18am on 05/13/05 at 06:07:00, asterex wrote:
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. |
||
Title: Re: hidden signaling Post by SMQ on May 14th, 2005, 5:00am on 05/14/05 at 01:15:51, Deedlit wrote:
Hmm, I was looking at the "next" four flips: XXX = 3/3 * 2/16; AXX through XBX = 2/3 * 10/16; XCX to XXC = 3/4 * 4/16 for a total of 35/48 = .7282. Maybe I need to code up a quick monte carlo simulator... :) --SMQ |
||
Title: Re: hidden signaling Post by Deedlit on May 15th, 2005, 7:12pm The problem is that in the first two cases, the fourth flip starts off a new segment, we can't just give it the same expected value as the previous three flips. |
||
Title: Re: hidden signaling Post by SMQ on May 15th, 2005, 7:46pm Yeah, and my monte carlo simulator agrees with your assessment as well. I bow, once again, to the greater experience. But hey, at least I got a cool coin flip simulator out of the deal. ;D --SMQ |
||
Title: Re: hidden signaling Post by amia on May 18th, 2005, 1:43am on 05/12/05 at 15:06:24, SMQ wrote:
Your method tried to get in the last block to 0 mistakes. What if if allowed any of the 0 to 400 errors in the last block and chosen the best combination out of these? Could this increase our chances and if so by how much? |
||
Title: Re: hidden signaling Post by Deedlit on May 18th, 2005, 2:52am This could certainly lead to more correct answers in certain cases, so it would likely generate a higher expected value for a specific n (number of coin flips). But we've been generally been thinking in terms of letting n go to infinity, and in that case you've got finitely many possibilities all converging to the same value (use a central limit theorem), and so the expected maximum will converge to the same value as well. |
||
Title: Re: hidden signaling Post by amia on May 18th, 2005, 4:39am on 05/14/05 at 01:15:51, Deedlit wrote:
I received an even simpler method to get to 0.75 (that does not require coding from the end to beginning): Divide the string into pairs. B bets 00 or 11 on each pair.according to A's instructions. Instructions are given on every 01 or 10 blocks (on the bit which is an error anyway). Each error adds one bit of information. Use only one bit of information after every 00 or 11 pair (even if more is accumulated). The information indicates if to guess 00 or 11. If the pair is 01 or 10 (happens 50% of the time) it does not matter what the guess is. Therefore the information is used in the next 00 or 11 block and no information is "wasted" on the 01 and 10 blocks. It is easy to see that the probability of the hit rate approaches 75% (3/4). 100% on the 00 and 11 pairs and 50% on the 01 and 10 pairs. In order for this solution to reach 3/4 we need a sacrifice to create a small improvement : 01 010101 - insert an error on the "correct" bit to save 3 errors. Probability of this sequence is 1/256. 3 information bits lost. 10 010101 - insert an error on the "correct" bit to save 3 errors. Probability of this sequence is 1/256. 3 information bits lost. 00 000000 - insert an error in the first bit to save 3 information bits. Probability of this sequence is 1/256. 3 information bits gained. 11 111111 - insert an error in the first bit to save 3 information bits. Probability of this sequence is 1/256. 3 information bits gained. 00 111111 - insert an error in the second bit to save 3 information bits. Probability of this sequence is 1/256. 3 information bits gained. 11 010101 - insert an error in the second bit to save 3 errors. Probability of this sequence is 1/256. 3 information bits lost. So in every 256 bits we are gaining additional 9-6=3 bits without loosing any information bits which adds 1.17%. The problem is that I don't see a way to increase it to large blocks and receive higher than 81% |
||
Title: Re: hidden signaling Post by Deedlit on May 18th, 2005, 5:16am Nice. Actually, it looks like the first part already reaches 75%, and the "small improvement" actually decreases the percentage slightly, although I'm not sure I've understood you correctly. |
||
Title: Re: hidden signaling Post by amia on May 18th, 2005, 5:28am on 05/18/05 at 05:16:27, Deedlit wrote:
It increases accuracy since for example 11 010101 in the original scheme had 3 mistakes (in the 3 '01's) and in the second scheme the second bit was damaged by A to flag the '010101' sequence with no errors - therefore 3 errors were replaced by 1 error for these 8 bits. |
||
Title: Re: hidden signaling Post by Deedlit on May 18th, 2005, 5:38am Ah, I see. However, the improvement is not 1.17%; each of the 6 possibilities takes 8 flips, and the other 250 possibilities take 2 flips each, so we improve by 3 answers every 548 flips, for an improvement of .547%. |
||
Title: Re: hidden signaling Post by amia on May 18th, 2005, 10:58pm on 05/18/05 at 05:38:36, Deedlit wrote:
Simulations show that niether 1.17 nor 0.547 is correct. It is actually about 0.87%. I believe that it is due to the fact that existance of '00 11 11 11' for example will decrease the chance of '11 11 11 11' to happen etc. This also changes the info bits ratio slightly to our favour (order of magnitude of 0.01%). I did not understand your rational, though. |
||
Title: Re: hidden signaling Post by rmsgrey on May 19th, 2005, 4:33am I'm a little confused - what happens with the following string? 00 11 00 11 ... More generally, what happens in strings where the number of matching pairs persistently exceeds the number of signalling pairs? |
||
Title: Re: hidden signaling Post by amia on May 19th, 2005, 5:47am on 05/19/05 at 04:33:10, rmsgrey wrote:
Statistically there should be other sequences to balance them out. It may happen that from time to time there would be missing some info bits but this could be solved by sending initial n info-bits and this should not affect statistics if the number of flips is large enough. |
||
Title: Re: hidden signaling Post by rmsgrey on May 20th, 2005, 5:36am on 05/19/05 at 05:47:50, amia wrote:
Statistically, symmetric 1-dimensional random walks spend a large majority of the time on the same side of the start position - so roughly half the time you'd expect to spend most of the time defective in information - by roughly half the square root of the number of flips. |
||
Title: Re: hidden signaling Post by Deedlit on May 21st, 2005, 1:17am on 05/20/05 at 05:36:43, rmsgrey wrote:
The key phrase being "square root of the number of flips." If d is the proportion of 00 or 11 appearances, then the expected number of correct guesses is 1/2 + min (d, 1-d)/2. So we have min (d, 1-d)/2 ~ 1/2 - 1/[2 sqrt(d)], and the expected number of corrected guesses is about 3/4 - 1/[4 sqrt (4)], which goes to 3/4 as d -> infinity. |
||
Title: Re: hidden signaling Post by Deedlit on May 21st, 2005, 2:48am on 05/18/05 at 22:58:15, amia wrote:
Yes, you are absolutely right. Note that even if the six configurations were reduced to one, the relative occurence of the configuration would depend on which one it was; '00 11 11 11' would show up every 512 coin flips, and '11 11 11 11' would show up every 680 coin flips. So the situation is a lot more complicated than I thought. I suspect it is still reasonably solvable, though. |
||
Title: Re: hidden signaling Post by amia on May 21st, 2005, 10:02pm In addition, please note that since the probability of success is larger than 75% we can use these extra sucesses to assure exact 75% success with no missing info bits relatively easily. |
||
Title: Re: hidden signaling Post by Deedlit on May 31st, 2005, 3:50am In your other thread, you indicate that SMQ's solution is actually optimal. Do you have a proof, or heuristic, that this is the case? |
||
Title: Re: hidden signaling Post by amia on May 31st, 2005, 4:09am I found the following paper that proves that any solution that is better than that will break the information constraint: http://ratio.huji.ac.il/dp/neyman/OMPDPmay6.ps |
||
Title: Re: hidden signaling Post by Deedlit on May 31st, 2005, 4:14am Thanks! I'll give it a look-over. |
||
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |