UNIVERSITY OF 

ILLINOIS LIBRARY 

AT URBANACHAMPAIGN 

BOOKSTACKS 



Digitized by the Internet Archive 

in 2011 with funding from 

University of Illinois Urbana-Champaign 



http://www.archive.org/details/generalizedgeome349evan 



Faculty Working Papers 



GEHERALIZED GEOMETRIC STRUCTURE OF THE MARGINAL 

r::~. :_"::::. 5 ::; zvi.:: ?y.:::_ : s;; 



Richard V. Evans 
#349 



College of Commerce and Business Administration 

University of Illinois at Urbana-Champaign 



• 



FACULTY WORKING PAPERS 
College of Commerce and Business Administration 
University of Illinois at Urbana-Champaign 

October 29, 1976 



GENERALIZED GEOIIETRIC STRUCTURE OF THE MARGINAL 
DISTRIBUTIONS IN EVENT PROCESSES 



Richard V. Evans 
#349 



ca3 : ■ . ctur< >f the Marginal 

:)istri: 



Richard V. Evans 
ifessor, Business Administration 



Suire;ia_ry: The states of vector valuei ■ ■ tion processes with nearesi ■ Lghbor 

transitions are divided into : sequenct of sets A.. The marginal distributions 

i 

i ifi i 

G are divided into a fai '< I ia! dG ' = L,(dG ). Re- 

t t t i t 

cursive calculations pi the form oi hi Linear fun< : ions L and thi 

, o 
indary cunt c Lor dG. . 
t 



This paper coni es the study of a genera] family of congestion processes 

[2], The state of the system led ectoi N(t), Wit). N(t) is a 

finite dimens on;:. tor wit;, non i nates. W(t) is a 

k dimensional vector of ela ; lossible intervals wmch 

may be in process at time t. ich value N(t) a k dimensional vector 

S is defined. ft ha i 1 in th> i the i th type interval 

n 

is in progress when N(t) = n rad »l I l(t) = n and no interval 

terminates in t to t + r , W(t + T ) = W(t) + i S . Each of the i th type inter- 
vals is assumed to be a random variable with disl i Lbution function F^t) ,F i (0)=0, 
continuous density f.(t),and a finite mean. If ,m event of type i occurs 
when N(t) = n and W(t) = w there is a change in the value of N(r) from n to u' 
and w becomes w' according to a set of routing probabilities u.(n,w,n ,w' ) 
which are continuous from the right in w and sum to i for each i,n, and w, 
The i th coordinate of w' becomes indicat Lng that either a new interval of 
the. ith type is begun or that when N(t) = n no interval of type i is in 
process. In addition this change me i ■, I the j th type interval so that 

w" . = or it mav interrupt the interval so that the j th coordinate of S .is 
j n 

is and w . : w.. The I mge to a' nay be - ; s ^ or continuation of 
J J 

anj number of intervals «rhi • ■ in process or suspended while 

N(t) = n. Final] utii Ltif Ltive only for n for 

which |n"-nj = 1 v Jute values of the 

tdinates. This is the >• - Lon which is the basis of 
the analysis. 

This papei will examine rgi tions of the process which 

often provide su: i ..cess. Let 

these distributions be G (n,w) the prob bility that N(t) = n 

and W(t) is approximately w. The ev i ur< provides a simple justifica- 

■■n for a recursive relal Lou hip l - first used in 



-2- 

queuing by Winsten [5] and Chen by Evan: i 
Sets of stale s 

To use the n< > at Lghboi pro erl , I Lrst the possible values of N(t), 

W(t) are divided into sets A., i = 0, ... These sets must have the property 

that if N(t), W(t) £ A. then rva2 (o,t) must: have 

occureci at some time a .'. . . , The fact 

that except for a set of pi finite number of events in 

(o,t) guarantees that to th< < iei tuusl I a last event in (o,t) 

[2 J. This combined wit >robabilities are 

oniy positive for pairs of values hii h i— n" L, makes the 
construction of a family ol -. ; £ feasible Even Ln ■ ;•> i 11 Lc models there 

may not bean obvious unique partition. ;ibilii , - with A containing 

the value n=0 and then defines A. = {n,w| , n-n for some n " s A, ,1. 



i 



-1 



Another possibility is A ={n,w| i rordin ti of n is 0i- and then 

o 

us*- the same inductive del Lnil :n oi i.. . 

l 

Tter at ive Rela tic n is] i 

The probability equati based on deco i can; Ltion from n,v 

A ar time ; : to n'. w'i A. at time n ord ti the possible 

o i 

number of events j Ln : Ln1 • ■ |uence of j events ; 

d o • an . he evei causes the last 

departure fro n A , t t.S be k + ' 

wh ii i ur ie t . fi 

P^(n,w,n \w ") = ... ■ ■,w*,n'*,w'*)d 

k=0 r w . , 

where 

P (n,w,n ,w) i Ltion from n, w at 

to n' and appro^ ' .-■ ' at t 



-3- 



anci 

Q 1 ' (n*,w*,n',w') alii of " event transition from 

a* ,w* t A , Li i . . i tls (o,dt) to 

A. at t wi t ho ut 

1 

> St. i ■ d ; , t ) 

The existence of u 1 1 c: ^ ^ probabi Lit: ; does i Lfficull ies since they 

involve appropri finite number of i/als. Summing over 

j produces 

■*' i 

>; P J (n,w,n',w') = I C (n,w,n*,w (n*,w*,n' ,w")dT 

j=0 C j=0 k=Q i w* u* \. , ' 

i - 1 

Reversing the summation operations produces 

- .- i - ^ 

P (n,w.n w ) = . / Y. P (n,w,n*,w*) (n*,w*,n ,w ) d'e 

t . . . L— I 

■ w* n 7r tA. , t 
l-l 

v. 

rfhere ? = ii P J and = 5 1 ' ' 

t . r t: t-T "t-i 

j=0 a=0 

Assuming dC (n,w) > only foi n w A this result can be written as 

dG t (n ''° = f f . : , k Q j (n* - , \w')d7 

n w* n*i A. . i i - 1 

This Dieans that there is a fa ly of ] ' ions L. wl Lc!i map the functions 

iG (n*,w^ for n*, inl or ri',w' . 

Using th • onshi Lc.it forms loi the taboo 

Drob. ties ( e deveio] Ln terms of s >m< Less complicated 

-> rob a b i ] i t ies . >e f 1 n e 

i k 
6 ' (n,w.n ,w ) = . . uence of k • vents starting 



■ ,w tl i i ie is complied in time t and 

= n ' ,w" i •- .■:.<), .. ; I A. for 



-A- 



B 1 = I B Uk 

1 n c 

i k 
Z (n,w,n',w') ; r> sequence of k events starting 

from n,w i i. at time is co q I ited in time t and 
t N(t), W(t) = n",w' i A. and N(t) , W(x) E A 

■ i 

(n,w,n',w') dt = probabilii ■ i /enl occurring Ln dt causing the 

tr; ... ■ : Lon rom n, w \. to n ,Vi - A . , , 



M at ■- /. = Q dc 

t t 

D (n,w,n',w' )dt = probability of an event occurring in at causing 

the transition from ■,. A. to n ,w ; A. . 

! l-l 

For each finite sequence of events the first exi! from A. and first reentrv 

' l 

into A. are well defined events. Thus 

i 

Qf' a dt = D W dt * B^' 1 + '"I 3 2 ~Z i l f U 1 " 1 *! * B i,k * ^"^V * D^dT * Z 1 ^ 

J-2 lc-1 ° ° T C " T 



For simplicity o not ition, the sums and Integra s over st i have been 

surpressed ir. • ieration mits on thi : : sums reflect the fact 

that it requires two events • ■ . ■, . . A . , , i en to A.. A1J on« and two 

event sequences whoso prol .-;'-. ■■■ must Q n< ver leave 

.•ifter entering it. miming over tli nber oi evi nts. 



Q X dt = U 1 l dt * B 1 + ■' r' • Q> lH L d i>' " 1 d 

*t c> o t-i 

This equation can be solved iti using 

t t 



-}- 



fc_i , ,i , .t . . k-l i+i i~] k-l„i 
Z t = 15 t + £ £ B t-? ' dl 



The validity of this Lterai Lve Ls mo i rotn its probabilistic 
interpretation. hi k measures the an • iber of entries into 

•:. event :-■■ - Lon. Phis means 

chat the ■ ; , •- imations is i> nd and converges 

because the number ' a 1 : finii h probability 1. 

A more interesting version of the pre equal Lon results from taicing 
Laplace transforms so that th< onvoli become ; s. A related 
tation occurs if the interest is focused on stable distributions. 
iUming t hat 

Limit dG (n.w) = dG (n.w) 

t 



i r f ■ . 

i;: J -- dG (n,w) for n.w ■ A 



The recursive 1 Lationsl , ■ is 
uG - G 



i — 1 o ■» + 1 

1 * / 



Lnl egra I must ( iv< ge or 

limit * n 1 di = Limit 

't- T 

t — '*> 
can converge only bi dG in zer tati r V. , are transient, 






ected time spent 1 A • - 1 mti ring A. . 



/ Co' does nor guarantee rhe e- ence ol ng distribution. This 

o t 

requires that dG. 1 chat the eigi thesi Integrals as 



functions >>i the dG b than 1 01 that LAG its. 

Most queueing system model s ha iquences which ect 

transitions from any state n., v, to a lei n ' , w" in finite time 

with positiv< I tb] Lsh that 

for i 1 

1) /" b 1 dt * o 1 * L j i L+1 = : ' 

o t 
and 

2) / ' [i'ch * U 1 * L 1+1 - T, 1 
o t 

where 3 < 1 and L (n,w) = 1 for all n, w e A.. 

The firsc requirement is that from an (n,w) in i, su eventually leaves 

A . Sir.ce D and U are finite this means that the expected Length of stay 

i 

GO i 

in A must be finite: i.e. / B dt is finil I (n,w) in A.. The .second 
i o t. l 

requirement is that the exit is not always to a stati A . These properties 

j , . 

guarantee that J Q dt converges. The argument is pe easiest to describe 
o t 

in terms of the. functions Z 

t . 

k i 
Integrating the iterative definition of Z. with respect to time 

:,i,. ," .i,,. , - 03 ,t f i . „i, . ' L+3 , k-l„i 

J Z dt = / B dt -:• d * D cr\ * Z 

o t at o t-i 

Rearrangii ; thi rati on 

/~V dt - /Vdt h B d * u^i [j o i+1 do * r/^-Vdtj 

o t o t . o t 

By induction on foi i 

/" R Z J at * D 1 Xl}' 1 = _ | dt * D 1 * L 1 " 1 

o t o 

. — 1 5 + 1 I - 1 i i i— 1 

• . [£,] * f • i; : A z * D * L 

"o o c 

i i — 1 i x*4~ 1 

B dt * I) * L + / B * U dt * L 

t o t 

< 



and 



V dt * l. L - I B I, V | , ' n * D i+1 d^] * [/^zfdr]]*!. 1 

r o t o ° L 



o 

r 8 dl * L 1 + [/ B * 

L-p 

.- 

As k goes to infini Lnite 

The consc. :ion to the 

equation. The solution found th so the only 

one which has the additional requi Q to have 

probabilistic meaning. Firsi must bi non negativ 'or any non i - ; ve 
measure W, W k Z must be a noi i Conversely, for any \\ox\ 

negative function V, Z * v must iction. In addition 

oo j j L- 1 3 

/ Z * D * L < L since thi rci I > tnus t i 

o t — I 

cceed 1. Lnall} Z^(n,w,n . (n w,n ',w') sir ifSK restricted 



than 



B . her W satisfy thes condil ation, Compan W with 

t t J t 



the sequence L produc ; 



1 - V - -' f 1 B j ' ! I - O i+1 dl * (W j . - k ~V p ) 

t t o o £ - - t-fc, 



Rv induction W Z • for a] i ' B . 

t t t I t 

Let (W - Z ) * D 1 ' I ! -! L 1 : ). Again 

induction (W 1 i U df * L BL 

t ' 

Repeating the in< ' L . cause of th n gativity 



thit, means that Z 1 • mvei Ls the only probabilisti* 

t t 

meaningful Lul Lon of ;. 



• type ; ' 

In a previous unpublisl liscussion, the author began . 
tessima] ■ > emarked that con- 
gestion processes wore derd from moi ' ary processes. That, point 



-8- 

of view has been enta 

elementary . the routing part of 

the pro i b< so im h the congestion process that 

separation ?rely an abstraction. Thi 

especially ti im ire 

of.- ultaneou 

di s( over the op tii ingestion 

prot ess . 

There Ls lestions, 

Suppose that • even all of random 

variables. Such vari tara r of expon a 

phases or p. tervals. '. ■ the end i Interval ter- 

minates or anoth< Llities 

alternatives dep< :e just I. The pin ises nei not '•• 

ordered and Ldei ■ inte: 

distributions, the natui rete supple 

v.. r i able wh j the s t art o f 

the inl ngestion md not 

on the tirae since in pro< ess 

can be studied j r valued process N(t) . 

This proce hases may have no 

physica i ' ■ 

on the i imbe ■ of trans i . : . 

supplef • val ued 

variab j e in ibility 

i 

equation to become in sbles. 

. this case the terms of 

-ind matrices although thi ■ , ■ ,.. isional. Such 

is the case len th j in th* fini >thod 



-9- 

■ t ■ be the best method continuous Liscrete so 

that digs La I - reason 

for this discuss:! > ' " ous 

supplenw 
Boundary Set A 

ko [3] is the 

general ni sest siental 

dixit that i 

has no asso;-i tei the ti on 

lome foi pro- 
babilities are then hat thi system 
is empl - ploit a n ■ Li ties 
recurs Lvej he number o mpty. 
rhis i si Liar tc the recui Ltio Les presented 
in [2 -ingle at its limit Ing 
probaba hen performii 
the recurs t the probabilities 
sum to 1. Th s is /sis of 
3 imit ing prob contain a 
numl-' ited suppl 
mentary vai i dG . 
Again one can the last depart nre 
from A . 

dc c = dc° * b° + :' 

t t '-> 

: i, Limil >1 the 



-10- 



dG° - dG° B° + /" f X dC_ * U ( I . * D'di * B° 
x o rc o o x-t, 

In interesting cases it is impossible to remain in A indefinitely and 3^ is 

the zero oDerator and . In t must also be 

o t t 

integratable and 

n r> 1 

dG - dG * I 

» «! D T O t 

or 

dG° = dG° * Z * 0"dt * D" 
"> <= o "<* 

This suggests choosing dG^ at=- a;. measure and iteratively calculating 



k o iC— 1 D o oo 1 co o 

dG = dG * U * / 2 dT * D * / Ed: 

oo co o - o t 



or 

IcO OO ool 1 oc o O fk— 1 1 » 1 x .oo o 

K dG = dG * U * If Z dT * D * / Bdt * U • ~' f Z dx * D * / 3°dt 

o° °= Of O t ' O T O t 

where the power k-1 means repeat the * operation k-i times. The expression 

oo o O 

/ B dt * U * L is the probat Llil of leaving A for the various starting 
o t v - " o 

states and thus must be L if the limiting system results are to be strictly 

oo i i 
positive. Similarly J Z dt * D * L is the probability of ever returning 

o T 

to A from states in A . These . states in A, or the 

o 1 i. 

system limit will be de operator in brackets must be 

strictly positive ma >n the subset of n and 

values of the supplementary ■■ ir b -hich car. be entered in a transition 

from A . From positive operator theory h j the repeated application of this 
to any non zero measure will produce a unic limit in the spai_e of 

signed measures. Thus the entire iterative proceedure will converge to such 



-11- 

o o c 
a limit if dG * U is positive at least for sen -as, Moreo .'lying 

U° * L to both sides shows chat "dG * U° ' U° * L . This 

number is imm tterial since it is puted s sum of probabilities 

is made equal to 1. 

Degeneracy 



S3 far this discussion has made iitl u . of the restricted nature of 

the changes in the supplementary variables. j.ments can be 

adapted to more general assumptions . tion require this. The 

assumptions about changes in the sup pier.au t a ry variables imply that both 

U and D are degenerate. They assign positive probability only to subsets 

of states* Because entry into A coincides with the termination of some 

i 

interval, some supplementary variables must be ^t cimes . Thus 

both of the sets A. = {n',w'> j (n' s ¥'} E A.. (J "(n,w ,n' ,w") > for 

some (n,w) e A } and A.. = {(n',w"") (n',w") e A~, D (n,w,n"*,w') > 

for some (n.w) z A , } are strict subsets of A.. This strict inclusion is 
' i+l i 

even true of A° (J A.. Within A. there is a Markov process for which the initial 
i w i r 



i 



u •< D 

distribution is concentrated in A. U A. ana B is the transition operator. 

1 ^^ T 1- 



Exists from A. to A. , and A, . have ti an functions B_ * U and B^ * D 
x i+l i- t c 

respectively. Let B,. be the restriction or B to transitions rrom A, to A , 

u > t t 11 

i i D 

B-r. the restriction or B tc k. to , These operators are 

D,t l 

all that are needed to study the co: .g rest. i . and Z of 

Z^. The restricted operators satis; :ns 

„i -,i .t ,t _i ^ „i+l - .i+l . , _j 
Z,, = B, T + ; / B,. * U * Z,. w Z^ d;dt 

TJ,t TI,t o o TJ,£ %, r-K D,t-t 

z n - = 4 h + / C / T B, 1 , , * U 1 * Z i+1 * D i+1 * Z 1 ix 
From the solution to these 



-12- 



equations the complete found since 

Z 1 - B 1 + f L 
t t o 

Further "ormulae na the Lap] transform 

or concentrating same 

symbols without the of the :.or 

with respect to time. 



z u - B u + * D 



1 
i i i4-l 

z^; = BI + BZ * u * z„ * d 

D D D u D 

Use the previous assumptions B * U ' * D * L < L 

_ 

These guarantee that measure;. = L are ma pea into 

measures G for v'a * L . Thy Largest value of 

B * U * Z * D is less t! rantees an explicit 

u 

solution to the second equ is 

Zi = I (BJ * U 1 * Z i+1 

r=0 

or 

z d ~ (1 " b d L ' 

where the power is l respectively, 

Substituting this 

Z 1 = B 1 + B? , i+1 ) (r) * B 1 

this can be reai • as 

oo x-t"l 

z* « bJ * i (u 1 * z * 

U U _ u 
r=0 



The operator series must conv 
i i i 

"u u v 



or 






4 = E 

This ns idt rs the 

last exit 

L 

E 

strictii are non negative gives 

the pre * . 






i k-l„i - r .i , k-l„i+l 



U U D 

For all k, -s > Z T1 sir- 
u 

4- k; .'■ ■ • ' 

U 

Also inducl is monotone non 

decreasing and bounded frc which satisfies 

the equation. 

», i 

D 

is well del of 

Z , Z satisfying the on for 2 was 

ae rived. 

u 



-14- 

M/M/I 

Although successive approximations often provide feasible calculations 
for numerical analysis, it is instructive to examine at least one example in 
which complete analytic solution is possible. Obvious candidates for dis- 
cussion are either M/6/1 or G/M/l using only the single necessary supplementary 
variable. In these cases D and U are extremely degenerate since A = (i,o) 
and A = (i,c) respectively. These special funneling states make it easy to 
solve for the Z which are. all identical. The analysis easily provides 
limiting results in probability rather than the more familiar transform form. 

In many ways more interesting here is the less general system M/M/l in 

which the analysis uses supplementary variables w, and w for both elapsed 

interarrival and service times respectively. The state space is partitioned 

according to sets A. = {(i,w ,w ) j w >_ 0. w 9 _> 0}. The set A = {(o,w ,w_) 

w i i 0,w = 0) is the obvious exception. When there is only one customer in 

the system, it is his service which is in process and this must have, begun after 

his arrival which is also the last arrival. Thus A = {(l,w..,w ) j w ^ w > 0} 

is also an exception. The degeneracy occurs because A. = {(i,o,w_) | v > 0}, 

A. = {(i.w. ,(T | w, > 0} . It is obvfously important but not the extreme of a 
l 1 ' 1 — 



funneling state. 

The operators which define the process are 

B° (w.^.w^O) = e- A(w l- W l>d Wl - 



B° = r B°dt - e^^W 
o t 1 

For all supplementary variable values for which it is defined and all i including 

i = 1 



,i, .> - N -(A+u) (w'~w, ) . , , , . , 

t (w l' W 2' W l ' W 2 ) = e X X " 5 (*'{- w 1 > w 2~ w ? ^ dt 

b 1 = /" B^dt - e- (x+v)( V w r*(w;-w,,w;-w 7 )d W : 

u t X 1 J. J. I 



where 



lb*] - (J jg 



-15- 



For i > 



U (w. ,w ? ,w' w") - "t 
1° 



if w£ = o,w 2 =W2 



otherwise 



For i > 1 



D 1 (w 1 ,w 2J w^,wp = -I 



For the limiting distribution the solution to 



if v' = o,w'=w. 



otherwise 



1 = B 1 + Z 1 * U 1 * Z t+1 * D ±+1 * B 1 
U U U U D 



is the same for all i >_ 1. It is 
-(A+n)v 



z u = e 



1 5(w£, W 2-w 2 )dw£ + Ae - Xw 2-"wi r(w-,w£)dw£dw^ 
for 



r(x v) = c 1 x - y 

UX ' y; l x>y 



From this 



Z^ * U = Xe- (X+ K )(w 2- W 2>dw 2 r(w 2 .w 2 ) + £ e - (X+y)w 2 dw 2 
Z y * D = Me~ UW ldw^ 



These combine to give 

Z U *U*Z U *D= Xe~ PW l dw£ 
from which 

Z D * U * Zy * D * B D = Xe~ m ' l ~ X ^ r(w 2 ,wpdw£dw 2 



For the distribution at the boundary the solution to 
dG° = dG° * U° * zi * D 1 * B° 

00> CD 



-16- 



is 



dG = A(e x - e 1 )dw 1 



where the arbitrary scale factor has already been set so that 

f" dG° = 1 - \/\i 
o °° 

In this way the recursive definition 

dG n = dG n_1 * U * Z 

oo CO 

produces functions which sum to 1 as required for X/v < 1, when the limiting 
distribution exists. For X/u > 1 the EdG does not converge. The explicit 

for m is 

, n-3 ,n+l ,w2-wf> ,, . N , 

dG 00 = a--) [z ^rr L tt^ 1 e' (x+u)w 2 + 

U i=0 y n - 1_1 l! 

,n ^wf-wf.n-Z ,. . , 



n+1 

dw„ 



u=r e r(w 2'V dw i c 



From this the marginal distributions in n and one supplementary variable are 

/ dG n = (i - A) (A n / u n+1 ) e - ,jw idw: 

w 2 '=0 V X 

00 . .n+1 A n+1 n-2 i-1 ^i .n., , . w? /i. \ •* 

/ dG n = (1 _ A )( 2l_ + * E i_J^_ + ^iA±El JL_ ,).- (Wll)wt *r; 

wi=0 " " M n u 11 " 1 i=l l! y (n " 1)! 2 

As anticipated marginal probabilities for the integer variable are 

«> oo n A A 

/ / dG" = (1- -)— 

o o « u n 

u 



-17- 



and for the supplementary variables they are 

S / dG n = Ae" Xw l dw: 

n=0 1*2=0 

and 

E / dG n = ue" MW2 ' dwX 

00 / 

n=0 w'=0 

The infintessimal generator for this process is found from 

dG*\. (w ,w ) = (l-AAt-yAt)dG^(w -At.w.-At) for w > and w > 

00 

dG t+At ( °' W 2 ) = / ^tdG°" 1 (w 1 ,w 2 -At) 
w o 

00 

dG t+At (w l' 0) = f yAt d G" +1 (w 1 -At,w 2 ) 
w 2 =0 

CO 

dG t+At (w i' 0) = ( 1 - AA t)dG°(w 1 -At,o) + / wAtdG^( Wl -At,w 2 ) 

w 2 =0 

CO 

dG t+At ( °' 0) = f XAtdG °( w !'°) 
w =0 

Substituting he functional forms fov .d for dG n Into thrse relationships for 
small At also verifies that the stationary distribution has been found. 

Truncated Processes 

Another interpretation of this process allows it to be used more generally 

00 i i 
or perhaps suggests making A relatively large. First / Q dt * D dt can be 

o ox 

interpreted as the conditional probability of a transition from states in A 
to states in A._ 1 in dt in the stachastic process derived from the original 
by ignoring time spent in states in A. for j > i. The truncated process 
produces probabilities which are conditional probabilities of the original 



-18- 

00 i i °° i— 1 
process. In the same vein I Q di * D * / B dt can be considered as 

o t o T 

conditional probabilities for transitions from states in A through A. in 

a truncated process in which time is discrete and measures the exits from 

the sets A. for i = 0, i-1. The. analysis for A alone is special because 
j o 

all exits from A lead to A . In general there are also transitions from 
A. to A._ 1 in the state just before exit process. 

The use of truncated processes is very appropriate in numerical analysis 
when for j > i the sets A. are identical and the transition structure does 
not depend on j, i.e. £r = IT, B = B and Er = D for j > i. In this case 

all Q = Q ' for j > i. Thus only a single equation need be solved for these 

*> i+i 
functions. Once / Q__ dt is known then the truncated process can be analyzed 
o t 

^k ^ "j *\/ i — 1 °° i+1 

to produce dG for k = o,i. The recursive relation dG J = dG ' * / Q dt 

* oo oo oo q ^-j 

^ i ^ i 

starting from j = i+1 and dG produces a complete set of dG . These may now 

be normalized to sum to 1 and the result is the limiting distribution dG 

° GO 

for the original process. 

This was the approach used by Winsten [5] in discussing some problems in 

which the upper tail of the limiting distributions are geometric. He also 

allowed transitions from A. to and A. for j £ i + 1 with probabilities which 

depend only of i-j . This is enough to prove the recursive relationship 

dG^ ' = dG^ * R even in the more general context of this paper. The problem 

is that the equation for R becomes extremely complicated. The suggestion that 

single event transitions from A. to A. for i < i + k produces a k term 

i J - 

recursive structure can also be persued. The expressions for the coefficients 
in this relationship also become complicated as k becomes large and the 
structure on the A. becomes complex. The introduction of groups of states by 
the author makes this last generalization unnecessary for treating Erland k 
distributions as Winsten suggests. 



-19- 

Applications 

So far, analytic application of this structure has been restricted to 
systems in which the A. are identical and discrete from some point on. The 
result is that the upper tail of the limiting congestion distribution is 
geometric with a matrix for the term ratio. Although not explicitly used in 
derivations this approach can provide relatively easy access to limiting 
distributions for systems such as E./E /s and many priority models. The 

J k 

intimate relation between convergent iterative calculations and the theoretical 
analysis make this approach useable even when it is difficult to proceed 
further analytically. 

In developing piecewise linear processes, Gnedenko and Kovalenko [3] used 
the remaining length of the intervals in process as supplementary variables. 
The arguments presented here can easily be revised to use this representation 
especially if one uses rates of progress toward termination which depend on 
the congestion. In terms of functional forms, there seems to be no strong 
preference at the moment. Although this approach raises questions because 
(N(t), W(t)) may not be observable, it does provide an analytic structure 
which matches that used in computer simulations. From both the philosophical 
and practical points of view it is important to think of simulation as one 
form of numerical analysis for complicated stochastic processes. 



1. Evans, R.V., "Geometric Distributions in Some Two Dimensional Queueing 

Systems" O.R. , Vol. 15, No. 5, 1967, pp. 830-846. 

2. Evans, R.V., "Transition Functions for Event Processes", Tech. Memo. 

University of Illinois, 19 76. 

3. Gnedenko, B.V. and Kovalenko, I.N. , Introduction to Queueing Theory 

translated by Kondor and edited by Louvish, Israel Program 
for Scientific Translations, 1968. 

4. Karlin, S., "Positive Operator", Journal of Math, and Mech. , Vol. 8, 

No. 6, 1959, pp. 907-937. 

5. Winsten, C.B., "Geometric Distributions in the Theory of Queues", Journal 

of Royal Statistical Society, Vol. 21, No. 1, 1959, pp. 1-35.