Buzen's algorithm is an algorithm related to queueing theory used to calculate the normalization constant
G
(
N
)
{\displaystyle G(N)}
closed jackson network . This constant is used when analyzing these networks, alternatively Mean-value analysis can be used to avoid having to compute the normalization constant. This method was first proposed by Jeffery P. Buzen in 1973.[ 1]
The motivation for this algorithm is the result of the combinatorial explosion of the number of states that the system can be in.
Derivation
G
(
N
)
=
g
(
M
,
N
)
{\displaystyle G(N)=g(M,N)}
g
(
m
,
n
)
{\displaystyle g(m,n)}
=
∑
n
1
+
⋅
⋅
⋅
+
n
m
=
n
∏
i
=
1
m
f
i
(
n
i
)
{\displaystyle =\sum _{n_{1}+\cdot \cdot \cdot +n_{m}=n}\prod _{i=1}^{m}f_{i}(n_{i})}
=
∑
j
=
0
n
∑
n
1
+
⋅
⋅
⋅
+
n
m
−
1
=
n
−
j
,
n
m
=
j
∏
i
=
1
m
f
i
(
n
i
)
{\displaystyle =\sum _{j=0}^{n}\sum _{n_{1}+\cdot \cdot \cdot +n_{m-1}=n-j,n_{m}=j}\prod _{i=1}^{m}f_{i}(n_{i})}
=
∑
j
=
0
n
f
m
(
j
)
∑
n
1
+
⋅
⋅
⋅
+
n
m
−
1
=
n
−
j
∏
i
=
1
m
−
1
f
i
(
n
i
)
{\displaystyle =\sum _{j=0}^{n}f_{m}(j)\sum _{n_{1}+\cdot \cdot \cdot +n_{m-1}=n-j}\prod _{i=1}^{m-1}f_{i}(n_{i})}
=
∑
j
=
0
n
f
m
(
j
)
g
(
m
−
1
,
n
−
j
)
{\displaystyle =\sum _{j=0}^{n}f_{m}(j)g(m-1,n-j)}
g
(
m
,
0
)
=
1
{\displaystyle g(m,0)=1}
g
(
1
,
n
)
=
f
1
(
n
)
{\displaystyle g(1,n)=f_{1}(n)}
This recursive relationship allows for the calculation of all
G
(
N
)
{\displaystyle G(N)}
order
O
(
M
N
2
)
{\displaystyle O(MN^{2})}
There is a more efficent algorithm for finding
G
(
N
)
{\displaystyle G(N)}
f
i
>
1
(
n
)
=
c
i
y
i
n
{\displaystyle f_{i>1}(n)=c_{i}y_{i}^{n}}
g
(
m
,
n
)
{\displaystyle g(m,n)}
=
∑
j
=
0
n
f
m
(
j
)
g
(
m
−
1
,
n
−
j
)
{\displaystyle =\sum _{j=0}^{n}f_{m}(j)g(m-1,n-j)}
=
f
m
(
0
)
g
(
m
−
1
,
n
)
+
∑
j
=
1
n
f
m
(
j
)
g
(
m
−
1
,
n
−
j
)
{\displaystyle =f_{m}(0)g(m-1,n)+\sum _{j=1}^{n}f_{m}(j)g(m-1,n-j)}
=
f
m
(
0
)
g
(
m
−
1
,
n
)
+
y
m
∑
j
=
1
n
−
1
f
m
(
j
)
g
(
m
−
1
,
n
−
1
−
j
)
{\displaystyle =f_{m}(0)g(m-1,n)+y_{m}\sum _{j=1}^{n-1}f_{m}(j)g(m-1,n-1-j)}
=
f
m
(
0
)
g
(
m
−
1
,
n
)
+
y
m
g
(
m
,
n
−
1
)
{\displaystyle =f_{m}(0)g(m-1,n)+y_{m}g(m,n-1)}
This simpler recursive relationship allows for the calculation of all
G
(
n
)
{\displaystyle G(n)}
O
(
M
N
)
{\displaystyle O(MN)}
Implementation
===Further
References
^ Buzen, Jeffrey (1973). "Computational algorithms for closed queueing networks with exponential servers". Communications of the ACM . 16 (9).[1] (Confirm and expand references?)
