Author |
Topic: hidden signaling (Read 2985 times) |
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 2084
|
 |
Re: hidden signaling
« Reply #25 on: May 14th, 2005, 5:00am » |
 Quote  Modify
|
on May 14th, 2005, 1:15am, Deedlit wrote:I'm getting an average of 19/8 correct guesses every 26/8 coin flips, for an average percentage of 73.077%.
|
|
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
|
|
 IP Logged |
--SMQ
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling
« Reply #26 on: May 15th, 2005, 7:12pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: hidden signaling
« Reply #27 on: May 15th, 2005, 7:46pm » |
Quote Modify
|
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. 
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
amia
Newbie
Posts: 19
|
|
Re: hidden signaling
« Reply #28 on: May 18th, 2005, 1:43am » |
Quote Modify
|
on May 12th, 2005, 3:06pm, SMQ wrote:
Deedit: [400,2105] is 81.0047% and growing very slowly, so I suspect your upper bound is accurate.
--SMQ |
|
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?
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling
« Reply #29 on: May 18th, 2005, 2:52am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
amia
Newbie
Posts: 19
|
|
Re: hidden signaling
« Reply #30 on: May 18th, 2005, 4:39am » |
Quote Modify
|
on May 14th, 2005, 1:15am, Deedlit wrote:
I'm getting an average of 19/8 correct guesses every 26/8 coin flips, for an average percentage of 73.077%.
|
|
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%
|
| « Last Edit: May 18th, 2005, 5:32am by amia » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling
« Reply #31 on: May 18th, 2005, 5:16am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
amia
Newbie
Posts: 19
|
|
Re: hidden signaling
« Reply #32 on: May 18th, 2005, 5:28am » |
Quote Modify
|
on May 18th, 2005, 5:16am, Deedlit wrote:| 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. |
|
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.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling
« Reply #33 on: May 18th, 2005, 5:38am » |
Quote Modify
|
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%.
|
|
IP Logged |
|
|
|
amia
Newbie
Posts: 19
|
|
Re: hidden signaling
« Reply #34 on: May 18th, 2005, 10:58pm » |
Quote Modify
|
on May 18th, 2005, 5:38am, Deedlit wrote:| 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%. |
|
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.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: hidden signaling
« Reply #35 on: May 19th, 2005, 4:33am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
amia
Newbie
Posts: 19
|
|
Re: hidden signaling
« Reply #36 on: May 19th, 2005, 5:47am » |
Quote Modify
|
on May 19th, 2005, 4:33am, rmsgrey wrote: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? |
|
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.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: hidden signaling
« Reply #37 on: May 20th, 2005, 5:36am » |
Quote Modify
|
on May 19th, 2005, 5:47am, amia 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. |
|
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.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling
« Reply #38 on: May 21st, 2005, 1:17am » |
Quote Modify
|
on May 20th, 2005, 5:36am, rmsgrey 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. |
|
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.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling
« Reply #39 on: May 21st, 2005, 2:48am » |
Quote Modify
|
on May 18th, 2005, 10:58pm, amia 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. |
|
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.
|
|
IP Logged |
|
|
|
amia
Newbie
Posts: 19
|
|
Re: hidden signaling
« Reply #40 on: May 21st, 2005, 10:02pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling
« Reply #41 on: May 31st, 2005, 3:50am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: hidden signaling
« Reply #43 on: May 31st, 2005, 4:14am » |
Quote Modify
|
Thanks! I'll give it a look-over.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print