Conditional expectation

[Kate2010]

Homework Statement

An email is sent on the network in which the recipients (0,1,2,3,4,5} are in communication.
1 can send to 4 and 2
2 to 1,3,5
3 to 0,2,5
4 to 1, 5
5 to 0,2,4
0 to 3 and 5
If a message is sent to 2,3,4,5 it is forwarded randomly to a neighbour (even if this means a repeat). 0 and 1 never forward messages.
Let e_k be the expected number of time that a message starting at k is passed on.
Find e₄.

Homework Equations

E(X) = $$\sum$$ E(X|A)P(A)

The Attempt at a Solution

I think I need to partition this but I'm unsure on the partition.

Let X be the number of times a message is sent on
E(X) = E(X|1st move is to 0)P(1st move is to ) + E(X|1st move is to 1)P(1st move is to 1) + E(X|1st move is to 2)P(1st move is to 2) + E(X|1st move is to 3)P(1st move is to 3) + E(X|1st move is to 4)P(1st move is to 4) + E(X|1st move is to 5)P(1st move is to 5)

I'm not sure how I'd work these out using a general k to start at.

If I assume I start at 4, as I'm trying to find e₄ then I get
e₄ = 0 + 1x(1/2) + 0 + 0 + e₅ (1/2)
2e₄ = 1 + e₅

e₅ = 1x(1/2) + 0 + e₂ (1/3) + 0 + e₄ (1/3)

I don't really think I'm going about this the right way, I would have thought I need to find a formula for starting at a general k but I don't know how.

 

[mighty2000]

I know the answer is 4.Hi there,

Your approach is definitely on the right track! To find the expected number of times a message is passed on, we can use the law of total expectation. This states that the expected value of a random variable can be found by taking the sum of the expected values of the random variable within each partition, weighted by the probability of each partition occurring.

For this problem, we can partition the possible paths of the message based on the first move. So let's start with the partition P1, where the first move is to 0. In this case, the expected number of times the message is passed on is just 0, since 0 never forwards messages.

Next, let's look at the partition P2, where the first move is to 1. In this case, the message will be passed on once with probability 1/2 (to 4) and twice with probability 1/2 (to 2 and then back to 1). So the expected number of times the message is passed on in this partition is 1/2 + 2(1/2) = 2.

Following the same logic, we can find the expected number of times the message is passed on in the remaining partitions P3, P4, P5, and P6. Then, using the law of total expectation, we can find the expected number of times the message is passed on overall:

E(X) = E(X|P1)P(P1) + E(X|P2)P(P2) + E(X|P3)P(P3) + E(X|P4)P(P4) + E(X|P5)P(P5) + E(X|P6)P(P6)

= 0(1/6) + 2(1/6) + 3(1/6) + 2(1/6) + 3(1/6) + e4(1/6)

= (2 + 3 + 3)/6 + e4/6

= 4 + e4/6

Since we know that the expected number of times the message is passed on is 4, we can solve for e4:

4 = 4 + e4/6

e4 = 24 - 24 = 0

So the expected number of times a message starting at 4 is passed