Buzen's algorithm

Buzen's algorithm is an algorithm related to queueing theory used to calculate the normalization constant ${\displaystyle G(N)}$ for a closed network. (Is this true?)

First proposed by Jeffery P. Buzen in 1973.^[1]

It can be used when ${\displaystyle G(N)}$ is of the form:

${\displaystyle G(N)=\sum _{n_{1}+n_{2}+\cdot \cdot \cdot +n_{M}=N}\prod _{i=1}^{M}f_{i}(n_{i})}$ with ${\displaystyle f_{i}(n)=y_{i}^{n}}$ for ${\displaystyle 1<i<=M}$ (We also require ${\displaystyle f_{i}(0)=1}$, right?)

This sum can be calculated efficiently in O(MN) time by utilizing a definition with a recursive structure:

Further information: dynamic programming

let ${\displaystyle G(N)=g(m,n)}$

${\displaystyle g(m,n)=\sum _{n_{1}+n_{2}+\cdot \cdot \cdot +n_{m}=n}\prod _{i=1}^{m}f_{i}(n_{i})=\sum _{n_{1}+\cdot \cdot \cdot +n_{m-1}=n,n_{m}=0}\prod _{i=1}^{m-1}f_{i}(n_{i})+\sum _{n_{1}+\cdot \cdot \cdot +n_{m}=n,n_{m}>0}\prod _{i=1}^{m}f_{i}(n_{i})=g(m-1,n)+{\frac {f_{m}(n)}{f_{m}(n-1)}}g(m,n-1)}$ (Is this last bit true?)

${\displaystyle g(m,0)=1}$, ${\displaystyle g(1,n)=f_{1}(n)}$

References

^ Buzen, Jeffrey (1973). "Computational algorithms for closed queueing networks with exponential servers". Communications of the ACM. 16 (9). {{cite journal}}: Unknown parameter |month= ignored (help) (Confirm? Expand?)