Buzen's algorithm: Difference between revisions

Revision as of 22:36, 17 January 2013

Revision as of 22:49, 17 January 2013

Line 14:

Buzen's algorithm is an efficient method to compute G(''N'').<ref name="buzen-1973" />

==Algorithm description==

Write g(''N'',''M'') for the normalising constant of a closed queueing network with ''N'' circulating customers and ''M'' service stations. The algorithm starts by noting<ref name="buzen-1973" />

: <math>g(0, m) = 1 \text{ for }m=1,2,\cdots,M</math>

: <math>g(n, 1) = (X_1)^n \text{ for }n=0,1,\cdots,N</math>

and solving for the ''X''_''i''. The recurrence relation<ref name="buzen-1973" />

&: <math>g(n, m) = g(n,m-1)+X_m g(n-1,m).</math>

is used to compute a grid of values. The sought for value G(''N'')&nbsp;=&nbsp;g(''N'',''M'').<ref name="buzen-1973" />

==Marginal distributions, expected number of customers==

Line 21 ⟶ 30:

:<math>P(n_i = k) = \frac{X_i^k}{G(N)}[G(N-k) - X_i G(N-k-1)]</math>

and the expected number of customers at facility ''i'' by

:<math>E[n_i] = \sum_{k=1}^N X_i^k \frac{G(N-k)}{G(N)}.</math>

Note that these expressions also involve G. It is in the evaluation of these expressions that the algorithm is useful.

==Derivation==

The algorithm computes not just ''G'' but a two-dimensional function

: <math>g(n,m) \text{ for }n=0,1,\cdots,N \text{ and }m=1,\cdots,M</math>.

Once the calculation ends the values we are interested in are found by

:<math> G(n) = g(n,M) \text{ for }n=0,1,\cdots,N</math>.

The definition of ''g'' and a recursive method of calculating it are as follows

:<math>

\begin{align}

g(n, m) & = \sum_{n_1 + \cdots + n_m = n} \prod_{i=1}^m (X_i)^{n_i} \\

& = \sum_{(n_1 + \cdots + n_m = n) \wedge (n_m=0)}^n \prod_{i=1}^m (X_i)^{n_i} +

\sum_{(n_1 + \cdots + n_m = n) \wedge (n_m>0)}^n \prod_{i=1}^m (X_i)^{n_i} \\

& = g(n,m-1)+X_m g(n-1,m)

\end{align}

</math>

Also

: <math>g(n, 1) = (X_1)^n \text{ for }n=0,1,\cdots,N</math>

and

: <math>g(0, m) = 1 \text{ for }m=1,2,\cdots,M</math>

This recursive relationship allows for the calculation of all ''G''(''N'') up to any value of ''N'' in [[Big O notation|order]] O(''MN'') time.

==Implementation==