pfqn_cftp.h File Reference

Perfect stationary state sampling for closed single-class multiserver product-form networks, by monotone Coupling From The Past. More...

#include <cmath>
#include <cstddef>
#include <vector>
#include "line/api/pfqn/pfqn_mc_common.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for pfqn_cftp.h:

Go to the source code of this file.

Classes
struct	line::pfqn::CftpResult< T >
	Return value of pfqn_cftp, mirroring [Q, X, T]. More...

Namespaces
namespace	line
namespace	line::pfqn

Enumerations
enum class	line::pfqn::CftpMethod { line::pfqn::Cftp , line::pfqn::Approx }
	Which sampler to run. More...

Functions
template<class T>
CftpResult< T >	line::pfqn::pfqn_cftp (const std::vector< T > &L, int N, const std::vector< int > &S, std::size_t nsamples, CftpMethod method, McRng &rng)
	Perfect stationary state sampling for closed single-class multiserver product-form networks, by monotone Coupling From The Past.
template<class T>
CftpResult< T >	line::pfqn::pfqn_cftp (const std::vector< T > &L, int N, McRng &rng)
	Reference defaults: single servers, one sample, exact CFTP.

Variables
constexpr int	line::pfqn::cftp_inf_servers = -1
	Sentinel for an infinite-server (delay) station, the reference's S = Inf.

Detailed Description

Perfect stationary state sampling for closed single-class multiserver product-form networks, by monotone Coupling From The Past.

Templated port of matlab/src/api/pfqn/pfqn_cftp.m, cross-checked against jar/src/main/java/jline/api/pfqn/Pfqn_cftp.java. Reference: S. Kijima and T. Matsui, "Approximate/Perfect Samplers for Closed Jackson Networks", Winter Simulation Conference 2005.

The chain moves one adjacent station pair at a time. A single uniform u encodes both the pair, through lam = 1 + u (M-1) and j = floor(lam), and the split of the pair's combined occupancy k = x_j + x_{j+1}, through the fractional part Lambda used as an inverse-CDF argument against

w(s) proportional to alpha_j(s) alpha_{j+1}(k-s), log alpha_i(m) = m log L_i - sum_{t=1}^{m} log min(t, S_i).

That update is monotone with respect to the componentwise partial order on the population simplex, so running the top state (K,0,...,0) and the bottom state (0,...,0,K) from -T with a FIXED randomness tape and doubling T until they coalesce returns a draw from the exact stationary distribution (Propp-Wilson). The randomness for the steps already simulated must be REUSED as T doubles, which is why the tape grows at its far end and is replayed oldest first; re-drawing it would destroy the perfection guarantee.

The 'approx' method is the rapidly-mixing sampler M_A of the same paper: a fixed number ceil(M(M-1)/2 log(K/eps)) of updates on uniformly random DISTINCT (not necessarily adjacent) pairs, from an arbitrary feasible start. It is not exact; the reference offers it because its running time is deterministic.

Log-space weights are kept in double, as in the reference: the split CDF is compared against a double uniform, so carrying the weights at a higher precision cannot change the sampled state. The reported mean queue length is accumulated in the working arithmetic.

Arithmetic: INEXACT BY CONSTRUCTION. The output is a random state; the balance functions are formed in the log domain.

RNG contract: see pfqn_mc_common.h. Comparable to MATLAB only in distribution, never stream for stream; reproducible within this port only when the generator is passed in the same state.

Definition in file pfqn_cftp.h.