Exact distribution of discrete-time D-BMAP/G/\inf queueing model

Tonglin Liao; Youming Li

REVIEW 3 major objections 5 minor 20 references

Exact distribution of discrete-time D-BMAP/G/\inf queueing model

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read By tracking customers who will still be in service at a fixed future time, the paper turns a non-Markovian discrete-time batch-arrival queue into a Markovian process and derives its exact time-dependent distribution.

desk verdict The central product-form formula has a one-step time-index slip and contradicts the paper's own M/M/∞ recursion; the effective-process idea is salvageable, but Theorem 2 is wrong as stated. read the letter →

arxiv 2505.23178 v1 pith:I7TDWDO5 submitted 2025-05-29 math.PR

Tonglin Liao , Youming Li This is my paper

classification math.PR MSC 60K2560J1060E10

keywords discrete-timequeueD-BMAP/G/∞infinite-servereffectiveMarkoviandynamicsprobabilitygeneratingfunctiontime-dependentdistributionM/M/∞Fanofactor

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper derives the exact time-dependent distribution of the number of customers in a discrete-time infinite-server queue where arrivals follow a batch Markovian arrival process and service times follow any distribution (the D-BMAP/G/∞ model). It does this by defining an 'effective process' that counts, at each earlier time $s$, only the customers who will still be in service at the target time $t$; that process is Markovian even though the original queue is not. The generating functions of the effective process satisfy a one-step recursion whose iteration gives a closed matrix-product formula for the distribution at time $t$. From that formula the full probability distribution and all factorial moments follow by differentiation. The result matters because it covers correlated batch arrivals and arbitrary service laws exactly, and it turns the discrete-time M/M/∞ queue into a sum of independent Bernoulli trials whose variance-to-mean ratio is below 1.

What carries the argument

The load-bearing object is the effective process $N(s;t)$, the number of customers present at time $s$ who will remain in service at the later time $t$. For fixed $t$, the pair $(I(s),N(s;t))$ built from the background chain and this effective count is Markovian in $s$: each arriving customer is retained until $t$ independently with probability $\Phi(t-s)$, the service-time survival probability. This Bernoulli-thinning fact converts the original non-Markovian queue into the vector recursion $g(z,s+1;t)=g(z,s;t)D(\Phi(t-s)z+1-\Phi(t-s))$, and iterating that recursion over $s=0,\dots,t-1$ yields the matrix product in Theorem 2. The matrix argument $\Phi(t-k)z+1-\Phi(t-k)$ is the generating function of a thinned batch: an arriving batch of size $l$ contributes to the generating function with the factor $(\Phi z+1-\Phi)^l$.

What would settle it

Run the one-slot experiment: a single certain arrival ($p=1$), service time exactly one slot, empty system at time 0, and count customers present at slot 1. The paper's Section 2 counting rule includes the customer arriving in slot 1, giving $N(1)=1$; the product formula Eq. (17) with $\alpha=0$ gives $G(z,1)=1$ and hence $N(1)=0$. That single calculation distinguishes the two slot conventions and determines whether the correct survival exponent is $\Phi(t-s)$ or $\Phi(t-s-1)$.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is Theorem 2: starting from an empty system, the vector of state-dependent generating functions at time $t$ is $$g(z,t)=p_0 \prod_{k=0}^{t-1} D(\Phi(t-k)z+1-\Phi(t-k)),$$ where $D$ is the matrix generating function of the D-BMAP and $\Phi(t)=P(Y>t)$ is the service-time survival function. The probability $p_m(t)$ of $m$ customers is the coefficient of $z^m$ in $G(z,t)=g(z,t)\mathbf{1}^T$, recovered as $(1/m!)G^{(m)}(0,t)$, and the $k$-th factorial moment is $G^{(k)}(1,t)$. For geometric service times with survival $\alpha^t$ and Bernoulli arrivals with probability $p$, the product collapses to $G(z,t)=\prod_{i=1}^t(1+p\alpha^i(z-1))$, so the discrete-time M/M/∞ count is a sum of independent, non-identically distributed Bernoulli variables; the paper emphasizes that its Fano factor (variance-to-mean ratio) is always less than 1, unlike the Poisson count of continuous-time M/M/∞.

Load-bearing premise

The entire construction rests on the Lemma 2 transition probability, which assumes a customer arriving at slot $s$ is still counted at the target time $t$ exactly when its service time is strictly larger than $t-s$, and the paper never states how that convention relates to its own rule that arrivals at slot $t$ are counted at slot $t$.

Editorial extensions

If this is right

For any finite $t$, the exact distribution $p_m(t)$ can be computed directly from derivatives at $z=0$ of the matrix product, without simulation.
All factorial moments are available as derivatives at $z=1$; the paper writes the mean and variance explicitly in terms of $\Phi$ and the arrival matrices.
The discrete-time M/M/∞ customer count is a sum of independent but non-identically distributed Bernoulli trials, and its Fano factor is below 1 at every time $t$.
Letting $t\to\infty$ in the product gives the stationary customer-number distribution for correlated batch arrivals.
Because only the survival function of the service time enters, the same formula covers any service-time law by substituting its $\Phi$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A natural extension the paper does not pursue: the same effective process should give joint distributions at several observation times, since the survival events for a fixed customer at multiple times are nested; covariance and autocorrelation of the count would then come from products of $D$ evaluated at products of survival probabilities.
In the small-slot limit, which the paper does not take, setting $p\approx\lambda\Delta t$ and $\alpha=1-\mu\Delta t$ sends $\prod_{i=1}^t(1+p\alpha^i(z-1))$ to $\exp(\lambda(1-e^{-\mu T})(z-1)/\mu)$, recovering the Poisson generating function of continuous-time M/M/∞ and making the Fano factor tend to 1.
The product form suggests a practical algorithm: with a truncated background chain, multiplying polynomial matrices in $z$ gives exact coefficients, so distributions at large $t$ could be computed by matrix-polynomial multiplication rather than Monte Carlo.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The headline is simple: the exact distribution claimed in Theorem 2 is not the distribution of the model as defined. The error is a one-step time-index slip, and the paper's own M/M/∞ example makes it visible. The effective-process construction is worth something, but this version does not support its central claim.

What is genuinely useful here is the device N(s;t), the count at time s of customers who will still be in service at time t. Lemma 1's monotonicity and Lemma 2's Markov property are clean, and the PGF update in Theorem 1 is a neat way to aggregate batch arrivals. The derivation is self-contained, and the simulation section is explicit about how to generate trajectories.

The soft spot is not a subtle one. In Lemma 2, a batch arriving during the step from s to s+1 is assigned survival probability Φ(t−s). Under Definition 1, those customers arrive at time s+1 and are counted at time t exactly when their service time Y satisfies Y > t−(s+1), i.e. with probability Φ(t−s−1), with Φ(0)=1. The paper never states an alternative convention. The slip propagates through Theorem 1, Eq. (10), and Theorem 2. In the M/M/∞ reduction, iterating the paper's own Eq. (18) from G(z,0)=1 gives G(z,1)=1+p(z−1), whereas Theorem 2's Eq. (17) gives 1+pα(z−1). The text says (18) 'finally yields' (17), but those are different functions for every 0<α<1. At t=1, Definition 1 forces the mean to be p; Theorem 2 predicts pα. That is a direct internal contradiction, not a matter of interpretation.

The numerical verification in Fig. 2 should also be re-examined, since the SSA described in Appendix A follows Definition 1 and therefore should not match Eq. (11) as written unless the implementation has the same off-by-one.

There is also a literature gap: no prior BMAP/G/∞ or M/G/∞ analytic work is cited, though the product-PGF form is the standard binomial-thinning structure. Even after the index fix, the novelty claim would need to be toned down.

My guess is the mistake is repairable: shift the survival index to Φ(t−s−1) in Lemma 2, Theorem 1, Eq. (10), and Theorem 2, and re-run the simulations. The intended result is probably true and would be a useful subfield tool. As submitted, though, the paper is not correct on its own terms. I would send it to a referee who can check the algebra and the conventions, with a clear instruction that the central identity must be verified before any acceptance; I would not desk-reject it, because the flaw is concrete and the fix is likely local. I would not cite it in its current form.

Referee Report

3 major / 5 minor

Summary. The paper proposes an effective-Markovian-dynamics method for the discrete-time D-BMAP/G/∞ queue. It defines a horizon-dependent process N(s;t), the number of customers present at time s that will still be in service at time t, proves that (I(s),N(s;t)) is Markovian, and derives a product formula for the vector of state-dependent generating functions g(z,t). From this formula the paper obtains time-dependent distributions and factorial moments, specializes to discrete-time M/M/∞, compares with the continuous-time M/M/∞ queue, and reports stochastic simulation verification.

Significance. If correct, the paper would provide a useful closed-form time-dependent generating function for a discrete-time infinite-server queue with batch Markovian arrivals and general service times, extending known results for Markovian special cases. The core idea of freezing a time horizon and conditioning on survival to that horizon is elegant, and the M/M/∞ specialization with its sub-Poissonian Fano factor is a nice observation. However, the central product formula contains an off-by-one index error that contradicts the model definition in Section 2 and the paper's own Markovian recursion in Section 5. As submitted, the announced exact distribution is not the distribution of the model as defined.

major comments (3)

[§3, Lemma 2 / §4, Theorem 2] Eq. (6) uses Φ(t−s) for arrivals during the transition from s to s+1, but under Definition 1 a customer arriving in that transition arrives at time slot s+1 and is counted at time t iff Y > t−(s+1); the survival probability should be Φ(t−s−1). Theorem 2 and Eq. (10) inherit this shift, so Eq. (11) is not the generating function of the model defined in Section 2. The error is visible in the M/M/∞ case: Eq. (17) gives G(z,1)=1−pα+pαz and stationary mean pα/(1−α), whereas Definition 1 and the recursion in Eq. (18) give G(z,1)=1−p+pz, and Little's law gives mean p/(1−α). Replacing Φ(t−s) with Φ(t−s−1) in Eq. (6), Theorem 1, Eq. (10), Theorem 2, and the moment formulas (14) appears to repair the derivation.
[§5, Eq. (18)] The claim that Eq. (18) 'finally yields' Eq. (17) is arithmetically false. Iterating Eq. (18) from G(z,0)=1 gives G(z,1)=1−p+pz and G(z,2)=(1−pα+pαz)(1−p+pz), while Eq. (17) gives G(z,1)=1−pα+pαz and G(z,2)=(1−pα+pαz)(1−pα²+pα²z); these differ for every 0<p<1 and 0<α<1. Thus the paper's own Markovian recursion contradicts the main theorem, and Section 5 cannot be used to validate it.
[Appendix A] The SSA description is ambiguous about the time slot assigned to arrivals in the transition from s to s+1. If they are assigned time s, the simulation is consistent with Eq. (11) but contradicts Definition 1; if they are assigned time s+1, it is consistent with Definition 1 but contradicts Eq. (11). Because the convention is never stated, the agreement in Fig. 2 cannot be interpreted as verification of the model defined in Section 2.

minor comments (5)

[§2, Definition 1] There is a typo: 't+ s − 1. but' should read 't+ s − 1, but'; also clarify whether an arrival at 'time slot t' is first counted at the slot boundary t or during the interval (t−1,t].
[§3, Lemma 2 proof] The phrase 'service time much be strictly larger' should read 'service time must be strictly larger'.
[§4, Theorem 1 proof] The word 'evalutated' should be 'evaluated'.
[§2] The text says inter-arrival and service times are non-negative integer-valued, but Definition 1 takes service times in {1,2,...}; please make the support conditions consistent.
[§4, Eq. (14)] The notation D^{(l_i)} is used without definition; please state explicitly that it denotes the l_i-th derivative of the matrix generating function D(z).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the time-dependent generating-function derivation is self-contained and independently checked.

full rationale

The central derivation (Lemma 2, Theorem 1, Theorem 2) starts from the two explicitly stated inputs—the D-BMAP generating function D(z) and the service-time survival function Φ(t)—and recursively propagates state-dependent generating functions for the effective process. No parameter is fitted to the quantity being predicted, and the M/M/∞ reduction in Section 5 is an independent consistency check rather than an input to the derivation. The only self-citation is reference [19], which is cited as naming the 'effective Markovian dynamics' idea, but the paper itself proves the Markov property in Lemma 2 and does not rely on any unverified result from that preprint. Any suspected one-slot index inconsistency in Lemma 2 (Φ(t−s) versus Φ(t−s−1)) would be a mathematical correctness issue affecting the claim's validity, not a circularity issue, because the formula is derived directly from the definitions and then compared with an independent recursion. Thus the paper does not reduce to its own conclusions by construction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

No parameters are fitted to data; p and α in the examples are model parameters, not free parameters. The central claim rests on the D-BMAP definition, the i.i.d. service-time assumption, the empty-initial-state assumption, and standard PGF algebra. The only introduced mathematical object is the effective process, which is a standard analytic device.

assumptions (4)

domain assumption The arrival process is a D-BMAP with matrix generating function D(z) (Definition 2); its transition matrices D_l determine the batch arrival probabilities.
This is the model definition in Section 2; the central derivation assumes the product structure of D(z).
domain assumption Service times are i.i.d., independent of the arrival process, with survival function Φ(t) = P(Y > t) (Definition 1).
Used in Lemma 2 for binomial thinning of batches.
domain assumption The queue is empty at time 0.
Explicitly assumed in Section 2 to avoid residual service-time information.
standard math Binomial and PGF manipulations, including the product rule for matrices with non-commuting factors.
Used in the proof of Theorem 1 and in the moment formulas (Eq. (14)).

invented entities (1)

Effective process N(s;t)
purpose: Number of customers present at time s whose service extends past time t; used to restore Markovianity.
A mathematical device (classical thinning/bridge construction), not a physical entity; it has no independent falsifiable handle outside the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Exact distribution of discrete-time D-BMAP/G/\inf queueing model." pith.science (2026). https://pith.science/paper/I7TDWDO5

@misc{pith2026250523178,
  author       = {Pith},
  title        = {Pith review of: Exact distribution of discrete-time D-BMAP/G/\inf queueing model},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/I7TDWDO5}},
  note         = {Machine review of arXiv:2505.23178}
}

read the original abstract

In this paper, we consider discrete-time D-BMAP/G/\inf queueing model. We construct effective discrete-time Markovian dynamics for this model and utilize it to derive exact time-dependent distribution of customer number and the corresponding moments for the original queueing model. Numerical simulations are used to verify our results. Using our result, we provide analytical distribution for discrete-time M/M/\inf, and then compare it with the distribution of continuous-time M/M/\inf.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[1]

New Journal of Mathematics, Series B 20, 33–39 (1909)

Erlang, A.K.: The theory of probabilities and telephone conversations. New Journal of Mathematics, Series B 20, 33–39 (1909)

work page 1909
[2]

Springer, New York (2014)

Nazarov, A., Yakupov, R., Gortsev, A.: Information Technologies and Mathemat- ical Modelling. Springer, New York (2014)

work page 2014
[3]

International Conference on Information Technologies and Mathematical Mod- elling, 195–212 (2018)

Kerobyan, K., Covington, R., Kerobyan, R., Enakoutsa, K.: An infinite-server queueing model in semi-markov random environment subject to catastrophes. International Conference on Information Technologies and Mathematical Mod- elling, 195–212 (2018)

work page 2018
[4]

Biophysical Journal 122(20), 4023–4041 (2023)

Shi, C., Yang, X., Zhang, J., Zhou, T.: Stochastic modeling of the mrna life process: A generalized master equation. Biophysical Journal 122(20), 4023–4041 (2023)

work page 2023
[5]

Physical Review E 110(3), 034413 (2024)

Shi, C., Yang, X., Zhou, T., Zhang, J.: Nascent rna kinetics with complex pro- moter architecture: Analytic results and parameter inference. Physical Review E 110(3), 034413 (2024)

work page 2024
[6]

Biophysical Journal (2024)

Szavits-Nossan, J., Grima, R.: Solving stochastic gene expression models using queueing theory: a tutorial review. Biophysical Journal (2024)

work page 2024
[7]

Communications in Statistics

Lucantoni, D.M.: New results on the single server queue with a batch marko- vian arrival process. Communications in Statistics. Stochastic Models 7(1), 1–46 (1991)

work page 1991
[8]

Statistics & Probability Letters 133, 42–49 (2018)

Cao, J., Xie, W.: Joint arrival process of multiple independent batch markovian arrival processes. Statistics & Probability Letters 133, 42–49 (2018)

work page 2018

Show all 20 references

[9]

Addison-Wesley Longman Publishing Co., Inc., Reading (1986) 14

Schwartz, M.: Telecommunication Networks: Protocols, Modeling and Analysis. Addison-Wesley Longman Publishing Co., Inc., Reading (1986) 14

1986
[10]

Journal of Applied Probability 16(4), 764–779 (1979)

Neuts, M.F.: A versatile markovian point process. Journal of Applied Probability 16(4), 764–779 (1979)

1979
[11]

Operations Research 6(1), 96–105 (1958)

Meisling, T.: Discrete-time queuing theory. Operations Research 6(1), 96–105 (1958)

1958
[12]

Reliability: Theory & Applications 18(4 (76)), 355–371 (2023)

Harini, R., Indhira, K.: A literature review on discrete-time queueing models. Reliability: Theory & Applications 18(4 (76)), 355–371 (2023)

2023
[13]

In: 2016 IEEE 83rd Vehicular Technology Conference (VTC Spring), pp

Wu, Y., Zheng, Y., Feng, Y., Zhao, Y., Fang, X.: End-to-end performance opti- mization of tandem queuing for high-speed train networks. In: 2016 IEEE 83rd Vehicular Technology Conference (VTC Spring), pp. 1–5 (2016)

2016
[14]

Queueing Systems 64, 69–102 (2010)

Saffer, Z., Telek, M.: Unified analysis of BMAP/G/1 cyclic polling models. Queueing Systems 64, 69–102 (2010)

2010
[15]

Hunter, J.J.: Mathematical Techniques of Applied Probability: Discrete Time Models: Basic Theory vol. 1. Academic Press, New York (2014)

2014
[16]

Queueing Systems 18, 183–197 (1994)

Takagi, H., Leung, K.K.: Analysis of a discrete-time queueing system with time- limited service. Queueing Systems 18, 183–197 (1994)

1994
[17]

Computers & Industrial Engineering 61(4), 1226–1232 (2011)

Wang, J., Huang, Y., Dai, Z.: A discrete-time on–off source queueing system with negative customers. Computers & Industrial Engineering 61(4), 1226–1232 (2011)

2011
[18]

Journal of the Operational Research Society 71(8), 1145–1160 (2020)

Worthington, D., Utley, M., Suen, D.: Infinite-server queueing models of demand in healthcare: A review of applications and ideas for further work. Journal of the Operational Research Society 71(8), 1145–1160 (2020)

2020
[19]

bioRxiv, 2024–12 (2024)

Li, Y., Jia, C.: Effective markovian dynamics method of solving non-markovian dynamics of stochastic gene expression. bioRxiv, 2024–12 (2024)

2024
[20]

Journal of The Royal Society Interface 20(208), 20230467 (2023) 15

Wang, X., Li, Y., Jia, C.: Poisson representation: a bridge between discrete and continuous models of stochastic gene regulatory networks. Journal of The Royal Society Interface 20(208), 20230467 (2023) 15

2023

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

New Journal of Mathematics, Series B 20, 33–39 (1909)

Erlang, A.K.: The theory of probabilities and telephone conversations. New Journal of Mathematics, Series B 20, 33–39 (1909)

work page 1909

[2] [2]

Springer, New York (2014)

Nazarov, A., Yakupov, R., Gortsev, A.: Information Technologies and Mathemat- ical Modelling. Springer, New York (2014)

work page 2014

[3] [3]

International Conference on Information Technologies and Mathematical Mod- elling, 195–212 (2018)

Kerobyan, K., Covington, R., Kerobyan, R., Enakoutsa, K.: An infinite-server queueing model in semi-markov random environment subject to catastrophes. International Conference on Information Technologies and Mathematical Mod- elling, 195–212 (2018)

work page 2018

[4] [4]

Biophysical Journal 122(20), 4023–4041 (2023)

Shi, C., Yang, X., Zhang, J., Zhou, T.: Stochastic modeling of the mrna life process: A generalized master equation. Biophysical Journal 122(20), 4023–4041 (2023)

work page 2023

[5] [5]

Physical Review E 110(3), 034413 (2024)

Shi, C., Yang, X., Zhou, T., Zhang, J.: Nascent rna kinetics with complex pro- moter architecture: Analytic results and parameter inference. Physical Review E 110(3), 034413 (2024)

work page 2024

[6] [6]

Biophysical Journal (2024)

Szavits-Nossan, J., Grima, R.: Solving stochastic gene expression models using queueing theory: a tutorial review. Biophysical Journal (2024)

work page 2024

[7] [7]

Communications in Statistics

Lucantoni, D.M.: New results on the single server queue with a batch marko- vian arrival process. Communications in Statistics. Stochastic Models 7(1), 1–46 (1991)

work page 1991

[8] [8]

Statistics & Probability Letters 133, 42–49 (2018)

Cao, J., Xie, W.: Joint arrival process of multiple independent batch markovian arrival processes. Statistics & Probability Letters 133, 42–49 (2018)

work page 2018