Buzen's algorithm is an algorithm related to queueing theory used to calculate the normalization constant
G
(
N
)
{\displaystyle G(N)}
closed jackson network . (Is this true?)
First proposed by Jeffery P. Buzen in 1973.[ 1]
It can be used when
G
(
N
)
{\displaystyle G(N)}
G
(
N
)
=
∑
n
1
+
n
2
+
⋅
⋅
⋅
+
n
M
=
N
∏
i
=
1
M
f
i
(
n
i
)
{\displaystyle G(N)=\sum _{n_{1}+n_{2}+\cdot \cdot \cdot +n_{M}=N}\prod _{i=1}^{M}f_{i}(n_{i})}
f
i
(
n
)
=
y
i
n
{\displaystyle f_{i}(n)=y_{i}^{n}}
1
<
i
<=
M
{\displaystyle 1<i<=M}
f
i
(
0
)
=
1
{\displaystyle f_{i}(0)=1}
This sum can be calculated efficiently in O(MN) time by utilizing a definition with a recursive structure:
let
G
(
N
)
=
g
(
m
,
n
)
{\displaystyle G(N)=g(m,n)}
g
(
m
,
n
)
=
∑
n
1
+
n
2
+
⋅
⋅
⋅
+
n
m
=
n
∏
i
=
1
m
f
i
(
n
i
)
=
∑
n
1
+
⋅
⋅
⋅
+
n
m
−
1
=
n
,
n
m
=
0
∏
i
=
1
m
−
1
f
i
(
n
i
)
+
∑
n
1
+
⋅
⋅
⋅
+
n
m
=
n
,
n
m
>
0
∏
i
=
1
m
f
i
(
n
i
)
=
g
(
m
−
1
,
n
)
+
f
m
(
n
)
f
m
(
n
−
1
)
g
(
m
,
n
−
1
)
{\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)}
Alternative:
f
m
(
0
)
∑
n
1
+
⋅
⋅
⋅
+
n
m
−
1
=
n
,
n
m
=
0
∏
i
=
1
m
−
1
f
i
(
n
i
)
+
∑
n
1
+
⋅
⋅
⋅
+
n
m
=
n
,
n
m
>
0
∏
i
=
1
m
f
i
(
n
i
)
=
f
m
(
0
)
g
(
m
−
1
,
n
)
+
f
m
(
n
)
f
m
(
n
−
1
)
g
(
m
,
n
−
1
)
{\displaystyle f_{m}(0)\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})=f_{m}(0)g(m-1,n)+{\frac {f_{m}(n)}{f_{m}(n-1)}}g(m,n-1)}
g
(
m
,
0
)
=
1
{\displaystyle g(m,0)=1}
g
(
1
,
n
)
=
f
1
(
n
)
{\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). 
