# Problem with probability theory task

1. Mar 9, 2013

### trenekas

Hello. I have problem with probability theory task. Sorry for my english but i'll try to define the task.

There are four classmates. Ana, Beta, Ceta and Deta. During the break all of them tiffed (probability is p) or became best friends (probability is 1-p). And all with each other tiffed or became best friend. After lessons, girls telling interesting stories or rumors for their best friends. Suppose that Ana to know something interesting. And we need to calculate probability that Deta will hear this news.

I dont know how to calculate this in the simply way. I just wrote all options. Results of all this is:(plus mean that became friends, minus - that became enemies)

1)A+B, A+C, A+D, B+C, B+D, C+D

2)A-B, A+C, A+D, B+C, B+D, C+D
3)A+B, A-C, A+D, B+C, B+D, C+D
4)A+B, A+C, A-D, B+C, B+D, C+D
5)A+B, A+C, A+D, B-C, B+D, C+D
6)A+B, A+C, A+D, B+C, B-D, C+D
7)A+B, A+C, A+D, B+C, B+D, C-D

8)A-B, A-C, A+D, B+C, B+D, C+D
9*)A-B, A+C, A+D, B-C, B+D, C-D
10)A-B, A+C, A-D, B+C, B+D, C+D
11)A-B, A+C, A+D, B-C, B+D, C+D
12)A-B, A+C, A+D, B+C, B-D, C+D
13)A-B, A+C, A+D, B+C, B+D, C-D
14)A+B, A-C, A-D, B+C, B+D, C+D
15)A+B, A-C, A+D, B-C, B+D, C+D
16)A+B, A-C, A+D, B+C, B-D, C+D
17)A+B, A-C, A+D, B+C, B+D, C-D
18)A+B, A+C, A-D, B-C, B+D, C+D
19)A+B, A+C, A-D, B+C, B-D, C+D
20)A+B, A+C, A-D, B+C, B+D, C-D
21)A+B, A+C, A+D, B-C, B-D, C+D
22)A+B, A-C, A+D, B+C, B-D, C-D

23)A-B, A-C, A-D, B+C, B+D, C+D
24)A-B, A-C, A+D, B-C, B+D, C+D
25)A-B, A-C, A+D, B+C, B-D, C+D
26)A-B, A-C, A+D, B+C, B+D, C-D
27)A-B, A+C, A-D, B-C, B+D, C+D
28)A-B, A+C, A-D, B+C, B-D, C+D
29)A-B, A+C, A-D, B+C, B+D, C-D
30)A-B, A+C, A+D, B-C, B-D, C+D
31)A-B, A+C, A+D, B-C, B+D, C-D
32)A-B, A+C, A+D, B+C, B-D, C-D
33)A+B, A-C, A-D, B-C, B+D, C+D
34)A+B, A-C, A-D, B+C, B-D, C+D
35)A+B, A-C, A-D, B+C, B+D, C-D
36)A+B, A-C, A+D, B-C, B-D, C+D
37)A+B, A-C, A+D, B-C, B+D, C-D
38)A+B, A-C, A+D, B+C, B-D, C-D
39)A+B, A+C, A-D, B-C, B-D, C+D
40)A+B, A+C, A-D, B-C, B+D, C-D
41)A+B, A+C, A-D, B+C, B-D, C-D
42)A+B, A+C, A+D, B-C, B-D, C-D

43)A+B, A+C, A-D, B-C, B-D, C-D
44*)A+B, A-C, A-D, B+C, B-D, C+D
45)A+B, A-C, A+D, B-C, B-D, C-D
46)A+B, A-C, A-D, B+C, B-D, C-D
47)A+B, A-C, A-D, B-C, B+D, C-D
48)A+B, A-C, A-D, B-C, B-D, C+D
49)A-B, A+C, A+D, B-C, B-D, C-D
50)A-B, A+C, A-D, B+C, B-D, C-D
51)A-B, A+C, A-D, B-C, B+D, C-D
52)A-B, A+C, A-D, B-C, B-D, C+D
53)A-B, A-C, A+D, B+C, B-D, C-D
54)A-B, A-C, A+D, B-C, B+D, C-D
55)A-B, A-C, A+D, B-C, B-D, C+D
56)A-B, A-C, A-D, B+C, B+D, C-D
57)A-B, A+C, A-D, B-C, B+D, C+D

58)A+B, A-C, A-D, B-C, B-D, C-D
59)A-B, A+C, A-D, B-C, B-D, C-D
60)A-B, A-C, A+D, B-C, B-D, C-D
61)A-B, A-C, A-D, B+C, B-D, C-D
62)A-B, A-C, A-D, B-C, B+D, C-D
63)A-B, A-C, A-D, B-C, B-D, C+D

64)A-B, A-C, A-D, B-C, B-D, C-D

So I calculated that 48 of these statisfies that Deta will get rumors. And inserted probabilistic values and sumed polynomials got that probability is equal to -2p^6+5p^5-2p^4-2p^3+1.
I dont realy know or this answer is correct. When p is 0.5, looks like good if my calculations that 48 variants statisfy with condition.

I want to ask you help. Maybe there is easier way to solve this task? Thanks.

2. Mar 10, 2013

### tiny-tim

welcome to pf!

hello trenekas! welcome to pf!
divide it into cases:

A+D
A+B B+D
A+C C+D
and … ?

and find the probability of each

(and remember that these cases overlap)

3. Mar 10, 2013

### trenekas

Yeah.but is quite difficult too i think :) but thanks :) i will wait the lecture and see what is easiest solution. :)

4. Mar 10, 2013

### tiny-tim

but you don't need to count all cases

eg P(A+D) = 1 - p

5. Mar 11, 2013

### haruspex

Tiny-tim's method is pretty easy for just four nodes. As a graph, you have four possible shortest routes: AD, ABD, ACD, ABCD. For larger numbers, you could construct a recurrence relation. Let Pk(n; r, s) be the prob of reaching r of n nodes in k steps, s in k+1. I get $P_{k+1}(n; r, s) = Ʃ_t P_k(n; t, r)\left(^{n-r}_s\right)(1-p^{r-t})^sp^{(r-t)(n-r-s)}$

6. Mar 11, 2013

### trenekas

OK :) thanks a lot, guys
P(A+D)=(1-p), P(A+B,B+D)=(1-p)^2, P(A+C,C+D)=(1-p)^2, P(A+B,B+C,C+D)=(1-p)^3 and P(A+C,B+C,B+D)=(1-p)^3

Last edited: Mar 11, 2013
7. Mar 11, 2013

### haruspex

Seems too much. After counting 1-p for AD, can apply a factor p to all remaining terms.
+p{2(1-p)2 - (1-p)4 for ABD or ACD but counting both only once
+2p2(1-p)3 for ABCD or ACBD but no other connections
}

8. Mar 11, 2013

### tiny-tim

hi trenekas!

(try using the X2 button just above the Reply box )

(and leave some spaces!)

yes, but i don't follow the rest of it …
… you certainly need to subtract the overlaps (and maybe add some "double-overlaps" etc), but it would be easier to check if you write out the P() formulas first

9. Mar 12, 2013

### trenekas

Edit :D
Let 1)P(A+D)=(1-p), 2)P(A+B,B+D)=(1-p)^2, 3)P(A+C,C+D)=(1-p)^2, 4)P(A+B,B+C,C+D)=(1-p)^3 and 5)P(A+C,B+C,B+D)=(1-p)^3

i found the formula. This is correct? but this formula have 36 members :O
P(1U2U3U4U5)=P(1)+P(2)+P(3)+P(4)+P(5) minus all unions(10) in pairs, add all unions(10) in three, minus all unions(5) in four, and finaly add one union in five.

Last edited: Mar 12, 2013
10. Mar 12, 2013

### haruspex

I believe that should produce the right answer, but why not use the logic I laid out in post 7? Did you understand what I wrote?

11. Mar 12, 2013

### Ray Vickson

I am trying to understand your problem. I think what you are saying is the following: there are 4 "nodes", A,B,C,D. For each node pair (i,j) separately, there is an arc between nodes i and j with probability (1-p) [meaning that i and j are best friends], and no arc between i and j with probability p [meaning that i and j are angry at each other and so do not talk to one another]. So, altogether, you have a random graph with nodes A, B, C, D, and you want to know if there is a path between A and D in the graph [meaning that a message can get from A to D]. Here is how I would do it.

First, let'snumber the nodes as 1,2,3,4 instead of A,B,C,D. Set up a node-node incidence matrix
$$A = \pmatrix{0,& x_1 & x_2 & x_3\\x_1 & 0& x_4 & x_5\\x_2 & x_4 &0 &x_6\\ x_3&x_5&x_6&0}$$
Here, $a_{i,j} = 1$ if there is an arc from i to j and $a_{i,j} = 0$ if not. When we take succesive matrix powers of A we are finding whether or not there are paths of length >=2 from i to j. In particular, $A^k(1,4) > 0$ if there is at least one path of length k from 1 to 4, and $A^k(1,4) = 0$ if there is no path of length k from 1 to 4.

We can use a computer algebra package to perform the matrix multiplications $A^2, \, A^3, \, A^4$ (always using the fact that $x_i^2 = x_i , \; x_i^3 = x_i,$ etc., since all the $x_i$ are either 0 or 1.

Here are the results:
$$A^2(1,4) = x_1 x_5 + x_2 x_6 \\ A^3(1,4) =x_3 + x_1 x_3 + x_2 x_3 + x_3 x_5 + x_3 x_6 + x_1 x_4 x_6 + x_2 x_4 x_5 ,$$
and $A^4(1,4)$ is a much longer expression, to be simplified later.

Let us ask for conditions in which there is NO path from 1 to 4, so we need all individual terms in $A^2$ and $A^3$ to vanish (since they are all >= 0 and their sums must vanish). Therefore, we need $x_1 x_5 = 0, x_2 x_6 = 0$ and $x_3 = 0,$ hence also
$x_1 x_4 x_6 = 0, x_2 x_4 x_5 = 0.$ When these are substituted into the expression for $A^4(1,4)$, the result is 0, so no more conditions are obtained by looking at $A^4$.

Thus, we have that no path exists from 1 to 4 if and only if all of the following obtain:
$$x_3 = 0, x_1 x_5 = 0, x_2 x_6 = 0, x_1 x_4 x_6=0, x_2 x_4 x_5 = 0.$$
We can now try to find the probability that all of these hold, given that $P(x_i = 0) = p$ for all i and that the $x_i$ are independent.

12. Mar 12, 2013

### trenekas

Im not understand all of this. 1-p means probability of A+D. 2(1-p)2 - (1-p)4 i think mean probability of A+B,B+D and A+C,C+D without their union. and last i dont understand what it mean "2p^2(1-p)3 for ABCD or ACBD but no other connections". And also all of this multiplied by p. maybe the problem is my english, also Ray Vickson solution is very difficult to understand all facts :) but thanks a lot, guys :)

Last edited: Mar 12, 2013
13. Mar 13, 2013

### tiny-tim

(just got up :zzz:)
yes
yes, but you have to be careful …

for example P(1U2) = P(1)P(2)

but P(2U4) ≠ P(2)P(4)

hmm … this method is going to be just as long as counting all the paths

see if you can find a short-cut

14. Mar 13, 2013

### haruspex

I broke it into cases according to the length of the shortest path.
For all longer paths, there must be no link AD, so there is a factor p to apply to all of them.
Length 2: ABD or ACD. Each has prob (1-p)2 of being a path, but must be multiplied by p for it to be a shortest path. And we have to avoid counting double when both exist, so this length case adds 2p(1-p)2 - p(1-p)4.
Length 3: ABCD or ACBD. Each has prob (1-p)3 of being a path. For there to be no shorter path, in the ABCD case, the links AD, AC, BD must not exist, so the prob this adds is p3(1-p)3. Similarly for ACBD. No need to eliminate double counting this time since we have already ensured no other links exist.
Is that clearer?

15. Mar 14, 2013

### trenekas

Thanks haruspex. Yeah :) understand. Also today was lecture of probability theory and lecturer said that this task was to hard for us. He made a mistake to giving us this task :D However thanks for all you!