pfqn_ld_is.h File Reference

Importance-sampling estimate of the normalizing constant of a closed LOAD-DEPENDENT product-form network. More...

#include <cstddef>
#include <vector>
#include "line/api/pfqn/pfqn_ca.h"
#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_ld_is.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::pfqn

Functions
template<class T>
NcResult< T >	line::pfqn::pfqn_ld_is (const Matrix< T > &L, const std::vector< int > &N, const std::vector< T > &Z, const Matrix< T > &mu, std::size_t samples, McRng &rng)
	Importance-sampling estimate of the normalizing constant of a closed LOAD-DEPENDENT product-form network.
template<class T>
NcResult< T >	line::pfqn::pfqn_ld_is (const Matrix< T > &L, const std::vector< int > &N, const std::vector< T > &Z, const Matrix< T > &mu, McRng &rng)
	Reference default of 1e4 samples.

Detailed Description

Importance-sampling estimate of the normalizing constant of a closed LOAD-DEPENDENT product-form network.

Templated port of matlab/src/api/pfqn/pfqn_ld_is.m, cross-checked against jar/src/main/java/jline/api/pfqn/nc/Pfqn_ld_is.java.

Identity. Every product-form station's balance function is the sum, over the orderings q of a given per-class count vector n, of an ordered product of a per-position factor,

F_i(n) = |n|!/prod_r(n_r!) prod_r L(i,r)^{n_r} / prod_{k=1}^{|n|} mu_i(k) = sum_{q: |q| = n} prod_{p=1}^{|n|} L(i,q_p) / mu_i(p),

so with ell = sum(N) and a cut vector splitting an ordering c of all ell jobs into S contiguous segments (one per station),

G(N) = sum_c sum_{cuts} prod_m prod_p L(m, seg_m(p)) / mu_m(p).

The delay is the station with mu_Z(k) = k, a single server is mu_i(k) = 1 and a c-server queue is mu_i(k) = min(k,c).

Estimator. An ordering c is drawn by placing a uniformly random present class at each step; for the sampled c the inner sum over ALL cut vectors is evaluated EXACTLY by the dynamic program A_0(0) = 1, A_m(k) = sum_{j<=k} A_{m-1}(j) w_m(c_{j+1..k}), in O(S ell^2). The estimate is the sample mean of A_S(ell)/p(c), which is unbiased for G(N).

Deviation from the reference, deliberate: MATLAB accumulates log p(c) and multiplies by exp(-logp). Here 1/p(c) is accumulated directly as the product of the integer branching factors, which is the same number computed without a log/exp round trip and is exact in every arithmetic. The two agree to rounding in double.

Arithmetic: INEXACT BY CONSTRUCTION. The estimator's output is a random variable whose value depends on the drawn orderings, so no arithmetic makes it exact; it is gated on has_transcendental because it reports lG = log(G) and because the sampler itself needs a real-valued uniform stream.

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