Puzzle 5

In Nikita's office there are two computers.

The first computer generates a string of 0s and 1s in the following way. The string always starts \(0,0,1\) and after that digits are chosen independently and take value 0 or 1, each with probability \(\frac{1}{2}\). The computer keeps adding extra digits to the end of the sequence until there are two 0s in a row, at which point the computer stops.

The second computer reads the output from the first computer and corrupts it in the following way. The computer reads the sequence from the beginning, and if at any point it sees a 0 followed by a 1 and then another 1, it replaces those digits with 1 followed by 0 and 0. It then starts the process again, reading the sequence from the beginning and replacing any 011 with 100. If at any point there are no occurrences of 011 in the sequence the second computer stops.

For example, the first computer might produce string \[ (0,0,1,0,1,1,0,0) \] which would be acted on by the second computer as \[ (0,0,1,0,1,1,0,0)\to(0,0,1,1,0,0,0,0)\to (0,1,0,0,0,0,0,0) \] which is where the process would terminate.

What is the probability that a random output from the first computer would be turned by the second computer into a string where the third digit is 1?

You might like to use the fact that, for a number r between 0 and 1 and any real number a, the infinite summation \[ a+ar+ar^2+ar^3+ar^4\cdots = \frac{a}{1-r}. \] Write your answer to 3 decimal places, for example if you think the answer is \(\frac{1}{9}\) you should write \(0.111\)