Package jline.api.pfqn.nc

Class Pfqn_ld_is

java.lang.Object
jline.api.pfqn.nc.Pfqn_ld_is
public final class Pfqn_ld_is extends Object
Importance-sampling (IS) estimate of the normalizing constant of a closed LOAD-DEPENDENT product-form queueing network. Load-dependent counterpart of Pfqn_pas_is /
invalid reference 
Pfqn_oi_is
: the same sample-an-ordering estimator, with the order-independent rank rate replaced by the load-dependent capacity.

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),
since the multiset has |n|!/prod_r(n_r!) orderings and each contributes the same ordered product. The delay (infinite-server) node is the special case mu_Z(k) = k, giving F_Z(n) = prod_r Z_r^{n_r}/n_r!; a single-server queue is mu_i(k) = 1; a c-server queue is mu_i(k) = min(k,c).

Consequently, writing ell = sum(N) and letting a "cut vector" split an ordering c of all ell jobs into S contiguous segments (one per station), 

   G(N) = sum_{c} sum_{cuts} prod_{m=1}^{S} w_m(seg_m),
   w_m(q) = prod_{p=1}^{|q|} L(m,q_p) / mu_m(p),
because summing over the orderings of each segment independently reproduces prod_m F_m(n_m), and each count split (n_1,...,n_S) is realized exactly once.

Estimator. An ordering c is drawn by placing, at each step, a uniformly random present class; p(c) is the product of the reciprocal branching factors. For the sampled c the inner sum over ALL cut vectors is computed exactly by the dynamic program 

   A_0(0) = 1,   A_m(k) = sum_{j=0}^{k} A_{m-1}(j) * w_m(c_{j+1..k}),
so S(c) = A_S(ell) in O(S*ell^2) time (no cut enumeration). Then G = E_{C~p}[ S(C) / p(C) ] is unbiased and is estimated by the sample mean.

Port of matlab/src/api/pfqn/pfqn_ld_is.m.

See Also:

  • Method Details

    • pfqn_ld_is

      public static Ret.pfqnNc pfqn_ld_is(Matrix L, Matrix N, Matrix Z, Matrix mu, SolverOptions options)
      Importance-sampling estimate of the load-dependent normalizing constant.
      Parameters:
      L - (M x R) per-class service demands at the M queueing stations.
      N - (1 x R) closed population vector, finite.
      Z - (1 x R) aggregated think time (delay) demand; null or zeros if none.
      mu - (M x ell) load-dependent capacities, mu(i,k) the capacity of station i holding k jobs; null for the load-independent case mu(i,k)=1 (see Pfqn_is). Shorter rows are extended with their last capacity.
      options - solver options; uses options.samples (number of IS samples) and options.seed (RNG seed for reproducibility).
      Returns:
      G and lG = log(G).