Experiments with acyclic stochastic Petri nets (Rev #1, changes)

Showing changes from revision #0 to #1:
Added | ~~Removed~~ | ~~Chan~~ged

For any non-negative integer $j$, define $f_j:R \to R$ by $f_j(x) = e^{-jx}$ for $x \ge 0$ and $f_j(x) = 0$ for $x \lt 0$. For a sequence $J$ of non-negative integers $j_1, \dots, j_k$, define $f_J:R \to R$ to be the convolution of all the $f_j$‘s, that is, $f_J = f_{j_1} \circ \dots \circ f_{j_k}$.

Suppose $G$ is a directed acyclic graph with a single root $r$ (a root is a node with indegree 0) and that $n$ is a node connected to $r$. For any walk $w$ from $r$ to $n$, let $J(w)$ be the sequence of outdegrees of the nodes along the walk, including both $r$ and $n$. Let $W(n)$ be the set of all walks from $r$ to $n$. Then the probability of a walker being at $n$ time $t$ after it was at $r$ is

$P(n,t) = \sum_{w \in W(n)} f_{J(w)} (t).$

I don’t have a proper proof, but I do have a calculation for one case, see R code for acyclic stochastic Petri net.

Note that if $j=0$ then $f_j(x)$ is just $1$ for $x \ge 0$, and convolving with this is the same as integrating, so if $n$ has outdegree 0, the formula still works, though it is a bit of a special case.

category: experiments