You are on the North Shore of a river, and you want to get to the South Shore. In the river are 6 islands and 13 bridges connecting the islands and shores. However, a storm gives a 50% chance to each bridge to collapse before you cross (independent of each other).
Some bridges are now collapsed (or they could be all intact or all collapsed). What is the probability that you will be able to make it over the river?
From FiveThirtyEight.
The answer is
exactly 50%.
To see this,
Suppose in a parallel universe, someone wants to cross from the West Shore to the East Shore at the same you're trying to cross from North to South:
Instead of saying the bridges are destroyed, we'll say that for each bridge, either the orange bridge or the green bridge that crosses it are built. This doesn't change the probability that the North-South crossing is possible.
In this situation, clearly exactly one of you or your imaginary friend will be able to cross -- if a West-East crossing is impossible, this means West and East are separated by a path that goes from North to South, and vice-versa. Because the situation is completely symmetric, the chance that you will be the one to cross, and not the one in the parallel universe, is 50%.
There is of course, a brute force way to answer this problem if, as @glugglug asked, the probability of a bridge breaking is not 0.5.
First, what's the probability of the three eastmost bridges all still standing? This gives us a path from North to South using only three bridges. Well, if the probability of a bridge still standing is p (in our case, p=0.5), the probability of all three of those bridges standing is p^3 (in this specific case, 0.125).
If those bridges are up, great, we will take those, but in the remaining 0.875 cases (1-p^3), what are the chances that the three center bridges are standing? Again, that's p^3, but it's p^3 out of the remaining 1-p^3 cases, not out of 1, because we wouldn't be looking at the center bridges if we had already found a way across on the eastmost ones. So, the chances of either being able to cross the eastmost briges or the center bridges are (p^3) + (p^3) * (1 - p^3).
Or, more generally, (probability of all the previous routes) + (probability of current route)*(1 - probability of all the previous routes).
For the westmost bridges, we would do the same thing, the probability of those three bridges standing is p^3, the total probability of a route using only three bridges existing is
[(p^3) + (p^3) * (1 - p^3)] + (p^3) * [(p^3) + (p^3)*(1 - p^3)].
You have to continue summing these up until you have accounted for all possible routes, I believe there are 3 that only use 3 bridges (each with probability p^3), 8 that use 4 bridges (p^4), 4 that use 5 bridges (p^5), 4 that use 6 bridges (p^6), and 4 that use 7 bridges (p^7), but I just did that very quickly in my head and may have missed some.
If anyone wants to do all that out by hand with p=0.5 and see if the answer is also 0.5, be my guest, I may do it later if I'm bored enough.
