Buzen's algorithm: Difference between revisions

Revision as of 04:37, 19 March 2006

Revision as of 17:42, 19 March 2006

Line 1:

==Buzen's algorithm==

Buzen's algorithm is an algorithm related to [[queueing theory]] used to calculate the [[normalization constant]] <math>G(N)</math> for a [[closed jackson network]]. (Is this true?)

First proposed by [[Jeffery P. Buzen]] in 1973.<ref name="buzen-1973">{{cite journal

Line 12:

| volume = 16

| issue = 9

}} (Confirm? Expand?)</ref>

It can be used when <math>G(N) = g(M, N)</math> is of the form:

{|

<math>G(N) = \sum_{n_1 + n_2 + \cdot\cdot\cdot + n_M = N} \prod_{i=1}^M f_i( n_i )</math> with <math>f_i( n ) = y_i^n</math> for <math>1 < i <= M</math> (We also require <math>f_i( 0 ) = 1</math>, right?)

|-

|<math>g(m, n)</math>

|<math>= \sum_{n_1 + \cdot\cdot\cdot + n_m = n} \prod_{i=1}^m f_i( n_i )</math>

|-

|

|<math>= \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 )</math>

|-

|

|<math>= \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 )</math>

|-

|

|<math>= \sum_{j=0}^n f_m( j ) g( m-1, n-j )</math>

|}

<math>g(m, 0) = f_m( 0 )</math> (Confirm?)

This sum can be calculated efficiently in O(MN) time by utilizing a definition with a recursive structure: {{see|dynamic programming}}

let <math>Gg(N1, n) = gf_1(m, n )</math>

This recursive relationship allows for all <math>G(N)</math> up to any value of N in [[Big O notation|order]] <math>O(MN^2)</math> time.

<math>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)</math> (Is this last bit true?)

There is a more efficent algorithm for finding <math>G(N)</math> for some network. If we assume that <math>f_{i>1}( n ) = cy_i^n</math>, then the recursive relationship can be simplified as follows:

Alternative:

{|

<math>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)</math>

|-

|<math>g(m,n)</math>

|<math>= \sum_{j=0}^n f_m( j ) g( m-1, n-j )</math>

|-

|

|<math>= f_m( 0 ) g( m-1, n ) + \sum_{j=1}^n f_m( j ) g( m-1, n-j )</math>

|-

|

|<math>= f_m( 0 ) g( m-1, n ) + y_m \sum_{j=1}^{n-1} f_m( j ) g( m-1, n-1-j)</math>

|-

|

|<math>= f_m( 0 ) g( m-1, n ) + y_m g( m, n-1 )</math>

|}

This simpler recursive relationship allows for all <math>gG(m,0n) = 1</math>, up to any value of N to be found in order <math>gO(1, n) = f_1(nMN)</math> time.

===References===

<references/>

(Confirm and expand references?)