1
$\begingroup$

There are many islands that are connected by one-way bridges, that is, if a bridge connects islands a and b , then you can only use the bridge to go from a to b but you cannot travel back by using the same. If you are on island a , then you select (uniformly and randomly) one of the islands that are directly reachable from a through the one-way bridge and move to that island. You are stuck on an island if you cannot move any further. It is guaranteed that after leaving any island it is not possible to come back to that island.

Find the island that you are most likely to get stuck on

What I have tried: suppose I am going from 3 to 4 then probability of getting stuck on 4 = probability of stucking at 3 /no of ways getting out of 3

if it is correct then what we call the above method like i know about conditional probability . If not then what should be the correct method?

Problem link Island

$\endgroup$
  • $\begingroup$ Are any two islands connected by a bridge? How many islands there are? Do you select uniformly only among the islands where you can move to? $\endgroup$ – user Mar 31 at 8:33
  • $\begingroup$ This is same as suppose there is white bowl and inside that there are three small bowls red,blue,green and inside red there are two small bowls pink and purple(other two has also some bowls) what is the probability of selecting pink? @user $\endgroup$ – aka1234 Mar 31 at 8:47
  • $\begingroup$ This does not seem to answer my questions. Or you just would like to say that this information does not matter? $\endgroup$ – user Mar 31 at 8:55
1
$\begingroup$

There is more than one approach to this question. The following, based on Markov chains, works but may not be the most efficient when you have hundreds of thousands of islands

Taking the example from your link (five islands where you starting at island $1$, and there are bridges from island $1$ to $2,3,4$, from island $2$ to $4,5$, and from island $3$ to $4$), you can find the probability of your island after $n$ moves or attempted moves as

$$\begin{bmatrix} 1& 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} 0 & \frac14 & \frac14 & \frac14 & \frac14 \\ 0 & 0 & 0 & \frac12 & \frac12 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}^n$$

so

  • with $n=0$ you start at island $1$, i.e. $\begin{bmatrix}1& 0 & 0 & 0 & 0\end{bmatrix}$
  • with $n=1$ the distribution of where you may be is $\begin{bmatrix}0 & \frac14 & \frac14 & \frac14 & \frac14\end{bmatrix}$
  • with $n\ge 2$ the distribution of where you may be is $\begin{bmatrix}0 & 0 & 0 & \frac58 & \frac38\end{bmatrix}$

In this example you can conclude that you will get stuck on one of islands $4$ or $5$ after two or fewer moves, with island $4$ being more likely

In general, if given no possibility of returning to an earlier island, then the number of moves until you are stuck must be less than the number of islands, so this is a finite algorithm

$\endgroup$
  • $\begingroup$ why we are taking the probability as 1 for getting stuck at island 1? suppose there will be roads for leaving out the island 1 then in that case it should not be 1, and we can also say that probability 1 means you will always stuck on island 1. $\endgroup$ – aka1234 Mar 31 at 9:01
  • $\begingroup$ And we can also say that we are standing on island and we are taking probability of getting stuck on that island to be 1 then we may never leave that island but in real case it is not true. $\endgroup$ – aka1234 Mar 31 at 9:03
  • $\begingroup$ @aka1234 - $\begin{bmatrix}1& 0 & 0 & 0 & 0\end{bmatrix}$ is the probability distribution when $n=0$, i.e. you start at island $1$. Similarly $\begin{bmatrix}0 & \frac14 & \frac14 & \frac14 & \frac14\end{bmatrix}$ is the probability distribution of your position when $n=1$ after one move or attempted move so is different. Then $\begin{bmatrix}0 & 0 & 0 & \frac58 & \frac38\end{bmatrix}$ is the probability distribution of your position when $n=2$ after two moves or attempted moves and is different again, but does not change when $n=3$ so is the distribution for when you are stuck. $\endgroup$ – Henry Mar 31 at 9:11
  • $\begingroup$ suppose there are five edges 1-2,1-3,1-4 and 2-5,2-6 then probability of getting stuck at 5 is 1/3*1/2 by conditional probability? $\endgroup$ – aka1234 Mar 31 at 9:19
  • $\begingroup$ I want to say that it can it be answered using conditional probability? $\endgroup$ – aka1234 Mar 31 at 9:20

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.