Problem with probability theory task

[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 don't 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 don't really 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]

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)

 

[trenekas]

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

 

[tiny-tim]

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]

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 P_k(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)}$

 

[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

So answer will be: (1-p)+2(1-p)^2+2(1-p)^3-(1-p)*(1-p)^2*(1-p)^2+(1-p)^3*(1-p)^3*(1-p)*(1-p)^2*(1-p)^2*(1-p)?

 

[haruspex]

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

So answer will be: (1-p)+2(1-p)^2+2(1-p)^3-(1-p)*(1-p)^2*(1-p)^2+(1-p)^3*(1-p)^3*(1-p)*(1-p)^2*(1-p)^2*(1-p)?

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

 

[tiny-tim]

hi trenekas!

(try using the X² 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

So answer will be: (1-p)+2(1-p)²+2(1-p)³ …

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

 

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

 

[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?

 

[Ray Vickson]

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 don't 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 don't really 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,&amp; x_1 &amp; x_2 &amp; x_3\\x_1 &amp; 0&amp; x_4 &amp; x_5\\x_2 &amp; x_4 &amp;0 &amp;x_6\\<br /> x_3&amp;x_5&amp;x_6&amp;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 \\<br /> 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.

 

[trenekas]

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

Im not understand all of this. 1-p means probability of A+D. 2(1-p)² - (1-p)⁴ i think mean probability of A+B,B+D and A+C,C+D without their union. and last i don't 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 :)

 

[tiny-tim]

(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

(for example, you could start with P(A+D) + P(A+B,B+D,notA+D) …)

 

[haruspex]

I broke it into cases according to the length of the shortest path.
Length 1: AD, prob 1-p.
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)² 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)² - p(1-p)⁴.
Length 3: ABCD or ACBD. Each has prob (1-p)³ 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 p³(1-p)³. Similarly for ACBD. No need to eliminate double counting this time since we have already ensured no other links exist.
Is that clearer?

 

[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!