A communication network is made of nodes conected with wire. The net sends packets in such a way that if one packet is located in an internal node $x$ (internal node is the one connected to more than one node), it chooses randomly the output node. The probability of going out through the node $y$ connected to $x$ is equal to $p_{xy}$, such that $\sum_{y} p_{xy}=1$. When the packet reaches an external node $X$, it remains there. $p_X$ denotes the probability of going to an external node, when we are connected to it.

We are thinking about calculating the probability $P(xX)$. That's to say, the probability that being the packet in an internal node $x$ it finishes in the external node $X$.

Solve the problem for a triangular net with nodes $a$,$b$,$c$ conected to the external nodes $A$,$B$,$C$,respectively. Solve it using linear equations that verify the different probabilities $P(xY)$.

If I want to the calculate probability $P(aA)$, I think that I have to solve a linear equation system with $P(aA)$, $P(bA)$ and $P(cA)$.

$P(aA)= P_A +P_A P_{ac}P_{ca} + P_A P_{ab}P_{ba} $. I don't know if I have to add the probabilites $P_A P_{ac}P_{cb}P_{ba}$ and $P_A P_{ab}P_{bc}P_{ca}$. Also if the packet goes from $a$ to $c$, instead of returning to $a$, $(P_{ac}P_{ca})$, it could go from $c$ to $C$.


HINT (in case this is homework)

To answer your last question directly, yes you have to consider all complicated possibilities, like $abcbcbcbabacbaA$ etc. That's why that is not the way to go.

Instead, the key is to formulate this as a system of simultaneous equations. E.g. one of those equations is:

$$P(aA) = P_A + P_{ab} P(bA) + P_{ac} P(cA)$$

Why? Because from $a$, either you go to $A$ and win, or you go to $b$ in which case you now have prob $P(bA)$ of winning, or you go to $c$ and now have prob $P(cA)$ of winning. There are $3$ unknowns, $P(aA), P(bA), P(cA)$ and you need to find $3$ equations (one of them given above) and then solve. That accounts for $P(xA)$. Similarly you need other equation-systems for $P(xB)$ and $P(xC)$.

Can you finish from here?


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.