 mersenneforum.org April 2020
 Register FAQ Search Today's Posts Mark Forums Read  2020-04-01, 12:15 #1 Xyzzy   "Mike" Aug 2002 11111111001012 Posts April 2020   2020-04-01, 18:43 #2 virgo   Apr 2020 510 Posts is there someone get 29.16521896% after day 10? i'm still getting 24.25371788% ._.   2020-04-01, 22:12   #3
uau

Jan 2017

2×32×5 Posts Quote:
 Originally Posted by virgo is there someone get 29.16521896% after day 10?
Yes, my calculations match the provided answer for the example graph.   2020-04-01, 22:19   #4
R.D. Silverman

Nov 2003

22×5×373 Posts Quote:
 Originally Posted by Xyzzy http://www.research.ibm.com/haifa/po...April2020.html
HUH?

This problem seems very under-posed! Some questions:

(1) What are the initial conditions? If all are healthy at t=0, then they remain healthy.
(if one is adjacent to 2 rather than 3 people the chance that at t+1 a neighbor will get
sick is lower).
(1a) How MANY are sick at t= 0??? Just one? Do we get to select which one
is sick at t = 0?
(1b) Can a sick person infect more than one adjacent person?

(2) If someone is sick at time t do the people immediately adjacent become sick with equal probability? (assuming the healthy ones have no other sick neighbors)

(3) Is it possible that once infected, someone will heal? If so, how long does it take?
[I assume not, but it needs to be stated]

(4) If sick at t, how is the probability determined that someone adjacent becomes sick
at t+1? Is it constant throughout the 10 days? Is it a necessity that someone adjacent does become sick? i.e. if at time 0 someone is sick and does not infect a neighbor
must another adjacent neighbor become sick?

(4) If someone is sick at time t do the people adjacent become sick with equal probability?

(5) Are the probabilities independent? If someone is healthy and two adjacent people are sick at t,
does one add the probabilities (p1+p2) that the person becomes sick at t+1 or is the probability
1- ( (1-p1)(1-p2))?

I assume the latter. I can see an argument for either if it is possible to get infected by two people at the same time....

Or am I just plain missing the obvious?

Last fiddled with by R.D. Silverman on 2020-04-01 at 22:25   2020-04-01, 22:33   #5
R.D. Silverman

Nov 2003

164448 Posts Quote:
 Originally Posted by R.D. Silverman HUH? This problem seems very under-posed! Some questions: (1) What are the initial conditions? If all are healthy at t=0, then they remain healthy. (if one is adjacent to 2 rather than 3 people the chance that at t+1 a neighbor will get sick is lower). (1a) How MANY are sick at t= 0??? Just one? Do we get to select which one is sick at t = 0? (1b) Can a sick person infect more than one adjacent person? (2) If someone is sick at time t do the people immediately adjacent become sick with equal probability? (assuming the healthy ones have no other sick neighbors) (3) Is it possible that once infected, someone will heal? If so, how long does it take? [I assume not, but it needs to be stated] (4) If sick at t, how is the probability determined that someone adjacent becomes sick at t+1? Is it constant throughout the 10 days? Is it a necessity that someone adjacent does become sick? i.e. if at time 0 someone is sick and does not infect a neighbor must another adjacent neighbor become sick? (4) If someone is sick at time t do the people adjacent become sick with equal probability? (5) Are the probabilities independent? If someone is healthy and two adjacent people are sick at t, does one add the probabilities (p1+p2) that the person becomes sick at t+1 or is the probability 1- ( (1-p1)(1-p2))? I assume the latter. I can see an argument for either if it is possible to get infected by two people at the same time.... Or am I just plain missing the obvious?
Also:

Is it possible to infect more than one person in a time period??   2020-04-01, 23:44   #6
uau

Jan 2017

2·32·5 Posts Quote:
 Originally Posted by R.D. Silverman This problem seems very under-posed! Some questions:
I think the initial conditions are the only particularly unclear part. I assumed that the first person (corresponding to the first row of the adjacency matrix) is always the only person infected at start.

For the rest, I think the following is the most obvious natural way to calculate how the set of infected people changes from one day to the next, and does match the probability given for the example:

Given a set of infected people S, find all edges in the graph that connect to an infected person. Color each such edge red with 10% probability. The next set of infected people is people who are either already in S or have a red edge.   2020-04-02, 01:51 #7 virgo   Apr 2020 510 Posts If I want to calculate probability of all infected at day t, should I just product all edges infection probability? If there are only 3 edges and infection probabilities are like (a:0.1, b:0.1, c:0.1) all edges infected probability @ day t = (0.1)^3 ? or should I also concern all edges infected probability @ day 0 to t-1 ? its rly confusing   2020-04-02, 01:52   #8
R.D. Silverman

Nov 2003

22·5·373 Posts Quote:
 Originally Posted by uau I think the initial conditions are the only particularly unclear part. I assumed that the first person (corresponding to the first row of the adjacency matrix) is always the only person infected at start.
But the labeling is arbitrary... Any node for a given graph can be labeled 'A'.

An interesting question: Given a graph X. Delete an edge. Prove or disprove that
the resulting graph always has a lower probability.

This seems intuitively true. The resulting graph has two people with no direct contact,
thus lowering the probability for at least those two.

This immediately suggests that the maximal probability graph should be complete.
(every node connected to every other). Now all one need do is check the complete graphs
to size 8.   2020-04-02, 01:59   #9
R.D. Silverman

Nov 2003

22×5×373 Posts Quote:
 Originally Posted by R.D. Silverman But the labeling is arbitrary... Any node for a given graph can be labeled 'A'. An interesting question: Given a graph X. Delete an edge. Prove or disprove that the resulting graph always has a lower probability. This seems intuitively true. The resulting graph has two people with no direct contact, thus lowering the probability for at least those two. This immediately suggests that the maximal probability graph should be complete. (every node connected to every other). Now all one need do is check the complete graphs to size 8.
I think the correct approach to a proof is to model the problem as a stochastic
process/martingale. I wish I could remember the material..... Its been 45 years
since I last looked at/took a course....Can you say "ossification of the intellect"?

Last fiddled with by R.D. Silverman on 2020-04-02 at 02:00 Reason: typo   2020-04-02, 02:07   #10
R.D. Silverman

Nov 2003

1D2416 Posts Quote:
 Originally Posted by R.D. Silverman I think the correct approach to a proof is to model the problem as a stochastic process/martingale. I wish I could remember the material..... Its been 45 years since I last looked at/took a course....Can you say "ossification of the intellect"?
BTW, there is a reason why .70 was selected. (1-1/e) should be familiar to participants
herein.

Another interesting question. Among all graphs, which is maximal? I think I know the answer.

Last fiddled with by R.D. Silverman on 2020-04-02 at 02:10   2020-04-02, 02:10   #11
uau

Jan 2017

2×32×5 Posts Quote:
 Originally Posted by R.D. Silverman But the labeling is arbitrary... Any node for a given graph can be labeled 'A'.
Well if you assume an unlabeled graph, you could label it arbitrarily. But the adjacency matrix necessarily implies an ordering of the graph nodes. So I interpreted it as: "find an adjacency matrix such that the probability will be close to 70% when doing 10 steps from the state where the node corresponding to the first row is the only infected node".

Quote:
 This immediately suggests that the maximal probability graph should be complete. (every node connected to every other). Now all one need do is check the complete graphs to size 8.
I don't quite get the point here? Sure the complete graph has maximal probability. But we're not trying to find maximal probability, we're trying to get close to 70%. So if we find that a size 5 complete graph has probability >70%, now what?   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post ewmayer Soap Box 685 2021-03-03 23:29 gd_barnes Conjectures 'R Us 14 2020-12-30 15:58 what Puzzles 1 2020-04-24 05:46 what Puzzles 20 2020-03-04 07:55 what Puzzles 21 2020-02-02 14:11

All times are UTC. The time now is 04:44.

Fri May 14 04:44:31 UTC 2021 up 35 days, 23:25, 0 users, load averages: 1.65, 1.68, 1.88