Joint probability of the per-station TOTAL queue lengths. More...

#include <algorithm>
#include <cstddef>
#include <string>
#include <vector>
#include "line/api/perm/perm_approx.h"
#include "line/api/perm/perm_sampling.h"
#include "line/api/pfqn/pfqn_ca.h"
#include "line/api/pfqn/pfqn_perm.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for pfqn_jointmarg.h:

Namespaces
namespace	line
namespace	line::pfqn

Functions
template<class T>
T	line::pfqn::pfqn_jointmarg (const std::vector< int > &n, const Matrix< T > &L, const std::vector< int > &N, const std::vector< std::size_t > &infset, const T &G, const std::string &engine="exact", std::uint64_t seed=0)
	Joint probability of the per-station TOTAL queue lengths.
template<class T>
T	line::pfqn::pfqn_jointmarg (const std::vector< int > &n, const Matrix< T > &L, const std::vector< int > &N, const std::vector< std::size_t > &infset, const std::string &engine="exact", std::uint64_t seed=0)
	Overload computing G with pfqn_ca first, matching the reference's default.

Detailed Description

Joint probability of the per-station TOTAL queue lengths.

Templated port of matlab/src/api/pfqn/pfqn_jointmarg.m, of jline.api.pfqn.Pfqn_jointmarg and of python pfqn_jointmarg.

Joint probability that station i holds n(i) jobs IN TOTAL, all classes summed out, in a closed multiclass product-form network:

P(n_1,...,n_M) = perm(A) / ( prod_r N_r! * prod_{j in INFSET} n_j! * G(N) )

with A the demand matrix whose column r is repeated N_r times and whose row i is repeated n_i times, so A is square of order sum(N).

HOW THIS DIFFERS FROM pfqn_joint_total, which is the same identity with the delay taken as ONE aggregated row: here every infinite-server station keeps its own row and contributes its own 1/n_j!. The queueing stations contribute the n_i! that the permanent identity supplies; the infinite servers do not. Dividing once, as a single aggregated delay row would, leaves the law unnormalized as soon as the model has two delays.

The identity holds for load-independent single-server queues plus infinite servers. Multiserver and load-dependent stations break the n_i! factor and are the caller's responsibility to exclude (see solver_nc_jointmarg).

ZERO ELEMENTS are safe under the exact engine and only under it: a station holding no jobs contributes no row, a class with no jobs contributes no column, a zero demand is an ordinary zero entry of A, and the permanent of the empty matrix is 1. The approximate engines are REFUSED on a matrix with a structural zero rather than having it floored at eps: Sinkhorn scaling needs full support, and the Bethe gap is a state-dependent lower bound that does not cancel when the estimates are normalized against each other.

Arithmetic: EXACT-CAPABLE on the "exact" engine, which reaches pfqn_perm and uses additions, multiplications and exact binomials only. The four approximate engines are double-precision Monte Carlo or message passing, so they collapse an exact T to double before running.

Reference: H. J. Ryser, "Combinatorial Mathematics", Carus Mathematical Monographs 14, Mathematical Association of America, 1963.

Definition in file pfqn_jointmarg.h.

Namespaces

Functions

Detailed Description