I'm interested in the behaviour of the following sort of system.
We are given: a finite set $X$, a subset $A_0 \subset X$, and a function $f : X \times X \to [0,1]$.
(It's supposed to model how a particular piece of information spreads, where: $X$ is some community, $A_0$ is the members who already know that information, and $f(x,y)$ is the probability that $x$ tells that information to $y$ in a unit of time.)
Then we successively generate $A_{n+1}$ by: if $x \in A_n$ then $x \in A_{n+1}$, and if $x \in X \setminus A_n$ then the probability of $x$ being in $A_{n+1}$ is given by $$P(x \in A_{n+1}) = 1-\prod_{a \in A_n}(1-f(a,x)).$$ (We can use this formula for all $x \in X$ if we ask $f(x,x)=1$.)
Has this sort of thing been studied before? In particular, I would be interested to know:
- Given $x \in X$ and $n \ge 0$, is there an efficient way to compute $P(x \in A_n)$?
- What if $f$ varies with time?
(The emphasis is on "efficient" here; one can turn this into a Markov process with state space $2^X$, but I'd prefer dealing with something smaller.)
Even just pointing to the right term to search would be very helpful.
Thank you very much in advance!
Edit: I believe the hardest part is dealing with dependency. For a fixed path $\pi = (x_0 \to x_1 \to \dots \to x_n)$, of course the probability $P(\pi)$ of the corresponding event (i.e. the information reaching from $x_0$ to $x_n$ via this particular route) can be calculated as $\prod_{1 \le i \le n}f(x_{i-1},x_i)$. But there can be many such paths, and what's unclear is how to combine them.
Just summing them would overestimate the probability since you are essentially assuming those events to be mutually exclusive. Something a little more sophisticated like $1-\prod_\pi(1-P(\pi))$ still doesn't work since you are assuming the events to be totally independent from each other when different paths can have common edges. For example, consider: $X = \{a,b,x,y\}$, $A_0 = \{a,b\}$, $f(a,x)=f(b,x)=f(x,y) = 1/2$ and $f$ takes the value $0$ elsewhere. Then we should get $P(y \in A_2) = 3/8$, but this formula yields $7/16$.
Edit 2: I have now cross-posted this question on MO.
Yes, you can!
Construct a graph of size $|X|$ with vertex for a person, and the weights on the edges are $f(x,y)$.
Then you want to sum all the product-trajectories in length up to $n$. (by the way, you can use log probabilities and then sum and exponent instead of multiplying).
This can be done in a dynamic programming. See here for example.
If $f$ varies in time, you will need a grpah in size $|X|\cdot n$ in order to express it, but still possible in polynomial complexity