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

Showing changes from revision #0 to #1: Added | Removed | Changed

For any non-negative integer jj, define f j:RRf_j:R \to R by f j(x)=e jxf_j(x) = e^{-jx} for x0x \ge 0 and f j(x)=0f_j(x) = 0 for x<0x \lt 0. For a sequence JJ of non-negative integers j 1,,j kj_1, \dots, j_k, define f J:RRf_J:R \to R to be the convolution of all the f jf_j‘s, that is, f J=f j 1f j kf_J = f_{j_1} \circ \dots \circ f_{j_k}.

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

P(n,t)= wW(n)f J(w)(t). 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=0j=0 then f j(x)f_j(x) is just 11 for x0x \ge 0, and convolving with this is the same as integrating, so if nn has outdegree 0, the formula still works, though it is a bit of a special case.

category: experiments