mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2020-04-01, 12:15   #1
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

170108 Posts
Default April 2020

http://www.research.ibm.com/haifa/po...April2020.html
Xyzzy is offline   Reply With Quote
Old 2020-04-01, 18:43   #2
virgo
 
Apr 2020

22 Posts
Default

is there someone get 29.16521896% after day 10?
i'm still getting 24.25371788% ._.
virgo is offline   Reply With Quote
Old 2020-04-01, 22:12   #3
uau
 
Jan 2017

2×37 Posts
Default

Quote:
Originally Posted by virgo View Post
is there someone get 29.16521896% after day 10?
Yes, my calculations match the provided answer for the example graph.
uau is offline   Reply With Quote
Old 2020-04-01, 22:19   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by Xyzzy View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2020-04-01, 22:33   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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??
R.D. Silverman is offline   Reply With Quote
Old 2020-04-01, 23:44   #6
uau
 
Jan 2017

2·37 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
uau is offline   Reply With Quote
Old 2020-04-02, 01:51   #7
virgo
 
Apr 2020

22 Posts
Default

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
virgo is offline   Reply With Quote
Old 2020-04-02, 01:52   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by uau View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2020-04-02, 01:59   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2020-04-02, 02:07   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2020-04-02, 02:10   #11
uau
 
Jan 2017

2·37 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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?
uau is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
U.S. Electile Dysentery 2020 ewmayer Soap Box 308 2020-09-14 23:50
2020 project goals gd_barnes Conjectures 'R Us 3 2020-09-03 20:21
March 2020 what Puzzles 1 2020-04-24 05:46
February 2020 what Puzzles 20 2020-03-04 07:55
January 2020 what Puzzles 21 2020-02-02 14:11

All times are UTC. The time now is 18:00.

Fri Sep 18 18:00:37 UTC 2020 up 8 days, 15:11, 1 user, load averages: 1.96, 1.70, 1.57

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.