MÜNCHENER STOCHASTIK-TAGE 1998 Sekt.-Nr.:1

Angewandte stochastische Prozesse

Sektionsleiter: T. Hanschke, Clausthal-Z.; U. Rieder, Ulm

Bäuerle , Nicole Universität Ulm

Wie man einen ATM multiplexer optimiert

Wir betrachten einen ATM multiplexer mit endlichem oder unendlichem Puffer und stochastischer Ausflußrate. Der multiplexer wird von einer Anzahl unabhängiger, identisch verteilter Quellen gespeist, deren Fluid direkt in den Puffer fließt. Wir zeigen, daß der Durchfluß des multiplexers in der Anzahl der verbundenen Quellen steigt, wobei der Einflußstrom so skaliert wird, daß die durchschnittliche und maximale Einflußrate unverändert bleiben. Beim endlichen Puffer fällt die Verlustrate des Einflußes in der Anzahl der verbundenen Quellen. Im allgemeinen kann man zeigen, daß durch Varianzreduzierung im Inputprozeß die Leistungsfähigkeit eines ATM multiplexers erhöht wird. Dieses Ergebnis kann man auf einfache Netzwerke wie Tandem-Puffer und Assembly-Systeme ausdehnen. Die Ergebnisse werden mittels multivariater konvexer Ordnung erzielt.

Bischof, Wolfgang Institut für Mathematik, Universität Augsburg

Stabilität in Polling–Systemen

In meinem Vortrag wird die Stabilität in Polling–Systemen untersuchtPolling–S nach einer Polling–Tabelle und gemäß unterschiedlicher Disziplinen bedient weEinen erst Systeme und der zugehörigen Bediendisziplinen. Es folgt eine exakte Definition der Stabilität in Polling–Systemen sowie deren Spezialisierung für Systeme mit Poisson–Ankunftsprozessen. Für entleerende und absperrende Bediendisziplinen wird für Erneuerungsankunftsprozesse, deren Zwischenerneuerungszeiten schließlich exponentialverteilt sind, eine hinreichende Stabilitätsbedingung angegeben und mit der Theorie über regenerative Prozesse bewiesen. Falls Poisson–Ankunftsprozesse vorliegen, werden für alle Bediendisziplinen, die sechs allgemein gehaltenen Grundforderungen genügen, notwendige und hinreichende Stabilitätsbedingungen formuliert. Der Beweis benutzt die stochastische Isotonie der Warteschlangenlängen zu Polling–Zeitpunkten bei zu Beginn leeren WarteschlDie Bedien untereinander und vom Ankunftsprozeß unabhängige, sonst beliebig verteilte Folgen nichtnegativer Zufallsvariablen.

Borkovec , Milan TU München

Extremal behaviour of diffusion models in finance

We investigate the extremal behaviour of a diffusion (X_{t}) given by the SDE

dX_{t} = μ(X_{t})dt + σ(X_{t})dW_{t} , t > 0 , X_{0} = x ,

where W is standard Brownian motion, μ is the drift term and σ is the diffusion coefficient. Under some appropriate conditions on (X_{t}) we prove that the point process of ε–upcrossings converges in distribution to a homogeneous Poisson process. As examples we study the extremal behaviour of term structure models or asset price processes such as the Vasicek model, the Cox-Ingersoll-Ross model and the generalised hyperbolic diffusion. We also show how to construct a diffusion with pre-determined stationary density which captures any extremal behaviour.

Brandt, Andreas , Brandt, Manfred Humboldt-Universität zu Berlin, Konrad-Zuse-Zentrum für Informationstechnik

Performance Analysis of Automatic Call Distributor Systems

An Automatic Call Distributor (ACD) forms the fundamental element of today’s call centers. An ACD system distributes a stream of incoming calls to agents who will provide a service or a product to the caller. An ACD with s agents, k waiting places (s+k lines) and an integrated Voice-Mail-Server, where calls may be recalled if they have waited longer than a given time, is considered. Additionally, waiting calls may become impatient. A system of integral equations for the state process is derived and solved explicitly by using former results of the authors. This allows to derive the stability condition as well as other relevant performance measures of the system, like the occupancy distribution. Further, by adopting stochastic decomposition results the analytical formulae may be iluminated. However, for the mean sojourn time in the Voice-Mail-Server an explicit result could not be given, but an efficient approximation is derived. The presented numerical results show that the proposed algorithms work well.

Breitung, Karl Institut für Mechanik, Universität Innsbruck

The asymptotic distribution of a stationary Gaussian process

We consider a continuous stationary Gaussian process x(t), which is standardized, i.e. E(x(t)) = 0 and var(x(t)) = 1. It will be assumed that its covariance function, denoted by r(t) = E(x(t)x(0)), satisfies the Berman condition r(t) log(t) → 0 as t → ∞. For t → 0 assume that the covariance function has the expansion

r(t) = 1 − C|t|^{α} + o(|t|^{α})

for some α ∈ (0, 2]. Then for the maximum of the process holds that

Pr [a_{T} ( max_{0≤t≤T} x(t) − b_{T} ) ≤ u] → exp (−e^{−u}) , T → ∞

for

a_{T} = (2 log(T))^{1/2}
b_{T} = a_{T} + a_{T}^{−1} [\frac{2 − α}{2α} log(log(T)) + log (C^{1/α}H_{α}(2π)^{−1/2}2^{(2−α)/2α})]

Here H_{α} is a constant. Its value is known only for α = 1, 2, H_{2} = π^{−1/2} for a continuously differentiable process and H_{1} = 1 for the Ornstein-Uhlenbeck process. In the last years in a number of stochastic models fractional Gaussian processes are used. These are processes with the properties above and 0 < α < 2. Therefore a derivation of the exact values of H_{α} will be of interest for these models. This is done by relating the exceedance time of the process over a level u, which is defined by

Z(T) = ∫_{0}^{T} 1_{x(t)>u} dt

to the probability that at a random point in time the process is above u, i.e. Pr(x(t) > u). The exceedance time can be modelled by a marked or filtered Poisson process, where the mark is the length of the exceedance. This is achieved using the Campbell theorem relating the length of the outputs of filtered Poisson processes to the output values at a random time point. The result is

H_{α} = 1/Γ(1/α).

Hesse, C.H. & \underline{Dunz}, \underline{A.} Mathematisches Institut A, Universität Stuttgart

Modellierung von Sedimentation durch interagierende Diffusionsprozesse

Die Sedimentation von Feststoffpartikeln in einem viskosen Fluid stellt ein Vielteilchensystem mit komplexen Wechselwirkungen zwischen den Komponenten dar. Ausgangspunkt der hier vorgestellten Arbeit ist ein Markov-Modell für die Sedimentation von n Teilchen, in dem die inkrementelle Dynamik jedes Partikels durch eine stochastische Differentialgleichung mit drei Parametern beschrieben wird. Hydrodynamische Interaktionen werden durch eine Abhängigkeit dieser Parameter von der momentanen lokalen Feststoffkonzentration modelliert, der wichtigsten eindimensionalen Einflußgröße auf die inkrementelle Bewegung eines Partikels. Um die Dynamik des Systems zu analysieren, wird das Konzentrationsfunktional durch ein Meanfield-Potential ersetzt, und zwar derart, daß sich das asymptotische Verhalten des Ensembles nicht ändert. Im Orts-Geschwindigkeits-Phasenraum ergibt sich ein System schwach interagierender Diffusionsprozesse mit singulären Diffusionsmatrizen. Für diese Prozesse wird die Konvergenz gegen unabhängige identisch verteilte Grenzprozesse gezeigt, die ihrerseits Lösungen nichtlinearer stochastischer Differentialgleichungen sind. Mit Hilfe der Konvergenzresultate erhält man eine quasilineare parabolische Evolutionsgleichung für die Dynamik des Ensembles im Limes unendlich vieler Partikel. Aus dieser Gleichung wiederum lassen sich Transportgleichungen für Konzentration, Massenfluß etc. im Markov-Modell bestimmen. Entsprechende Transportgleichungen ergeben sich aus der Erhaltung von Masse und Moment für die Feststoffphase. Der Vergleich liefert Beziehungen zwischen den Parametern des stochastischen Modells und Momenten des Geschwindigkeits- und Konzentrationsfeldes.

Eichelsbacher, Peter Universität Bielefeld, Fakultät für Mathematik

Compound Poisson Approximation

Wir betrachten eine endliche Kollektion von Indizes I und für α ∈ I seien I_{α} 0-1-wertige Zufallsgröße, die abhängig sein könne Sei W = ∑_{α∈I} I_{α}. Die Poisson Approximation ist eine geeignete Approximation im Falle seltener Ereignisse. Nehmen die Zufallsgrößen Werte in der Menge der natürlichen Zahlen an, oder liegt ein Modell zugrunde, bei dem ”Klumpen” von 1-Werten (lokale Konzentrationen) vorkommen, erhofft man mittels einer Compound Poisson Approximation einer Verbesserung bestehender Resultate, also eine bessere Erfassung dieser speziellen Phänomene. Wir entwickeln eine Abschätzung des Totalvariations-Abstandes zwischen der Verteilung von W und einer (geeigneten) Compound Poisson Verteilung für Modelle, die mittels einer Klasse von assoziierten oder dissoziierten I_{α} beschrieben werden können. Die I_{α} nennt man assoziiert, wenn sie einer FKG-Ungleichung genügen, und dissoziiert, wenn (I_{α}, α ∈ A) und (I_{α}, α ∈ B) unabhängig sind für A ∩ B = ∅. Die Herleitung der Abschätzung basiert auf der Stein-Chen Methode, die für Compound Poisson Approximationen allgemein von Barbour, Chen und Loh 1992 eingeführt wurde. Wir erhalten obere Abschätzungen für

d_{T V} (L(W), CP (λ)),

wobei d_{T V} (·, ·) den Totalvariations-Abstand und CP (λ) ein spezielle Klasse von Compound Poisson Verteilungen mit Parameter λ bezeichnet.

Wir wenden dieses allgemeine Resultat auf unterschiedliche stochastische Modelle an. So erhalten wir bei der Bestimmung der Anzahl von k-runs in einer Bernoulli-Folge oder bei gewissen Zählstatistiken in einem zufällig gefärbten (festen) Graphen Verbesserungen der Konvergenzrate gegenüber Resultaten der Poisson Approximation. Asymptotische Entwicklungen unsere Resultate ermöglichen auch Anwendungen für spezielle U-Statistiken, wie sie bei interessanten ”DNA-breakage”-Modellen auftreten. Weiter wollen wir berichten, daß Konvergenzraten bei Compound Poisson Approximationen in Markovschen Zufallsfeldern endlicher Reichweite mit der Stein-Chen Methode erzielt werden können.

(gemeinsame Arbeit mit M. Roos, Universität Zürich)

Gnedin , Alexander Universität Göttingen

Sequentielle Auswahl monotoner Teilfolgen

Es werden verschiedene (auch multivariate) Versionen des folgenden Problems betrachtet. Seien X_{1}, X_{2}, … iid Beobachtungen. Eine online Auswahlstrategie wird definiert als die Folge τ = (τ_{1}, τ_{2}, …) von Stoppzeiten mit τ_{1} < τ_{2} < … und X_{τ_{1}} < X_{τ_{2}} < … Zum festen n, sei die Strategie τ durch EL_{n}(τ) bewertet, wobei L_{n}(τ) = max{i : τ_{i} ≤ n} die Länge der ausgewählten aufsteigenden Teilfolge ist. Das Problem ist, EL_{n}(τ) zu maximieren. Wir konstruieren asymptotisch optimale Strategien und untersuchen das Verhalten des Supremums für n → ∞.

Hasenfuss , Sven Universität Ulm

Leistungsanalyse von (max,+)-linearen Systemen mittels Taylor-Reihenentwicklungen

Unter gewissen Kopplungs- und Integrierbarkeitsbedingungen wird für eine Klasse von Funktionalen von markierten Poissonschen Punktprozessen gezeigt, daß diese bezüglich der Intensität in einer rechtsseitigen Umgebung des Nullpunktes differenzierbar sind. Dieses allgemeine Resultat kann dann beispielsweise dazu herangezogen werden, um Leistungskenngrößen von (max,+)-linearen Systemen mittels Taylor-Reihenentwicklungen zu untersuchen. (max,+)-lineare Systeme sind discrete event systems, deren zeitliche Entwicklung sich vollständig durch ein (in einem gewissen Sinne ”lineares“) Gleichungssystem beschreiben läßt, welches als einzige Operatoren ‘max’ und ‘+’ verwendet. In diese Klasse fallen neben zahlreichen Warteschlangennetzwerken auch Modelle aus der flexiblen Produktionsplanung, wie Kanban oder Job–Shop Systeme, und viele andere. Verschiedene Funktionale wie Laplace–Transformierte, höhere Momente oder Tailfunktionen von Wartezeiten in derartigen Systemen lassen sich in Taylor-Reihen entwickeln. Sowohl für transiente als auch stationäre Leistungskenngrößen werden die Taylor-Koeffizienten explizit bestimmt. Für eine Klasse von deterministischen Systemen ist es darüber hinaus möglich, durch explizite Auswertung des Restterms geschlossene Formeln für erwartete stationäre Wartezeiten zu bestimmen. Die hier vorgestellten Resultate wurden in Zusammenarbeit mit F. Baccelli und V. Schmidt erzielt.

Lakatos, Laszlo Eötvös Loránd University, Budapest, Hungary M/G/1 and related systems in equilibrium For characterization of equilibrium in the M/G/1 system one usually uses the Pollaczek-Khinchin formula, the generating function of ergodic distribution. The ergodicity theorem for Kovalenko’s piecewise-linear processes gives possibility to find the desired probabilities on the basis of duration of a busy period and times spent in different states for it. The same may be done for the system with vacation, i.e. in which after each busy period an additional time interval (called “vacation”) appears. The busy periods and vacations change till for a vacation no request enters (this sequence is called “cycle”). We introduce the notations: a_{k} and d_{k} - the probability of appearence of k requests for the service of a request and a cycle; ζ and ζ′ - the mean values of a busy period and a cycle; ξ_{i} and ξ′_{i} - the mean values of time spent on the i-th level for a busy period and a cycle; ρ = λτ - the utilization factor, λ is the arrival rate, τ is the mean value of service time of a request; η - the mean value of duration of a vacation. According to Kovalenko’s results the ergodic probabilities for the simple M/G/1 system are p_{i} = ξ_{i}/ζ (i = 0, 1, 2, …), for the system with vacation p′_{i} = ξ′_{i}/ζ′ (i = v, 0, 1, 2, …). The necessary mean values (ξ_{i} and ξ′_{i}) are determined by the following theorems: Theorem 1. In the M/G/1 system

ξ_{0} = τ, ξ_{1} = \frac{1 − a_{0}}{a_{0}} τ, ξ_{2} = \frac{1 − a_{0} − a_{1}}{a_{0}} (ξ_{0} + ξ_{1}),

and the mean values ξ_{k} (k ≥ 3) satisfy the recurrence relation

ξ_{k} = ∑_{i=1}^{k−2} \frac{1 − a_{0} − … − a_{i}}{a_{0}} ξ_{k−i} + \frac{1 − a_{0} − … − a_{k−1}}{a_{0}} (ξ_{0} + ξ_{1}).

Theorem 2. The mean values of time spent on the k-th level in the M/G/1 system with vacation ξ′_{k} satisfy the relations

ξ′_{v} = \frac{τ}{d_{0}} , ξ′_{0} = η, ξ′_{1} = \frac{τ}{a_{0}d_{0}} − τ + \frac{d_{1}}{d_{0}} (η − τ),

ξ′_{k} = ξ_{k} + ∑_{i=0}^{k−2} \frac{1 − d_{0} − … − d_{i}}{d_{0}} ξ_{k−i} + \frac{1 − d_{0} − … − d_{k−1}}{d_{0}} (ξ_{0} + ξ_{1}) + \frac{d_{k}}{d_{0}} (η − τ) (k ≥ 2),

where ξ_{i} (i ≥ 0) are determined by Theorem 1.

Seidel , Wilfried  v. Kocemba , Kai  Mitreiter , Klaus

Universität der Bundeswehr Hamburg

Zu Taylorreihenentwicklungen für Verweilzeiten in Tandemsystemen

Wir beschreiben einen Algorithmus zur Berechnung der Koeffizienten einer Taylorreihenentwicklung für Erwartungswerte stationärer Wartezeitverteilungen in Tandemsystemen. Dieser beruht auf einer von François Baccelli und Volker Schmidt entwickelten Reihenentwicklung für Momente stationärer Verweilzeitverteilungen in offenen (max,+)-linearen Systemen mit Poissonschen Input und läßt sich daher auch auf auf allgemeinere Warteschlangennetze übertragen. Die Koeffizienten sind als Erwartungswerte gewisser Polynome angegeben, deren Berechnung in der Regel hochdimensionale Integration erfordert. Unser Algorithmus unterstellt diskrete Bedienzeitverteilungen und arbeitet sehr effizient, wenn der Zufallsvektor der Bedienzeiten aller Stationen auf wenigen Atomen konzentriert ist.

In einer Simulationsstudie wird der Approximationsfehler untersucht. Für unabhängige Bedienzeiten gilt in guter Näherung eine einfache Faustregel, die unter der Annahme exponentialverteilter Bedienzeiten exakt hergeleitet werden kann.

Weiss , Gideon Hauptvortrag Haifa University

Fluid Models for Multi-Class Queueing Networks: Stability, Performance and Control

Multi-Class Queueing Networks — MCQN consist of nodes i = 1, …, I, classes k = 1, …, K, where C_{1}, …, C_{I} partitions the classes by nodes. Customers/parts arrive exogenously at rates α_{k}, queue up, are served at rate 1/m_{k} and then are routed between nodes or leave the system with probabilities P_{k,l}, 1−∑_{l} P_{k,l}; Q_{k,l}(t) denotes the queue length of class k parts. MCQN are useful to model manufacturing as well as communications systems. They differ from formerly studied single class queueing networks in that each node has several distinguishable classes of parts. I will focus mainly on Re-Entrant lines, a special class of MCQN where all parts follow a single deterministic route of successive production stages k = 1, …, K, which are common in semi-conductor wafer fabrication. Multi-Class Fluid Networks — MCFN have the same topology but rather than discrete stochastic parts they move continuous deterministic fluid, at rates proportional to the effort dedicated to each class by the node/machine. An MCQN will be approximated by a MCFN under fluid scaling, when state is counted in unit of n and time is speeded n fold. The fluid approximation of an MCQN in steady state is 0, hence uninformative, but the transient form, obtained by using n = ∑ Q_{k}(0) → ∞ turns out to be very informative in the study of stability, performance and control of MCQN. In the first half of the talk I will survey these briefly. Stability: The dynamics of a MCQN depend on the service discipline at the nodes — a MCQN may be unstable under a given discipline even when there is enough capacity at each node to handle the traffic (Kumar Seidman, Rybko Stolyar, Bramson). Dai’s theorem says that if the MCFN which is obtained by fluid scaling (the fluid limit model) is stable, then the original MCQN is stable under the given discipline. Stability of MCFN was established for FBFS, LBFS (first/last buffer first served) and for HOLPPS (head of the line proportional processor sharing) disciplines, and FIFO (first in first out) is stable for Fluid Kelly networks (Bramson). Performance: Various averaged performance measures (first moment, hence fluid information) need to satisfy relations which can be formulated as linear constraints. Regions of stability and of achievable performances may be derived or bounded by the solution of linear programs (Kumar Meyn, Bertsimas). For certain classes of networks the performance region is an extended polymatroid (Bertsimas Nino-Mora). Of practical interest is the global stability region — range of service rates for which a MCQN is stable under all work conserving disciplines. This has been characterized for 2 node MCFN (Dai Vande-Vate). Control: The optimality equations for average cost control of a MCQN can be formulated as g = max_{u}{c(Q, u)+A_{u}h(Q)} where g is the average cost, Q, u the queue state and the vector of controls (flow rates), c the cost rate, h the potential function, and A the infinitesimal generator. In the solution of these the main element is the potential function h. Meyn has shown that the fluid scaling of h is asymptotically equal to the optimal objective of the transient control problem for the corresponding MCFN. These results motivate the problem of optimal minimum inventory/cycle time draining of fluid re-entrant lines: Find fluid outflow rates u to:

max  ∫_{0}^{T} (T − t)u_{K}(t)dt

∫_{0}^{t} (u_{k}(s) − u_{k−1}(s)) ds ≤ a_{k}

∑_{k∈C_{i}} m_{k}u_{k}(t) ≤ 1

where a_{k} are the initial fluid levels. This is a Separated Continuous Linear Program, but its special structure suggests an efficient algorithm to solve it. I will discuss the solution for the 2 node case. The solution of the fluid draining problem is extremely informative. An important issue is how to implement a discipline for the control of a MCQN which follows the solution of the MCFN. I discuss possible implementations.

Wunderlich , Ralf TU Chemnitz

Dimensionsreduktion nichtlinearer zufälliger Schwingungssysteme

Bei der Modellierung realer Schwingungssysteme (z.B. von Fahrzeugen, Generatorwellen) können Differentialgleichungssysteme mit einer großen Anzahl von linearen als auch nichtlinearen Gleichungen entstehen. Werden zusätzlich zufällig gestörte Erregungen (Fahrwegunebenheiten, Lastschwankungen) berücksichtigt, so ergibt sich die Aufgabe, die statistischen Charakteristiken der Systemantwort, wie Mittelwert, Varianz, Korrelationsfunktion, zu bestimmen. Bei großen Systemen stößt man bei der Berechnung dieser Charakteristiken schnell an Grenzen. Es ist deshalb die Frage nach geeigneten Ersatzsystemen kleinerer Dimension von Interesse, welche das Originalsystem ”ausreichend” gut approximieren. Im Vortrag wird zunächst eine Methode zur Berechnung der genannten Charakteristiken für lineare und polynomial nichtlineare Systeme vorgestellt. Diese basiert auf der Theorie schwach korrelierter zufälliger Funktionen (vgl. [1],[2]). Durch Anwendung von Grenzwertsätzen dieser Theorie werden Approximationen der statistischen Charakteristiken als Entwicklungen nach der Korrelationslänge gefunden. Niedrigdimensionale Ersatzsysteme können abgeleitet werden, wenn Projektionen der Systemantwort auf geeignete lineare Untermannigfaltigkeiten des Zustandsraumes betrachtet werden. Der mittlere quadratische Abstand des Zustandsvektors von seiner Projektion ist Basis eines Gütemaßes, bezüglich dessen optimale Submannigfaltigkeiten bestimmt sowie Abschätzungen für den Fehler der Approximation der statistischen Charakteristiken angegeben werden. Literatur

[1] vom Scheidt, J.: Stochastic equations of mathematical physics. Akademie-Verlag, Berlin (1990)

[2] vom Scheidt, J.; Fellenberg, B.; Wöhrl, U.: Analyse und Simulation stochastischer Schwingungssysteme. Teubner, Stuttgart (1994)