A Message from Deep Space

Our thanks for this puzzle to its author - Clive Fraser!

A satellite launched from earth many years ago is now heading out of the solar system into deep space. The satellite continues to send regular messages back to earth but the strength of the received signal is now getting very weak. To increase the chances of receiving the message correctly, the satellite transmits the same message 3 times. The message is a series of binary digits. The weak signal, combined with several sources of background interference, results in the 3 versions of the message being significantly different.

To further increase the possibility of determining the correct message, the message can be picked up simultaneously by several different tracking stations around the world. The location of these tracking stations, with respect to the direction of the satellite, has a determining effect on the accuracy with which a message can be received. However, using a larger number of tracking stations increases the ability to obtain an accurate message, by combining the results of all stations. Each tracking station is able to determine, from various measurements, the probability that it will detect an incoming binary digit correctly.

Suppose that we have 4 tracking stations, with the following probabilities for correct detection of a single binary digit. 0.647, 0.683, 0.732 and 0.747. With just the fourth tracking station we can be confident that each bit in a single message has a probability of 0.747 of being correct. However, the station receives each bit on 3 separate occasions. We can use all three of these to specify the value of the bit with a greater probability that it is correct. Using the results from the other tracking stations as well will further increase the probability that the specified bit is correct.

If we consider one particular bit in the message, each tracking station receives 3 versions of that bit. There are 4 tracking stations so we have a total of 12 versions of this bit, together with the associated probabilities that the bit has been received correctly. Since each version of the bit must be either 0 or 1, we have 2^12 = 4096 different possible sets of the 12 bits. Although all of these are possible they are not equally likely. A computer program takes the set of 12 received versions of the bit, together with the associated probabilities and is able to determine the most likely value for the bit that was actually transmitted. In the rare event that the computer determines that 0 and 1 are equally likely, one of these is chosen at random.

So we have a system where the computer uses all of the available data to construct the original message, bit by bit. Even though this is likely to be significantly more accurate than any of the individual received messages, there is no reason to suppose that it will be error free. Clearly we would like to know the probability that a bit in the computer generated message is correct. This is what you are asked to do for this question. In the example above, it can be shown that the bits in the computer generated message will have a probability of 0.935462430 (rounded to 9 decimal places) of being correct. This is considerably better than that of the best of the 4 receiving stations described above.

The example given above is deliberately small. In the actual problem there will be 17 receiving stations, in order to give a high probability of bits in the generated message being correct.

Input/Output description: The first line of the input data will contain a single integer N for the number of receiving stations. The second and final line of the input contains N space-separated probability values, associated with each of the N stations. Find the probability that a binary digit in the final generated message is correct. Give this answer rounded to 9 decimal places.

Example:

input:
4
0.647 0.683 0.732 0.747

answer:
0.935462430