pfqn_pas_is.h File Reference

Importance-sampling estimate of the normalizing constant of a single communicating class of a cyclic two-station pass-and-swap (P&S) network with swap graph H. More...

#include <cstddef>
#include <functional>
#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_pas_is.h:

Go to the source code of this file.

Classes
struct	line::pfqn::PasIsResult< T >
	Return value of pfqn_pas_is / pfqn_oi_is, mirroring [G, lG, Q]. More...

Namespaces
namespace	line
namespace	line::pfqn

Typedefs
template<class T>
using	line::pfqn::OiRateFun = std::function<T(const std::vector<int>&)>
	The OI rank rate of a station as a function of the per-class COUNT vector: the svcRateFun of an OI / P&S node.

Functions
Matrix< int >	line::pfqn::pas_placement (const Matrix< int > &H)
	matlab/src/api/pfqn/pas_placement.m: transitive closure of the "must precede" relation.
template<class T>
PasIsResult< T >	line::pfqn::pfqn_pas_is (const std::vector< int > &N, const std::vector< OiRateFun< T > > &mu, const Matrix< int > &H, std::size_t samples, McRng &rng, bool want_qlen=true)
	Importance-sampling estimate of the normalizing constant of a single communicating class of a cyclic two-station pass-and-swap (P&S) network with swap graph H.
template<class T>
PasIsResult< T >	line::pfqn::pfqn_pas_is (const std::vector< int > &N, const std::vector< OiRateFun< T > > &mu, const Matrix< int > &H, McRng &rng, bool want_qlen=true)
	Reference default of 1e4 samples.

Detailed Description

Importance-sampling estimate of the normalizing constant of a single communicating class of a cyclic two-station pass-and-swap (P&S) network with swap graph H.

Templated port of matlab/src/api/pfqn/pfqn_pas_is.m together with its placement-order helper matlab/src/api/pfqn/pas_placement.m, cross-checked against jar/src/main/java/jline/api/pfqn/nc/Pfqn_pas_is.java.

Model. Two order-independent stations (1 upstream, 2 downstream) hold all N jobs. With a non-empty swap graph the ordered-state chain is reducible and the recurrent communicating class D is the set of orderings that are non-decreasing with respect to H (Comte and Dorsman, 2021). Writing Phi_m for the balanced-fairness balance function,

G_C = sum_{c in D} sum_{k=0}^{ell} Phi_1(c_{1..k}) Phi_2(c_{ell..k+1}), Phi_m(q) = prod_{p=1}^{|q|} 1 / mu_m(n(q_{1..p})), n(.) = prefix counts,

which depends on the ordering only through the counts reached at each position; that is the order-independence property.

Auto-normalized IS. Orderings are drawn from D by placing, at each step, a uniformly random placement-order-minimal present class. The SAME samples feed numerator and denominator: with xi = 1 the estimate is G_C, and with xi = (number of class-r jobs in the prefix) the ratio is the mean class-r queue length at station 1. Auto-normalized IS is consistent but biased at finite sample count for the ratio Q, while G_C itself is unbiased.

Deviation from the reference, deliberate: 1/p(c) is accumulated as the product of the integer branching factors rather than as exp(-sum log na). Same number, no log/exp round trip.

Arithmetic: INEXACT BY CONSTRUCTION. The output is a random variable, so no arithmetic makes it exact; the gate is also required by lG = log(G).

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_pas_is.h.