0
$\begingroup$

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 net with an external node $A$ connected to an internal node $a$, connected to an internal node $b$ connected to an external node $B$.

Note that the only free parameters are $p_A$ and $p_B$.

So if I want to calculate the probability of going to the external node A from node $a$, $P(aA)$, the packet can go to node $b$ then back to node $a$, again back to node $b$... in a complete random way, before going to the external node $A$.

I the packet is in $a$, it has two choises, to go to the external node $A$ or to to go to $b$. Once in $b$ it can only go to $a$. I don't know if this is right, but this probability is equal to $p_A + p_{ab}p_{ba}$ and once in $a$ again, the process can be repeated infinite times.

If the packet is in $a$ it has two choices, to go to the external node $A$ or to to go to $b$. Once in $b$ it can only go to $a$. I don't know if this is right, but this probability is equal to $p_A + p_{ab}p_{ba}$ and once in $a$ again, the process can be repeated infinite times. So $P(aA)= \sum_{1}^{\infty} (p_A + p_{ab}p_{ba})$ ?? But it can also iterate a finite number of times.

$\endgroup$
  • $\begingroup$ You are on right track by saying the probability of going back to itself can be repeated infinitely often, but it is not $p_A + p_{ab}p_{ba}$ as you say, but rather $p_Ap_{ab} p_{ba}$ since multiplication is what we do to combine events. So if we repeat it for another cycle, we multiply another $p_{ab}p_{ba}$ to get $p_A p_{ab}^2 p_{ba}^2$ and another cycle $p_{A}p_{ab}^3 p_{ba}^3$ and so on so that, $P(aA) = \sum_{n=0}^\infty p_A p_{ab}^n p_{ba}^n$ $\endgroup$ – symchdmath Apr 20 at 2:38
0
$\begingroup$

This answer puts the problem into formal terms so that you can hopefully learn more from how I've set up the problem so that you can do it yourself, rather than me giving the solution outright. What we have here is a Markov chain, that is, if we label the nodes $(X_i)_{i \geq 0}$ as the nodes the packet arrives at over its course, with $X_0 = a$. Then the probability of $X_i$ being any particular node depends only on the value of $X_{i-1}$. The transition matrix associated with this matrix is given by,

$$\begin{bmatrix} p_{aa} & p_{aA} & p_{ab} & p_{aB} \\ p_{Aa} & p_{AA} & p_{Ab} & p_{AB} \\ p_{ba} & p_{bA} & p_{bb} & p_{bB} \\ p_{Ba} & p_{BA} & p_{Bb} & p_{BB} \end{bmatrix} = \begin{bmatrix}0 & p_A & 1- p_A & 0 \\ 0 & 1 & 0 & 0 \\ 1-p_{B} & 0 & 0 & p_B \\ 0 & 0 & 0 & 1 \end{bmatrix}$$

We want to know the probability that starting at $X_0 = a$, we obtain $X_n = A$ for some $n$. That is,

$$P(aA) = \mathbb{P} \left(\bigcup_{i=0}^{\infty} \{X_n = A | X_0 = a \} \right) $$

Since the events are disjoint we have,

$$P(aA) = \sum_{i=0}^{\infty} \mathbb{P}(X_n = A | X_0 = a) $$

We can proceed in one of two ways, the less general way to do it is simply to analyse the network we have built and notice that if we set $q_n = \mathbb{P}(X_{n} = a | X_0 = a)$ then if we are at $X_n = a$, to continue the sequence, we can only go to $b$ and then back again, which occurs with probability $(1-p_A)(1-p_B)$ since that is the probability of $a$ going to $b$ and then back to $a$. So that,

$$q_{n+2} = q_{n}(1-p_A)(1-p_B)$$

But we have that,

$$\mathbb{P}(X_n = A | X_0 = a) = p_A \mathbb{P}(X_{n-1} = a | X_0 = a) = p_A q_{n-1}$$

So that we notice, $P(X_n = A | X_0 = a) = 0 $ whenever $n$ is even, and so,

$$P(aA) = p_A + 0 + p_A(1-p_A)(1-p_B) + 0 + p_A(1-p_A)^2(1-p_B)^2 + 0 + \dots $$

That is,

$$P(aA) = p_A (1 + (1-p_A)(1-p_B) + (1-p_A)^2(1-p_B)^2 + \dots) = \frac{p_A}{1 - (1-p_A)(1-p_B)} = \frac{p_A}{p_A + p_B - p_Ap_B}$$

Hope that helps, if you need a simpler explanation, let me know.

$\endgroup$
  • $\begingroup$ No you don't need to, I included that because that would be the start of the proper way to approach this problem. You can choose to ignore the first paragraph except for the definition of $X_i$. If you are comfortable with notation like $P(X_n = A | X_0 = a)$ the rest of the answer should be interpretable for you $\endgroup$ – symchdmath Apr 20 at 2:23
  • $\begingroup$ Thanks. Could you please explain why $P(aA) = \mathbb{P} \left(\bigcup_{i=0}^{\infty} \{X_n = A | X_0 = a \} \right)?$ $\endgroup$ – roy212 Apr 20 at 2:26
  • $\begingroup$ That is saying that in order for us to move from $a$ to $A$, that is the same as saying that we start at $a$ ($X_0 = a$) and end up at $A$ either in the first go ($X_1 = A$), or second go ($X_2 =A$) or the third go ($X_3 =A$) or so on. The big symbol $\cup$ means "or" over $i=0$ to infinity. $\endgroup$ – symchdmath Apr 20 at 2:29
  • $\begingroup$ Yes, don't worry about my answer then, I will help you out by commenting on your original post. $\endgroup$ – symchdmath Apr 20 at 2:36
  • $\begingroup$ $q_n = \mathbb{P}(X_{n} = a | X_0 = a) = (1-p_A)(1-p_B)$. What happens when n is odd? is $q_n = \mathbb{P}(X_{n} = a | X_0 = a) = 0?$. $\endgroup$ – roy212 Apr 20 at 3:22

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.