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.

tiny-tim
Homework Helper
welcome to pf!

hello trenekas! welcome to pf!
… Maybe there is easier way to solve this task?

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)

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

tiny-tim
Homework Helper
Yeah. i did that. but i hope that there is easier way without the census of all cases :)

but you don't need to count all cases

eg P(A+D) = 1 - p

haruspex
Homework Helper
Gold Member
2020 Award
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)}##

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:
haruspex
Homework Helper
Gold Member
2020 Award
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

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
}

tiny-tim
Homework Helper
hi trenekas!

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

(and leave some spaces!)

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

yes, but i don't follow the rest of it …
-(1-p)*(1-p)^2*(1-p)^2+(1-p)^3*(1-p)^3*(1-p)*(1-p)^2*(1-p)^2*(1-p)

… 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

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:
haruspex
Homework Helper
Gold Member
2020 Award
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?

Ray Vickson
Homework Helper
Dearly Missed
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.

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.

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
}
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:
tiny-tim
Homework Helper
(just got up :zzz:)
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?

yes
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.

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

haruspex