3
$\begingroup$

In this question, we have a person trying to cross the river. However a night before that, there is a storm and each bridge has 50% chance of being struck by lightning strike unconditionally from the previous lightning strike. This would destroy and bridge. What is the probability that there exists a path to cross river? enter image description here

(As you can see in the drawings, we have 13 bridges, some of then cross at one of the 6 junctions)

Firstly I just tried adding all the possibilities together and computing the probability of two vertical bridge move (1/4) and probability of (two vertical and one horizontal - 3/8) in the end both of these computations were wrong because the issue here is that there is a lot of overlapping, i.e. if there is 2+ routes, this overlapping event made me confused and stuck and any progress I made, or any pattern I tried to spot came back to the questions how do I get all the possibilities without actually writing all of them down. Thanks for any help

$\endgroup$

1 Answer 1

6
$\begingroup$

This is a problem about crossing probability from percolation theory in disguise.

The idea is that you can consider a "dual graph" of the original graph representing the bridge that is obtained by rotating each segment by $90^{\circ}$ degrees about its center:

dual graph

If we call paths in the dual graph as simply dual paths, then a moment of though reveals that:

$$ \left\{\begin{gathered} \exists\text{ a path of unstruck segments} \\ \text{from top to bottom} \end{gathered}\right\} \qquad\iff\qquad \left\{\begin{gathered} \not\exists\text{ a }\textbf{dual}\text{ path of struck segments} \\ \text{from left to right} \end{gathered}\right\} $$

Indeed, any dual path of struck segments from left to right will separate the top from the bottom in the original graph, whereas any path of unstruck segments from top to bottom will prevent such left-to-right dual path from occurring.

Moreover, the dual graph is nothing but a $90^{\circ}$-rotation of the original graph, and each segment is struck by a lightning or not with equal probabilities. So, if $H$ denotes the event that there exists a path to cross the river, then

\begin{align*} \mathbf{P}(H) &= \mathbf{P}\left(\begin{gathered} \exists\text{ a path of unstruck segments} \\ \text{from top to bottom} \end{gathered}\right) \\ &= \mathbf{P}\left(\begin{gathered} \exists\text{ a dual path of struck segments} \\ \text{from left to right} \end{gathered}\right) \\ &= 1 - \mathbf{P}\left(\begin{gathered} \not\exists\text{ a dual path of struck segments} \\ \text{from left to right} \end{gathered}\right) \\ &= 1 - \mathbf{P}(H) \end{align*}

and therefore $\mathbf{P}(H) = \frac{1}{2}$.

$\endgroup$
6
  • $\begingroup$ @sangchl Lee, thanks a lot, Im starting to get is slowly, I'm kinda confused with the terminology - what exactly are struck and unstruck segments? Thanks $\endgroup$
    – Sam333
    Jul 5 at 13:43
  • $\begingroup$ @Sam333, struck segments are those segment which are struck by lightning, and likewise for unstruck segments. :) $\endgroup$ Jul 5 at 18:22
  • $\begingroup$ thanks a lot! Last question just to clarify, I understand everything except the 2nd row in the P(h) bit. In the first paragraph, we have established that there is a path from top to bottom if there isnt a path of struck segments from left to right (if we rotate every bridge 90 degrees left). But then in line 3 we actually say that P(h) is 1 - that probability. And instead, here the probability of path depends on the existence of dual path and not not existence of dual path (which we said in the first paragraph). Hopefully you understand what I mean $\endgroup$
    – Sam333
    Jul 5 at 21:35
  • $\begingroup$ basically I feel like we have established (H) <=> (A) and then said P(H) = P(B) where B is exact opposite of A so then P(H) = 1 - P(A) . .. isn't that kinda contradiction? $\endgroup$
    – Sam333
    Jul 5 at 21:37
  • $\begingroup$ @Sam333, the second equality of the last formula holds because we can interchange 'struck segments' and 'unstruck segments' without changing the probabilities. It is quite analogous to the following toy example: Toss a fair coin 5 times. Then $$\mathbf{P}(\text{exactly 3 coins land on heads})=\mathbf{P}(\text{exactly 3 coins land on tails})$$ even though the events themselves are not the same. $\endgroup$ Jul 5 at 21:54

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.