Table of Contents

  1. Molloy 1985: Discrete Time Stochastic Petri Nets
  2. Glynn 1989: A GSMP Formalism for Discrete Event Systems
  3. pomp docs: A quick note on Exponential and Geometric processes from the pomp documentation

Discrete Time Petri Nets (Molloy 1985 DOI:10.1109/TSE.1985.232230)

For a discrete time stochastic Petri net (DTSPN), on each time step, if no events are in conflict, then the probability of any combination of firings and non-firings (a binary vector) will simply be a product of \(\rho_{i}\) and \(1-\rho_{i}\). The probability \(\rho_{i}\) are assigned by the designer a priori, and are “the probability that the enabled transition \(t_{i}\) fires at the next time step, given (conditioned on) the fact that no other transition fires.” This means the firing times are Geometrically distributed, if \(\rho_{i}<1\).

Molloy’s equation 4 is: \[\rho_{i} = \frac{P[E_{i}]}{P[E_{i}\cup E_{0}]}\].

We can interpret this equation like this, the denominator is restricting the sample space to \(E_{i}\cup E_{0}\), that is, the world where either nothing happens or \(E_{i}\) happens (\(P[E_{i}\cup E_{0}] = P[E_{i}] + P[E_{0}] + P[E_{i}\cap E_{0}]\) but because the events are mutually exclusive, \(P[E_{i}\cap E_{0}] = 0\)). So the equation asks “given only nothing or \(E_{i}\) can happen, what’s the probability \(E_{i}\) happens?”, which is precisely the interpretation of \(\rho_{i}\) used by the modeller.

In a set of mutually exclusive transitions \(\{t_{i}\}\), that equation holds for all, so using the constraint all \(0<\rho_{i}<1\), one can solve for \(P[E_{0}]\) (he does not show this). Let’s consider the simple case with 2 mutually exclusive transitions. We get 3 equations, and 3 unknowns (the elementary unconditional probabilities). The denominators are sums here, he writes unions but because the events are mutually exclusive the intersection, coming from the inclusion-exclusion principle is the zero set.

\[ P[E_{0}] + P[E_{1}] + P[E_{2}] = 1 \\ \rho_{1} = \frac{P[E_{1}]}{P[E_{1}] + P[E_{0}]} \\ \rho_{2} = \frac{P[E_{2}]}{P[E_{2}] + P[E_{0}]} \] Solving these is easy, start with \(P[E_{1}]\):

\[ \rho_{1} = \frac{P[E_{i}]}{P[E_{i}\cup E_{0}]} = \frac{P[E_{1}]}{P[E_{1}] + P[E_{0}]} \\ \rho_{1}( P[E_{1}] + P[E_{0} )= P[E_{1}] \\ \rho_{1}P[E_{1}] + \rho_{1}P[E_{0} = P[E_{1}] \\ \rho_{1}P[E_{0}] = P[E_{1}] - \rho_{1}P[E_{1}] \\ \rho_{1}P[E_{0}] = P[E_{1}] (1 - \rho_{1}) \\ P[E_{1}] = \frac{\rho_{1}}{(1 - \rho_{1})}P[E_{0}] \\ \] And that holds generally with sets of mutually exclusive transitions. Then just use the knowledge that the sum of all events is 1 to solve for \(P[E_{0}]\).

The case for \(\{t_{i}\}\) sets larger than 2 follows generally. The key is just realizing that due to mutual exclusivity, the denominators of the conditional probabilities \(\rho_{i}\) can be changed so \(P[E_{0}]\) does not appear in them, solve for all the \(P[E_{i}]\) values, then use the sum to 1 constraint to get \(P[E_{0}]\). Molloy gives a formula for the probability that a particular transition in a set fires to be:

\[ P[E_{i}] = \frac{\frac{\rho_{i}}{1-\rho_{i}}}{ 1 + \sum \frac{\rho_{j}}{1-\rho_{j}} } \]

molloy <- function(rho,i){
  (rho[i] / (1 - rho[i]))  / ( 1 + sum( rho / (1 - rho) ))

rho <- c(0.5,0.25)

We can check our solution works against his:

fractions((rho[1] - prod(rho)) / (1 - prod(rho)))
## [1] 3/7
## [1] 3/7

If \(\rho_{i}=1\) is allowed for some subset \(T_{D}\subset T_{E}\) in the set of enabled, mutually exclusive (conflicting) transitions, the previous equations do not make sense. Molloy gives the only reasonable conflict resolution as saying that for \(t_{i}\in T_{E}\) where \(\rho_{i}<1\), their probability of firing \(P[E_{i}]\) is zero. For \(t_{i}\in T_{D}\):

\[ P[E_{i}] = \frac{1}{|T_{D}|} \]

By making “chains” of \(\rho_{i}=1\) transitions and places, one can implement deterministic firing time distributions into DTSPN.

Now, that worked nicely when the sets of transitions were all mutually exclusive, but there are complications he remarks upon. For the 4 token SPN in Fig. 1, we have a set of transitions that are in conflict but not mutually exclusive. Based on the firing rules, the sample space contains the following exhaustive, mutually exclusive events:

\[ S = \{E_{0}, E_{1}, E_{2}, E_{3}, E_{12}, E_{23}, E_{13}\} \] So we can have no transitions fire, any single transition fire, or any combination of 2 transitions firing. The modeller gives us \(\{\rho_{1}, \rho_{2}, \rho_{3}\}\). We know \(P[E_{i}]\) for each of the events corresponding to a single