There are $n$ islands in the ocean. Each island is linked by a single bridge between each and every unique pair of islands to ensure no island is isolated from the others. The probability of each bridge collapsed independently by earthquake is $p$. Suppose there is an earthquake causing some bridges to collapse - what is the probability of the remaining bridges are able to be traversed to each and every island?

I think we have $(n-1)+(n-2)+(n-3)+...+1=\frac{n(n-1)}{2}$ bridges and the remaining bridges in order to be able to be traversed to each and every island are at least $(n-1)$ bridges, so we have binomial probability and the probability of the event $(X)$ is $$P(X \ge n-1)=1-\sum_{k=0}^{n-2}\binom{\frac{n(n-1)}{2}}{k}p^k(1-p)^{\frac{n(n-1)}{2}-k}$$ Is my approach correct?

  • $\begingroup$ That's not right. It's not enough that at least $(n-1)$ bridges survive $-$ they have to be the right bridges. I would be surprised if there was a simple formula for this. $\endgroup$ – TonyK Aug 24 '14 at 9:46
  • $\begingroup$ @TonyK You are right. Now the problem becomes complicated $\endgroup$ – Venus Aug 24 '14 at 9:51
  • $\begingroup$ See math.stackexchange.com/questions/584228/… $\endgroup$ – Henry Mar 31 at 10:42

Is my approach correct?

No, first because your $X$ seems to be both an event and a random variable (make up your choice), second because the fact that there remains at least $n-1$ bridges is necessary but not sufficient for every island to be connected to the others: with four islands called 1, 2, 3 and 4, the three bridges 1-2, 2-3 and 1-3 leave island 4 isolated.

  • $\begingroup$ But we still can go to island 4 using route 1-2-3-4, can't we? $\endgroup$ – Venus Aug 24 '14 at 9:55
  • $\begingroup$ @Venus: Yes -- bad example, Did! But the three bridges 1-2, 2-3, and 1-3 leave 4 isolated. $\endgroup$ – TonyK Aug 24 '14 at 9:57
  • $\begingroup$ @TonyK You're right but how we determine the right bridges are still exist? $\endgroup$ – Venus Aug 24 '14 at 9:59
  • $\begingroup$ Yes, bridges 1-2, 2-3 and 1-3. Sorry about the typo. $\endgroup$ – Did Aug 24 '14 at 10:20
  • $\begingroup$ @Did Could you please take a look to my edited question? I really hope you can help me with this one. Thanks. $\endgroup$ – Venus Aug 24 '14 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.