Über die Verteilung von Wartezeiten

Uber die Verteilung von Wartezeiten

Von HANS-JOACHIM ROSSBERG in Berlin

(Eingegangen am 17.7. 1963)

1. Einleitung

Wir betrachten eine Warteschlange vor einem einzigen Bediener. Etwas abweichend von der iiblichen Terminologie nennen wir im AnschluB ail W. L. SMITH [4]

die Verteilungsfunktion der LSinge t des Zeitintervalls zwischen der Ankunft von zwei aufeinanderfolgenden Kundeii (Psusen- zeit) ;

H (u) die Verteilungsfunktion der Zeit ZL, die der Kunde am Schalter verbringt (Bedienungszei t ) ;

F (w) die Verteilungsfunktion der Zeit v , die der Kunde in der Schlange verbringt, ehe er bedient wird (Schlangenzeit) ;

L (w) die Verteilungsfunktion der Wartezeit w = u + v.

G ( t )

Ferner fiihren wir die Zufallsgrofie x = ZL - t ein, die die Verteilungs- funktion

m

K ( z ) = H ( x ) * (1 - G (-- x)) = J H ( Z L + X) dG (u) 0

besitzt. D. V. LINDLEY setzte in [ I ] die Unabhgngigkeit von Pausen- und Be-

dienungszeit der einzelnen Kunden und die Bedingung rn, < rn, < 00 fur die mathematischen Erwartungen von H und G voraus und bewies die Existenz einer stationken Verteilungsfunktion F (w) fiir die Schlangenzeit. Wie er ferner zeigte, genugt sie der %vIENER-HOPFschen Integralgleichung

m

P ( x ) = - J- Y(Y)dR(z-Y) (x > 0) 0

(1)

(fur x I; 0 wird F (x) = 0 gesetzt), und diese Losung ist eindeutig. Die Methode von WIENER und HOPF zur Behandlung einer solchen

Integralgleichung wurde von SMITHIES [ti] verallgemeinert. W. L. SXITH [4] 1 Math. Nachr. 1965, Bd. 30, H. I12

2 Rossberg, Uber die Verteilung von Wartezeiten

erkannte, da13 diese verallgemeinerte Methode im vorliegenden Fall (in dem der Kern eine Faltung von zwei Verteilungsfunktionen ist, von denen die eine fur negative Werte der Variablen verschwindet, die andere fiir positive Werte der Variablen gleich 1 ist) unter gewissen zusatzlichen Voraus- setzungen (s. Lemma 1 in [4]) anwendbar ist. Wie sich dabei zeigte, lassen sich, falls die LAPLACE-STIELTJES-(L-S)-TranSfOrmatiOn H* (8) (s = of i t) von H einer gewissen Klasse von analytischen Funktionen angehort, schon unter geringen Voraussetzungen uber G (2) Aussagen iiber F (2) machen.

In der vorliegenden Arbeit wird der Beweis von S l ~ ~ ~ wesentlich ver- einfacht. Mit Hilfe eines Stetigkeitssatzes ( § 2) werden dadurch alle wesent- lichen Resultate von SMITH verallgemeinert. Z. B. wird uber die Ver- teilungsfunktion H (z) nicht mehr vorausgesetzt, daB sie eine Dichte besitzt. Vielmehr werden die Voraussetzungen, die wir uber H (2) oder G (5) machen, nur Eigenschaften ihrer L-S-Transformationen betreffen, wie es der be- nutzten Methode entspricht. Auch in dieser Hinsicht werden geringere Vor- aussetzungen als bei SR~ITH verwendet, z. B. was das Verhalten von H* (s) auf gewissen Vertikalen der komplexen Zahlenebene betrifft. Eines unserer Ergebnisse wird sein, da13 die L-S-Transformationen P* (s) von F ( x ) und L* (s) von L (2) rational sind, wenn H* (s) rational ist ( 5 4). Uber G werden wir dabei lediglich die Voraussetzung

m,<m,<m

machen, die durch die Natur des Problems bedingt ist und die wir deshalb in dieser Arb& nicht standig wiederholen werden. Resultate dieser Art nennen wir Erhaltungssiitze. Sie sind im vorliegenden Fall von besonderem Interesse, weil man aus den rationalen Transformationen, indem man sie in Partialbruche zerlegt, ohne Schwierigkeiten die zugehorigen Verteilungs- funktionen berechnen kann. 1st dagegen H (z) unbekannt und die Trans- formierte von G (z) rational, so ergeben sich keine Erhaltungsdtze ( § 5).

Wertvolle Hinweise zu dieser Arbeit verdanke ich Herrn Professor J. KERSTAN, Jena.

2. Ein Stetigkeitssatz

Fur unseren Zweck ist ein Stetigkeitssatz wichtig, der auch selbstiindiges Interesse verdient.

Satz 1. Die Perteilungsfunktion F (x), die als Losung der Integralgbeichung (1) auftritt, hangt in folgendem Sinne stetig von G und H ab: Die Kerne der Integralgleichungen

( I7 m

Fv (4 = - J Fs (Y) d K (2 - Y) (lJ =I, 2, . . .; z > 0) 0

Rossberg, tfber die Verteilung von Wartemiten 3

seien definiert durch m

K,, (4 = J H, (u + 4 dG,, (u) , 0

wo H, u n d G,, Yerteilungsfunktionen m i t H,(O) = G,(O) = 0 sind, die die mathematischen Erwartungen ma, bzw. m,, besitzen. Wenn G, (x) u n d H, (x) schwach gegen die Yerteilungsfunktionen G (z) bzw. H (2) konvergieren u n d zugleich lim ma,, = mB, lim ma” = m, , ma < m, < 00 gilt, so folgt

Y-W- ,+-

lirn F, (z) = F (z) Y + e O

in allen Stetigkeitspunkten von F (x). Beweis. Bus der Voraussetzung folgt nach dem Stetigkeitssatz fur

charakteristische Funktionen lim K Y ( z ) = K (2) in allen Stetigkeits-

punkten der Verteilungsfunktion K (2). Fur eineTeilfolge (Y’) der natiirlichen Zahlen existiert eine Grenzfunktion F, (y), so darj in allen ihren Stetigkeits- punkten lim Fv, (y) = F, (Y) ; sie braucht zunachst keine Verteilungs-

funktion zu sein, da die Bedingung F , (m) = 1 nicht gesichert ist. Die Zahl z sei ein Stetigkeitspunkt von R (x). Wir unterteilen das Interval1 (0, Y) durch die Punkte yo = 0 , yl, . . ., yN = Y , die so gewahlt werden, dafi lim F,,, (yi) = F,(yi) und lim K,. (z - yi) = K (z - yi) ( j = .O, . . . , Lv) existieren ; dann gilt

I+-

v’+m

r’+m d-+m

N - 1

Der Grenzubergang v’ 4 00 in den Approximationssummen fuhrt zu den Approximationssummen des Integrals

2-

S F J Y ) d K ( z - Y ) , 0

das fiir fast alle z existiert (man muB nur durch Auswahl von z dafiir sorgen, daB Unstetigkeiten von P, (y) und R (z - y) nicht zusammenfallen) und somit der Limes des abgeschatzten Integrals ist. Da K J z ) eine Ver-

teilungsfunktion ist, bleibt - 1 F,, (y) d K,, (z - y) < K,, (z - Y ) beliebig Do

P I.

4 Rossberg, ober die Verteilung von Wartezeiten

klein fur genugend grofies Y . Folglich liefert (1’) bei Y‘ -+ co

(2)

Da die positive, monotone und beschriinkte Losung clieser Gleichung bis auf einen Faktor eindeutig ist, finden wir

m

P , ( 4 = - f R s Y ) d j u - Y ) (z > 0 ) . 0

lim F,,(z) = Pm(z) = F,(m) P (z) mit O 5 Eb,(oo) 5 1. u’+m

(3)

Jetzt mussen wir die Gleichung Fm(co) = 1 bemeisen. Damit wird der Beweis des Satzes abgeschlossen sein, denn jede Teilfolge Fv, (z) der PV (z), die gegsn eine Grenzfunktion konvergiert, hat dann nach (3) den eindeutig bestimmten Limes F (x); daraus folgt lim F,(z) = P (z).

Y J W

Wir fiihren die Funktionen I -

ein, so daR aus (1) und (1’)

(4) W

P (4 + FI (4 = - j - P (Y) d K (z - Y)

F, (x )+P, , ( z ) = - p v ( y ) d K ” ( z - y ) ( - - < z < < )

( - 00 < I): < 00) 0

bzw. W

0 (4’)

folgt. F u r die eben eingefuhrten Funktionen gilt 0 0

J’ Pi(.) d z < cm und l P f v ( z ) d z < co: -m -m

0

Wegen [ mK I = [m, - m, 1 < 00 ist namlich

die Vertauschungsformel

(5)

K (z) dx < 00 ; folglich gilt --

O m

j d P ( y ) / K (x - y) dz = J d x J’ K (z - y) d F ( y ) 0 -m -m 0

0

= p w d z , -ca

da das Integral auf der linken Seite absolut konvergiert. Ebenso ergibt sich natiirlich die Integrierbarkeit yon F,, (x). Aus (4) folgt durch Fourier- Transformation, wenn g, (t) und ic (6) die charakteristischen Funktionen von

Rossberg, Uber die Verteilung von Wartezeiten 5

F (2) bzw. K (z) sind,

e, ( t ) (1 - x ( t ) ) + V I P ) = 0 , wo

m n p l ( t )= 1 e i ‘ ” d F l ( x ) = - - i t J e i ” F P , ( x ) d x = - - i t y ( t ) .

-00 -ca

Fur t + 0 folgt

1 - x ( t ) e, ( t ) i t - Y ’ ( t ) = 0.

y ( t ) ist stetig fur t = 0, und wegen

x ( t ) = ( t f i t m H f 0 ( t ) ) (1 - it ??lo f 0 ( t ) ) folgt daher aus (6) fur t + 0

0 mff - mH = JFi(x)dx.

-00

In derselben Weise ergibt sich naturlich aus (4‘)

Unsere Voraussetzungen fuhren jetzt auf 0 0 -- -m - m

Jim JP , , ( s )dx = J P i ( z ) d z . (7)

Somit kennen wir den Limes der rechten Seite der Gleichung m 0 0

6 -m -m dE:(Y) JK&- Y ) d X = /F , , ( x )dz , (8)

die in Analogie zu ( 5 ) besteht. Den Limes der linken Seite berechnen wir jetzt a d Grund von (3).

Wegen mG = J zdG,(z) + m, und G,(z) + G (2) gilt bei festem y > 0 m

und genugend groDem A > 0 fur genugend grol3e Y - A - y - A - y m

-m -00 0 1 K,(x)dx= f d x f B,(U+x)dG,(u)

m - A - y

= J dG,(u) 1 B V ( U + x)dx 0 -m

m - A - y 00

A t Y -t4 A i Y = J d ~ , ( u ) J ~ , ( u + z ) d z < J u a q ( u ) < E .

Die Vertaukhung der Integrationen ist wiederum gerechtfertigt, weil (wegen my = mxu - ma,) das linksstehende Integral absolut konvergiert. Aus

6 Rossberg, uber die Verteilung von Wartezeiten

dieser Abschiitzung und K,(x) + K (2) folgt 0 0

Dieselbe Methode, die uns auf ( 2 ) fuhrte, liefert jetzt nach (3) und (5) als Grenzwert (Y' + m) der linken Seite von (8)

W 0 0

[ dP,(y) p U x - y ) d z = P , ( m ) J ' F l ( Z ) d Z . 0 --Do --m

Indem wir die Limites beider Seiten von (8) vergleichen, erhalten wir F,(co) = 1; q. e. d.

3. Allgemeine SItze iiber die LBsung der Integralgleichung

Satz 2. H * ( s ) und G*(s) seien in cl > - 2 1 analytisch, wo 1 eine gewisse positive ZahZ ist. In dem Streifen - 1 5 cl 5 1 gelte die Darstellung

K*(s) = H * ( s ) G * ( - 8) = KT(s ) + K:I (s),

wo K;" ( s ) analytisch und

[KT (s)/ 5 1 - 6 (6 > 0) in cl 5 1, KT, (s) = 0 -

Integralgleichung (1) gegeben durch die L-S-Transformation

( - 1 CT 5 1) is t l ) . Dann ist die .LLBsung der (,:I) (9)

wo A e ine

A P*(s) = -

@+ (s) '

Konstante ist. Pur Of ( s ) gilt mit der Abkurzung

s - 1 1 - K*(s) 1 - KT (8) s 1 - K:(s)

A

Q (8) = -

I ) Diese Zerlegung mag von einem rein funktionentheoretischen Standpunkt seltsam erscheinea. Sind aber H I ( z ) und HII(Z) Verteilungsfunktionen, so ist auch

a(4 = a HI(^ + B a11(4

E:(s) = a H ; ( s ) a*(- s), eine solche, falls a 2 0, ,9 2 0, M + 1 = 1. Man kann dam

K&(s) = /3 H11(s) a*(- s) aetzen; die Voraussetzungen des Satzes iiber E:(s) sind z. B. erfiillt, wenn HI(A) = 1, also B?(s! eine game Funktion der Ordnung 1 und vom Mitteltyp A > 0 ist und wem G(A) = 0 Ist; die letztere Bedingung hat ntimlich U* (8) = o ( e - A o ) (a > 0) und somit K?(a) 5; 1 - 6 in a 1 fiir gewisse 1 > 0 und 6 > 0 zur Folge.

Roasbeq, uber die Verteilung von Wertezeiten 7

u n d einer genugend kleinen Zahl p > 0

p-im

rll @-($I hat @+ ( s ) ist in u 2 - - analytisch, ohne Nullstellen und beschrankt; - 2 s - A

dieselben Eigenschaften in u 5 -. iu 2

Beweis. Da im1nt;ervallO 5 y 5 cu die Abschatzung P(0) 5 F ( y ) 5 1 gilt, folgt fur die oben eingefuhrte Hilfsfunktion

m

O $ P ~ ( X ) ~ - J d K ( x - y ) = K ( x ) (z<O). 0

K (x) aber hat nach dem Faltungssatz fur die zweiseitige L-S-Trans- formation eine Transformierte

K*(s) = H*(s ) a*(- s), die in - 2 A < u < 2 A keine Singularitgten aufweist. Daher gilt (E. L u a c s [2], Satz 7.2.1) K (x) = o (e") fur x -+ - co und jede positive Zahl r < 2 A ; folglich ist auch Fi(z) = o (em), und nach dem eben zitierten Satz ist

- w -ca

analytisch in der Halbebene u < A ; zugleich gilt in diesem Gebiet mit einer gewissen Konstanten C

Ip:(s)I < c . Wir konnen nun die zweiseitige L-S-Transformation der Gleichung (4)

bilden und erhalten, indem wir nochmals den Faltungssatz anwenden,

Die Funktion 1 - K*(s) kann nach Voraussetzung in dem Streifen - A 5 G 5 A nur endlich viele Nullstellen haben. Der Ursprung s = 0 ist


wegen m, $; m, eine einfache Nullstelle. Auf der imaginaren Achse kann es uberhaupt keine weiteren Nullstellen geben, da die Gleichung 1 K* (i t) 1 = 1 fur t $1 0 nur bei gitterformigen Verteilungen auftritt; dann aber ist K* (i t) fastperiodisch und lim sup IK* (i t) 1 = 1, und das widerspricht

unserer Voraussetzung. Wie wir hieraus ersehen, gibt es eine Zahl p > 0, so dal3 die Funktion

I4+-

und daher naturlich auch 6 (s) keine Nullstelle in dem Streifen - [ I

hat. Nach dem Monodromiesatz ist daher

log 6 (s)

in dem bezeichneten Gebiet eine eindeutige analytische Funktion. Nach Voraussetzung gilt

lim Q ( s ) = I Irl-)m

114)

gleichmanig in - p 5 CT =( p. D a wir aus dieser Gleichung

A

schlienen wollen, miissen wir das Verhalten von arg Q (s) studieren, wenn t von - 00 his + 00 wandert; dabei k6nnen wir u = 0 setzen, da der Limes (14) gleichmaBig bezuglich u gilt.

Fur kleine t gilt

Q (it) = 1 (mo - m,) + O ( t ) . Wahlen wir ein kleines 6 > 0, so bleibt also arg Q (i t) nahe bei 0 fur It 1 5 6. Wegen ]R* (i t) 1 < 1 (t + 0) ist

z ]arg{l--*( i t )}/ <--, a

und folglich ist TG

- 72 < aFgQ (i t) < - (z 5 - 6) 2

57 Ferner ist I arg Q (i t) 1 <- fiir geniigend grol3e It 1 . Wie aus diesen Fest-

stellungen hervorgeht, ist die Zunahme von arg Q (i t) im Interval1 2

- m ~ t ~ m

Rossberg, gber die VerteiIung von Wartezeiten 9

* kleiner als n; folglich ist die von arg Q (i t) kleiner als 2 n, wegen (14) also 0. Daraus aber folgt (15).

Wir sind jetzt in der Lage, die CAucRYsche Integralformel auf die Funktion log 8 (s) anzuwenden und finden

(vgl. [4], 9 4), d. h. die Gleichung (11). Die Integrale, durch die @+ (s) und

@- (’) dargestellt werden, konvergieren infolge unserer Voraussetzungen uber s--A

K&(s) absolut. Nach [3], S. 53, haben die Funktionen @+ und - die

im Satz angegebenen Eigenschaften.

@- s - - A

Aus Gleichung (12), die wir in der Form

P* (8) Q (s) + (S - A) 2 ( ~ ) = 0

schreiben konnen, erhalten wir nun

(A - s) F; (s) @- ( 8 ) -F*(s) @+ (8) = (0 < CJ <i). 1 - K:(s) S - 1 (17)

Die linke Seite dieser Gleichung ist analytisch und beschrankt fur CJ > 0; die rechte dagegen hat wegen ‘ 1 FT ( s ) I < C dieselben Eigenschaften in (r < p. Jede der beiden Funktionen ist somit die analytische Fortsetzung der anderen, und zusammen stellen sie eine beschrankte ganze Funktion dar, die also eine Konstante ist. Folglich gilt die Gleichung (9). Der Faktor A ist durch die Bedingung F*(O) = 1 bestimmt.

Satz 3. Setzt man in Satz 2 voraus, daB KT(s) die angegebenen Eigen- schaften in a 2 - 1 hat, so lindert sich an der Aussage uon Satz 2 nw die FormeZ (9), die jetzt

(9’)

Zautet . Beweis. Schreibt man (17) in der Form

@- (8) (s) ~ s - 1’ F* ( s ) @+ ( s ) ( 1 - KT (8)) = ( A - s)

so kann der ganze Beweis von Satz 2 wortlich wiederholt werden und liefert die Behauptung.


4. Erhaltungssltze

Aus Satz 2 gewinnen wir sehr schnell die folgende Verallgemeinerung

Satz 4. Die L-8-Transformation H*(s) sei in der ganzen Ebene mero- morph mit nur endlich uielen Polen b,, . . . , bn 2) ; sie ,gestatte eine Zerlegung H* ( s ) = HT ( s ) + H:I(s), wo I HF (8) 1 < y < 1 fiir 0 < I und geniigend

kleines 1 > 0 ; ferner sei Hg ( s ) = 0 - (z+=Oo) fur 101 5 I . G * ( S ) sei

analytisch in 0 > - I . Wenn es eine Xchar von Kreisen R, um 0 mit den Radien R, -+ 00 gibt, so dap I K* (s) I = lH* (s) G* ( - s) I < 1s j k f” ur eine naturliche Zahl k und s E 9, (a < 0) (v = 1, 2, . . .), dann ist3)

des Satzes 3 von SMITH:

S * I--

(18) P*(s) =n-- bi

i I-- s ai

Die Zahlen a, sind die Nullstellen der Funktion 1 - K * ( s ) in 0 < 0. Falls fur gewisse b j gilt P- ( - b j ) = 0, aber auch nur in diesem FaEle, sind

die entsprechenden Baktoren in (18) wegzulassen. F* ( s ) entartet jedoch nie z u einer Konstanten.

Beweis. Zunachst sei P(- bi) =i= 0 (i = 1, . . ., n). Urn Satz 2 anzuwenden, setzen wir K:(s) = H:(s)G*(- s ) ( A = I, 11). Wahlen wir p’ geniigend klein, so ist fiir gewisses 6 > 0 die Bedingung IKf (s) I 5 1 - 6 in

a ~ y ’ e r f u l l t . NB:IG*(o +i?)/s ~ e - u z d G ( z ) = G * ( a ) ( o > - l ) .Dann

ist f i i r ein gewisses y (0 < ,LJ < y’) nach Satz 2 die Funktion @+ (s) fur

a 2 - - beschrankt; ferner wird @+ (s) gemaB (11) in die Halbebene a < p

analytisch fortgesetzt (denn (11) gilt unter unseren Voraussetzungen in a < p ) und hat dort die Pole von R* (s) und die Nullstellen von 1 - K* (s). Nach Voraussetzung folgt aus (11)

1 m

( 0

iu 2

l @ + ( s ) I < C I s I k ( S E W ,

P (s) = @+ (s)

wo C eine genugend groBe Konstante ist. Die Funktion n

(s - bj ) 1

a) Wegen H ( 0 ) = 0 ist natiirlich Re bi < 0 (i = 1, . . ., n). 3) Hier und im weiteren werden alle Pole und Nullstellen entsprechend ihrer Vielfach-

heit aufgefiihrt.

Rossberg, uber die Verteilung von Wartezeiten 11

ist somit in der ganzen Ebene analytisch und laljt sich auf grol3en Kreisen 8" durch 2 C majorisieren. Deshalb ist P (s) ein Polynom, das hijchstens den Grad k f n besitzt, d. h.

jst rational. Da aber @+ (s) eine in a > 0 beschrankte Funktion ist, hat P (s) den Grad m 5 n. Nach (9) mu13 aber auch der Kehrwert von @ + (s) in a > 0 beschrankt sein, und daher gilt m 2 n. Aus (9) folgt nun (18) ; die Be- hauptung uber die Zahlen a, ergibt sich aus ( l l ) , denn d ie Pole von F* (s) sind die Nullstellen von @+ (8).

Die Behauptung uber den Fall G* (- bi) = 0 ist aus dem Beweis leicht erkennbar. Unter den Polen von H* (s) ist stets einer reell; andererseits ist G* (a) > 0 fur (r > 0; daher hat F* (s) in (18) stets mindestens einen Faktor. Damit ist Satz 3 bewiesen.

Als Verallgemeinerung des Korollars 1 von SMITH folgt der Erhaltungs- satz

Satz 5. Wenn H * ( s ) rational ist mit d e n Polen b L , . . ., b , , so ist auch . F* ( s ) rational, und es gilt die Aussage von Satz 4.

Beweis. Es gilt fur Is1 --f 00 die Darstellung

H*(s ) = a(+ 0) + O - (12 (0 5 H (+ d) < I",), so dalj wir in Satz 4 HT (s) = H (+ 0) = const setzen konnen. Wenn fur eine gewisse Zahl XI > 0 G (Xi) = 1 gilt, so ist G* (s) eine ganze analytische Funktion und Satz 4 liefert sofort die Behauptung. Falls aber G (z) < 1 fur alle k, definieren wir fur Y = 1, 2, . . . die Funktionenfolge

Fiir die zugehorigen L-S-Transformationen gilt dann

(20) C,*(s) = G*(s ) + g.*(s) (0 > 01,

4) Wenn H(+ 0) = I, die Verteilungsfunktion der Bedienungszeit also ausgeartet ist, so kann sich natiirlich keine Warteschl!nge bilden. Da in diesem Falle

K ( z ) = 1 4 a(- z),

liefert (I) erwartungsgemiU3 B(s) = 1 (z > 0) als eindeutige Losung.


wo m m

gf ( 8 ) = e-'" ( 1 - G (v)) - 1 e-rz d G (z) = s ( I - G (z)) e-sZ d z , Y t

Daher ist in (T < 0 8 - 1

Q,(s) = __ (I - H * ( s ) G ~ ( - s)) P

s - A = Q (s ) - --- H* ( s ) gf ( s ) .

S

Zunachst sei G* (- bi) + 0 ( j = 1, . . . , n). Fur genugend grol3e Y ist dann GT(- b j ) $5 0, denn anderenfalls ergibt sich aus (20) und (21) ein Wider- spruch.

Wir betrachten die Integralgleichung (l'), in der wir H, (2) = H (z) setzen. Satz 4 liefert sofort die Losung

S , I-- - bi

1 I-- P T ( S ) = n--,

S

ai, wo a, die Wurzeln der Gleichung 1 - K,*fs) = 1 - H * ( s ) G,*(- s ) = 0 in (T < 0 sind.

Jetzt fuhren wir den Grenziibergang v -+ 00 aus. Wegen m," + m, ist namlich Satz 1 anwendbar, und daher konvergiert die Folge FV(z) der Losungen von (1') gegen die gesuchte Losung F (z) von (1). Die charakteristischen Funktionen 'p, (t) = PT (- it) konvergieren folglich gegen P* (- it). Daher hat F* (s) , wenn man ui = lim ui,( j = 1, . . . , n) setzt, die im Satz

behauptete Gestalt. 'Fur kein j kann ui = 00 sein, da sonst F* (- i t ) nicht beschrankt ware.

AuSerdem ist kein a,. einem bi gleich, ferner gilt 1 - K* (aj) = 0 : Dazu betrachten wir ein beschranktes Gebiet (8, das links der imaginaren Achse liegt und alle Punkte b,, . . ., b, enthalt. Nach (20) und (21) gilt gleich- maSig in @

v-+-

GT (s) + G* ( s ) . Daher gilt fur jedes j (j = 1, . . . , n) wegen a*(- bi) =+ 0 auch

1 ' - & ( s ) 8 - 1 - Q, (8) - G,* ( -s ) G*(--s) s (G: ( -s ) G * ( - S )

Rossberg, Vber die Verteilung von Wartezeiten 13

gleichmll3ig in einer Umgebung von b, . Die Beziehungen 0 = lirn &, (aj,)

und bj = lim uiv fuhren folglich zu & ( b j ) = 0, also zu einem Widerspruch. u + m

v+m

Aus (21) und (22) ergibt sich fur u < 0

l Q y ( ~ ) - &(a) I < Is - 1 I lH* (8) I 7 (1 - O(2)) C E Z . V

Wegen ai += b, folgt daraus lirn Q (a,) = Q (aj) = 0 , V + O O

Wir kommen nun zum letzten Teil des Beweises und nehmen an, da13 eine Indexmenge M vorhanden ist, SO dalj G*(- bk) = 0 ( k E M ) . Wir brauchen nur den Fall zu betrachten in dem G,* (- bk) + 0 fur unendlich viele Y. Den bisherigen Betrachtungen entnehmen wir, dalj man jedem bi mit G* ( - bi) + 0 ein aj + b, zuordnen kann. Es sei k E M , und lirn a,, = ak sei

verschieden von allen b, , . . . , b,. Das fuhrt wie oben auf Q (ak) = 0. Das ist aber nach dem folgenclen Lemma unmoglich, denn die Pole von Q ( s ) sind die bj mit j e M und die zugehorigen Nullstellen sind die uj mit j 6 &I. Folglich ist (bei geeigneter Numerierung) ak = b, (k E 113).

Lemma. Die Funktion Q ( s ) hut unter der Voruussetzung von Satz 5 benso viele Nullstellen wie Pole o < 0.

Beweis. Es sei sI = uI < 0 der der imaginaren Achse.am nachsten gelegene reelle Pol von H*(s) . Fur 01 < u < 0 konvergieren die Integral- darstellungen von H*(s ) und von G*(- s). Wegen

v-+m

nimmt die Funktion H * ( s ) , wenn man sie auf der durch u defkierten Parallelen zur imaginaren Achse betrachtet, ihr Maximum im Punkte s = u an; dasselbe gilt naturlich fur G*(- s). Nun gilt fur die Funktion q ( b ) = H*(u)G*( - c): q ( 0 ) = 1, ~ ( g l ) = 00, ~ ( 0 ) > O(al < G < O),

lim p'(u) = lim [H*'(a) G*( - c) - H * ( u ) G*'(- u)] a+-0 a+-0

= rnG - m, > 0 ;

daher existiert eine Zahl urn (ui < u, < 0), so dal3 lH*(u,) G*(- a,)/ < 1. Aus dem obigen folgt IH*(s) G*(- s)l < 1 fur u = urn, - 00 < z < 00. Wir schlagen nun um den Punkt s, = u, einen Kreis mit einem so grol3en Radius R, daI3 alle Pole bl , . . . , b, von N* (8) in ihm liegen. Sein Durch- messer, der auf der Geraden s = a, liegt, einerseits und der links von diesem befindliche Halbkreis andererseits bilden zusammen eine Kontur C, auf der, wie die eben durchgefuhrten Betrachtungen und die Darstellung


H* (s) s H (+ 0) + 0 (h) zeigen, f i i r genugend grol3e R

\ H * ( s ) G*(- s)l <: 1.

n a+( - -b i )+0 Wir bilden nun P ( s ) = (S - bj) . Fur s E C folgt

IP(s) l L IP(8) H * ( s ) Q*( - s)l7

und der Satz von ROUCHE liefert daher sofort die Behauptung, denn mit Konturen der Gestalt von C kann man die ganze Halbebene {cr < 0 ) aus- schopfen.

Die Verallgemeinerung des Satzes 4 von SMITH folgt sofort aus unserem Satz 5 und lautet:

Satz 6. Es sei

D a n n ist die Verteilung der Wartezeit gegeben durch

L* ( s ) = P* (s ) H" (s) =

wo die Zahlen ai wie in Sa t z 5 bestimmt sind. Wenn far e in ige i gilt

G * ( - bi) = 0 ,

so ist a, = b, fur diese i zu setzen. Der besonders interessante Spezialfall dieses Ergebnisses lautet :

Korollax. Es sei H (x) = 1 - e-b2 und - = m, < ma < 00 ; d a n n ist 1 b

S 1 +-.

b Zum Beweis ist nur noch darauf hinzuweisen, da13 P* (s) = - nur S

i+;

fur 0 < a < b die L-#-Transformation einer Verteilungsfunktion ist.

5 ) m = 0 bedeutet, da5 E*(s) keine Nullstelle hat.

Rossberg, uber die Verteilung von Wartezeiten 15

5. Eine Aussage uber die LBsung der Integralgleichung, wenn H (2) unbekannt ist

Wir verallgemeinern hier noch den Satz 5 von SMITH. Satz 7. G* ( s ) sei rational mit den Polen fi , . . . , f n ; H* ( s ) sei analytisch

in {u > - ;I} ftir gewisses 3, > 0 , H* ( - f i ) =k 0. Dann gilt in u > 0

Die Zahlen ri sind d ie Nullstellen der Funktion 1 - H* ( s ) G*(- s ) mit Re r j > 0 (j = 1, . . . , n).

Beweis. Es gilt G*(s) = G ( + 0) + 0 - , 0 5 G ( + 0) < I. Wir

definieren daher KT (s) = G (+ 0) H* (8). Da H* (s) in {u > -;I} analytisch ist, konnen wir Satz 3 anwenden. Beim Beweis von Satz 5 haben wir @+ (s) mit Hi& von (11) in die ganze Ebene analytisch fortgesetzt ; jetzt dagegen setzen wir @-(s) analytisch fort. Dazu schreiben wir (11) in der Form

(,:I)

I - KT (s) rp- (8) = s @+ (8) 1 - K* (8) . (23)

Die rechte Seite dieser Gleichung ist (fur gewisses p > 0) in u > - p als analytische Funktion dehier t , daher ist jetzt nach Satz 3 die Funktion @- (s) in der ganzen Ebene erklart. Ihre Pole und Nullstellen sind die Null- stellen bzw. Pole von 1 - K* (s) in u > 0. AuBerhalb eines genugend grol3en Kreises urn 0 ist

1 (24) [ I - K * ( s ) I z j - ( I - G ( + 0))

in (I > 0, denn es gilt K*(s) = G ( + 0) H ( s ) + 0 - . Daher ist @-(s) (I:,) eine analytische Funktion mit n Nullstellen, die innerhalb eines gewissen Kreises hochstens endlich viele (k) Pole hat, und auBerhalb dieses Kreises

ist 121 beschrankt. Somit ist @-(s) rational, und es gilt

@(I-;)

v(:-:) @-(8) = -x (k 2 n - 1).

16 Rossberg, Uber die Verteilung von W a h a a i t e n

Aus (23) und (9’) folgt nun

Die Ungleichung 1 $ ’ * ( 0 ) 1 5 1 (O 2 0) liefert noch k + 1 5 72, d. h. es ist k = n - 1. Aus F*(O) = 1 ergibt sich nun die Behauptung.

Z u s a t z b e i d e r K o r r e k t u r. Wie Verf asser inzwischen erfuhr, hat C. C. HEYDE (J. Appl. Probability 1. 175-178 (1964)) eine etwas andere Methode angedeutet, mit der man unseren Satz 5 ebenfalls beweisen kann. Die Arbeiten von HEYDE und vom Verfasser wurden fast gleichzeitig zum Druck eingereicht. Benntzt man sein Resultat, so kann man auf unser Approsimationsverfahren verzichten. - Verfasser wird in einer weiteren Veroffentlichung den Beweis des Satzes 5 so weit vereinfachen, dal3 man ihn unter geringen Voraussetzungen uber G ( t ) umkehren kann. Wie daraus erhellt, ist unser Satz 4 nicht wesentlich allgemeiner als Satz 5.

Literatur

[l] D. V. LINDLEY, The theory of queues with a single server. Proc. Cambridge Philos.

[2] E. LUXACS, Characteristic functions, London 1960. [3] R. E. A. C. PALEY, N. WIENER, Fourier Transforms in the complex domain, New York

[4] W. L. SMITH, On the distribution of queuing times. Proc. Cambridge Philos. SOC. 49,

[5] 3’. SMITHIES, Singular Integral Equations. Proc. Lond. Math. SOC. ( 2 ) 46, 409-466

SOC. 48 (1952).

1934.

449461 (1953).

(1940).

Documents

Über die Verteilung von Wartezeiten