pfqn_cyclet_ofree.h File Reference

Exact passage-time law along an OVERTAKE-FREE PATH of a closed single-chain tree-like product-form network. More...

#include <algorithm>
#include <cmath>
#include <complex>
#include <cstddef>
#include <string>
#include <vector>
#include "line/api/lti/laplace_invert.h"
#include "line/util/error.h"

Include dependency graph for pfqn_cyclet_ofree.h:

Go to the source code of this file.

Classes
struct	line::pfqn::CycletPathInfo
	One path's outcome: which route ran, and the network constant it used. More...
struct	line::pfqn::CycletResult
	Density, distribution and moments of the passage time along a path. More...

Namespaces
namespace	line
namespace	line::pfqn

Functions
CycletResult	line::pfqn::pfqn_cyclet_ofree (const std::vector< double > &v, const std::vector< double > &mu, std::size_t N, const std::vector< std::vector< std::size_t > > &paths, const std::vector< double > &tset, const std::string &method="auto", std::size_t nmom=3, const std::vector< double > &pathprob={}, const std::string &lti_method="euler", double tol=1e-8)
	Exact passage-time density, CDF and moments along the overtake-free paths paths, mixed by pathprob.

Detailed Description

Exact passage-time law along an OVERTAKE-FREE PATH of a closed single-chain tree-like product-form network.

Port of matlab/src/api/pfqn/pfqn_cyclet_ofree.m, which is the reference. Source: P. G. Harrison and W. J. Knottenbelt, "Passage Time Distributions in Large Markov Chains", 2002, Sec. 7.1, Theorems 1 and 2, after P. G. Harrison, J. Appl. Prob. 27, 1990 and H. Duduna, Adv. Appl. Prob. 14, 1982. The underlying sojourn-time result for overtake-free paths is F. Kelly and P. Pollett, Adv. Appl. Prob. 15, 1983.

THE ONE FACT THAT MAKES ALL THREE ROUTES WORK. Conditional on the path,

T | z  =  sum_{j in z} Erlang(u_{z_j} + 1, mu_{z_j})

with u distributed as the network's equilibrium population vector AT N-1 (the arrival theorem). Hence the transform of Theorem 1 collapses to

L(s|z) = prod_{j in z} mu_j/(s+mu_j) * G(y(s), N-1) / G(x, N-1)

where x_i = v_i/mu_i and y_i(s) = x_i mu_i/(s+mu_i) on the path, x_i off it. One Buzen convolution per value of s.

MOMENTS ARE NEVER TAKEN FROM THE DENSITY. They come from running the same Buzen convolution in the ring of truncated power series in s, so they are exact to machine precision, are unaffected by the time grid, and stay valid when the rates coincide and Theorem 2 does not apply.

NOTE ON THE PAPER. The inner sum of Theorem 2 reads (v_j t)^(c-i)/(c-i)! and that is CORRECT as printed, however odd the visit ratio looks against a time: substituting the service rate instead returns negative densities. Verified against a direct mixture-of-Erlangs oracle to 1e-15, and at the paper's own N = 18 example against the transform route to 1e-11.

ARITHMETIC: double. The density needs exp and an incomplete gamma.

Definition in file pfqn_cyclet_ofree.h.