28 results
Search Results
2. Multiple drawing multi-colour urns by stochastic approximation
- Author
-
Olfa Selmi, Cécile Mailler, and Nabil Lasmar
- Subjects
Statistics and Probability ,Mathematics(all) ,General Mathematics ,Markov process ,Stochastic approximation ,01 natural sciences ,Multiple drawing Pólya urn ,010104 statistics & probability ,symbols.namesake ,Polya urn ,stochastic approximation ,FOS: Mathematics ,0101 mathematics ,Mathematics ,Discrete mathematics ,discrete-time martingale ,Probability (math.PR) ,010102 general mathematics ,Ball (bearing) ,symbols ,limit theorem ,Statistics, Probability and Uncertainty ,reinforced process ,Mathematics - Probability - Abstract
A classical P��lya urn scheme is a Markov process whose evolution is encoded by a replacement matrix $(R_{i,j})_{1\leq i,j\leq d}$. At every discrete time-step, we draw a ball uniformly at random, denote its colour $c$, and replace it in the urn together with $R_{c,j}$ balls of colour $j$ (for all $1\leq j\leq d$). We are interested in multi-drawing P��lya urns, where the replacement rule depends on the random drawing of a set of $m$ balls from the urn (with or without replacement). This generalisation has already been studied in the literature, in particular by Kuba & Mahmoud (ArXiv:1503.09069 and 1509.09053), where second order asymptotic results are proved for $2$-colour urns under the balanced and the affinity assumptions. The main idea of this work is to apply stochastic approximation methods to this problem, which enables us to remove the affinity hypothesis of Kuba & Mahmoud and generalise the result to more-than-two-colour urns. We also give some partial results in the two-colour non-balanced case., This new arxiv version (v6) corrects a mistake that we discovered in the previous versions of this paper (v1-5). The mistake was in Theorem 1$(a)$ and in the last sentence of Theorem 4. In this new version, Theorem 1$(a)$ has been corrected, and Theorem 4 has been deleted
- Published
- 2018
3. Two queues in series with a finite, intermediate waitingroom
- Author
-
Marcel F. Neuts
- Subjects
Statistics and Probability ,Discrete mathematics ,Independent and identically distributed random variables ,Service (business) ,Queueing theory ,Series (mathematics) ,General Mathematics ,010102 general mathematics ,Poisson distribution ,01 natural sciences ,010104 statistics & probability ,symbols.namesake ,symbols ,0101 mathematics ,Statistics, Probability and Uncertainty ,Unit (ring theory) ,Random variable ,Queue ,Mathematics - Abstract
A service unit I, with Poisson input and general service times is in series with a unit II, with negative-exponential service times. The intermediate waitingroom can accomodate at most k persons and a customer cannot leave unit I when the waitingroom is full. The paper shows that this system of queues can be studied in terms of an imbedded semi-Markov process. Equations for the time dependent distributions are given, but the main emphasis of the paper is on the equilibrium conditions and on asymptotic results. 1. Description of the model The system of queues, discussed in this paper, consists of two units. Customers arrive at a first unit (I) according to a homogeneous Poisson process of rate 2. Their service times in unit I are independent, identically distributed random variables with common distribution function H(.). We assume that H(.) has a positive, finite mean a and we will denote the Laplace-Stieltjes transform of H( ) by h(s), Re s 0. Upon completion of service in unit I, all customers go on to a second unit (II) via a finite waitingroom. We assume that there can be not more than k customers in unit II and in the waitingroom at any time. If upon completion of service in unit I a customer finds the waitingroom full, then the unit I blocks until a service in unit II is completed. At that time he is allowed to enter the waitingroom. We assume that the service times in unit II are independent, identically distributed random variables with a negative-exponential distribution with mean 1/a. The service times in unit II are also stochastically independent of those in unit I and of the arrival process. The case k = 1, i.e., when no customers can wait between the two units, was studied by B. Avi-Itzhak and M. Yadin[1], T. Suzuki [11] and N. U. Prabhu [7]. These authors allow the service times in the second unit to have a general distribution. In the case of general k, we impose the requirement that these service Received 3 July 1967. Research supported in part by Office of Naval Research Contract NONR 1100(26). 123 This content downloaded from 157.55.39.217 on Mon, 18 Apr 2016 07:16:32 UTC All use subject to http://about.jstor.org/terms
- Published
- 1968
4. Stochastic Monotonicity and Duality of kth Order with Application to Put-Call Symmetry of Powered Options
- Author
-
Vassili N. Kolokoltsov
- Subjects
Statistics and Probability ,Stochastic monotonicity ,General Mathematics ,Markov process ,Duality (optimization) ,97M30 ,Monotonic function ,Perturbation function ,01 natural sciences ,dual semigroup ,62P05 ,010104 statistics & probability ,symbols.namesake ,60J25 ,FOS: Mathematics ,Strong duality ,Wolfe duality ,stochastic duality ,0101 mathematics ,Mathematics ,60J60 ,Discrete mathematics ,put-call symmetry and reversal ,powered and digital options ,Computer Science::Information Retrieval ,010102 general mathematics ,Probability (math.PR) ,generators of dual processes ,straddle ,Weak duality ,Valuation of options ,symbols ,60J75 ,Statistics, Probability and Uncertainty ,Mathematical economics ,Mathematics - Probability - Abstract
We introduce a notion of $k$th order stochastic monotonicity and duality that allows one to unify the notion used in insurance mathematics (sometimes refereed to as Siegmund's duality) for the study of ruin probability and the duality responsible for the so-called put - call symmetries in option pricing. Our general $k$th order duality can be financially interpreted as put - call symmetry for powered options. The main objective of the present paper is to develop an effective analytic approach to the analysis of duality leading to the full characterization of $k$th order duality of Markov processes in terms of their generators, which is new even for the well-studied case of put -call symmetries., Comment: To appear in Journal of Applied Probability 52:1 (March 2015)
- Published
- 2015
5. Exponential Random Graphs as Models of Overlay Networks
- Author
-
Ayalvadi Ganesh, Moez Draief, and Laurent Massoulié
- Subjects
Statistics and Probability ,Dense graph ,General Mathematics ,Symmetric graph ,01 natural sciences ,law.invention ,Combinatorics ,010104 statistics & probability ,symbols.namesake ,Pathwidth ,law ,Line graph ,Random regular graph ,FOS: Mathematics ,0101 mathematics ,Mathematics ,Random graph ,Block graph ,Discrete mathematics ,Probability (math.PR) ,010102 general mathematics ,Planar graph ,symbols ,Statistics, Probability and Uncertainty ,Mathematics - Probability ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
In this paper, we give an analytic solution for graphs with n nodes and E edges for which the probability of obtaining a given graph G is specified in terms of the degree sequence of G. We describe how this model naturally appears in the context of load balancing in communication networks, namely Peer-to-Peer overlays. We then analyse the degree distribution of such graphs and show that the degrees are concentrated around their mean value. Finally, we derive asymptotic results on the number of edges crossing a graph cut and use these results $(i)$ to compute the graph expansion and conductance, and $(ii)$ to analyse the graph resilience to random failures., Comment: 18 pages
- Published
- 2009
6. Continuous-State Branching Processes and Self-Similarity
- Author
-
Andreas E. Kyprianou and Juan Carlos Pardo
- Subjects
Statistics and Probability ,Discrete mathematics ,Self-similarity ,General Mathematics ,010102 general mathematics ,Markov process ,State (functional analysis) ,01 natural sciences ,Branching (linguistics) ,010104 statistics & probability ,symbols.namesake ,Transformation (function) ,symbols ,Statistical physics ,0101 mathematics ,Statistics, Probability and Uncertainty ,Mathematics ,Branching process - Abstract
In this paper we study the α-stable continuous-state branching processes (for α ∈ (1, 2]) and the α-stable continuous-state branching processes conditioned never to become extinct in the light of positive self-similarity. Understanding the interaction of the Lamperti transformation for continuous-state branching processes and the Lamperti transformation for positive, self-similar Markov processes gives access to a number of explicit results concerning the paths of α-stable continuous-state branching processes and α-stable continuous-state branching processes conditioned never to become extinct.
- Published
- 2008
7. A matrix-analytic approach to the N-player ruin problem
- Author
-
Yvik Swan and F Thomas Bruss
- Subjects
Statistics and Probability ,Discrete mathematics ,Markov chain ,General Mathematics ,010102 general mathematics ,Applied probability ,Hitting time ,Markov process ,Ruin theory ,01 natural sciences ,Combinatorics ,010104 statistics & probability ,symbols.namesake ,Absorbing Markov chain ,symbols ,Phase-type distribution ,0101 mathematics ,Statistics, Probability and Uncertainty ,First-hitting-time model ,Mathematics - Abstract
Consider N players, respectively owning x1, x2, …, xN monetary units, who play a sequence of games, winning from and losing to each other integer amounts according to fixed rules. The sequence stops as soon as (at least) one player is ruined. We are interested in the ruin process of these N players, i.e. in the probability that a given player is ruined first, and also in the expected ruin time. This problem is called the N-player ruin problem. In this paper, the problem is set up as a multivariate absorbing Markov chain with an absorbing state corresponding to the ruin of each player. This is then discussed in the context of phase-type distributions where each phase is represented by a vector of size N and the distribution has as many absorbing points as there are ruin events. We use this modified phase-type distribution to obtain an explicit solution to the N-player problem. We define a partition of the set of transient states into different levels, and on it give an extension of the folding algorithm (see Ye and Li (1994)). This provides an efficient computational procedure for calculating some of the key measures.
- Published
- 2006
8. On ordered series and later waiting time distributions in a sequence of Markov dependent multistate trials
- Author
-
Yung-Ming Chang and James C. Fu
- Subjects
Statistics and Probability ,Discrete mathematics ,Markov chain mixing time ,Markov chain ,General Mathematics ,Variable-order Markov model ,010102 general mathematics ,Discrete phase-type distribution ,Markov process ,Markov model ,01 natural sciences ,010104 statistics & probability ,symbols.namesake ,Markov renewal process ,symbols ,Applied mathematics ,Markov property ,0101 mathematics ,Statistics, Probability and Uncertainty ,Mathematics - Abstract
The sooner and later waiting time problems have been extensively studied and applied in various areas of statistics and applied probability. In this paper, we give a comprehensive study of ordered series and later waiting time distributions of a number of simple patterns with respect to nonoverlapping and overlapping counting schemes in a sequence of Markov dependent multistate trials. Exact distributions and probability generating functions are derived by using the finite Markov chain imbedding technique. Examples are given to illustrate our results.
- Published
- 2003
9. Output analysis of a single-buffer multiclass queue: FCFS service
- Author
-
Vidyadhar G. Kulkarni and K. D. Glazebrook
- Subjects
Statistics and Probability ,Discrete mathematics ,General Mathematics ,010102 general mathematics ,Markov process ,01 natural sciences ,010104 statistics & probability ,symbols.namesake ,First-come, first-served ,M/G/1 queue ,Fluid queue ,symbols ,Renewal theory ,0101 mathematics ,Statistics, Probability and Uncertainty ,First-hitting-time model ,Constant (mathematics) ,Queue ,Algorithm ,Mathematics - Abstract
We consider an infinite capacity buffer where the incoming fluid traffic belongs to K different types modulated by K independent Markovian on-off processes. The kth input process is described by three parameters: (λk, μk, rk), where 1/λk is the mean off time, 1/μk is the mean on time, and rk is the constant peak rate during the on time. The buffer empties the fluid at rate c according to a first come first served (FCFS) discipline. The output process of type k fluid is neither Markovian, nor on-off. We approximate it by an on-off process by defining the process to be off if no fluid of type k is leaving the buffer, and on otherwise. We compute the mean on time τkon and mean off time τkoff. We approximate the peak output rate by a constant rko so as to conserve the fluid. We approximate the output process by the three parameters (λko, μko, rko), where λko = 1/τkoff, and μko = 1/τkon. In this paper we derive methods of computing τkon, τkoff and rko for k = 1, 2,…, K. They are based on the results for the computation of expected reward in a fluid queueing system during a first passage time. We illustrate the methodology by a numerical example. In the last section we conduct a similar output analysis for a standard M/G/1 queue with K types of customers arriving according to independent Poisson processes and requiring independent generally distributed service times, and following a FCFS service discipline. For this case we are able to get analytical results.
- Published
- 2002
10. Optimal estimation of diffusion processes hidden by general obstacles
- Author
-
Hyung Geun Kim and Dougu Nam
- Subjects
Discrete mathematics ,Statistics and Probability ,Optimal estimation ,Stochastic process ,General Mathematics ,010102 general mathematics ,Estimator ,Markov process ,Function (mathematics) ,01 natural sciences ,010104 statistics & probability ,symbols.namesake ,Diffusion process ,Bounded function ,Calculus ,symbols ,0101 mathematics ,Diffusion (business) ,Statistics, Probability and Uncertainty ,Mathematics - Abstract
Let X t be an n-dimensional diffusion process and S(t) be a set-valued function. Suppose X t is invisible when it is hidden by S(t), but we can see the process exactly otherwise. In this paper, we derive the optimal estimator E[f(X 1) | X s 1 X s ∉S(s), 0 ≤ s ≤ 1] for a bounded Borel function f. We illustrate some computations for Gauss-Markov processes.
- Published
- 2001
11. Continuous-time Markov additive processes: Composition of large deviations principles and comparison between exponential rates of convergence
- Author
-
Claudio Macci
- Subjects
Discrete mathematics ,Statistics and Probability ,Markov chain ,Markov additive process ,General Mathematics ,010102 general mathematics ,Markov process ,Composition (combinatorics) ,01 natural sciences ,Exponential function ,Settore MAT/06 - Probabilita' e Statistica Matematica ,symbols.namesake ,010104 statistics & probability ,Rate of convergence ,symbols ,Calculus ,Large deviations theory ,0101 mathematics ,Statistics, Probability and Uncertainty ,Rate function ,Mathematics - Abstract
We consider a continuous-time Markov additive process (J t ,S t ) with (J t ) an irreducible Markov chain on E = {1,…,s}; it is known that (S t /t) satisfies the large deviations principle as t → ∞. In this paper we present a variational formula H for the rate function κ∗ and, in some sense, we have a composition of two large deviations principles. Moreover, under suitable hypotheses, we can consider two other continuous-time Markov additive processes derived from (J t ,S t ): the averaged parameters model (J t ,S t (A)) and the fluid model (J t ,S t (F)). Then some results of convergence are presented and the variational formula H can be employed to show that, in some sense, the convergences for (J t ,S t (A)) and (J t ,S t (F)) are faster than the corresponding convergences for (J t ,S t ).
- Published
- 2001
12. The detection of words and an ordering for Markov chains
- Author
-
Albrecht Irle and Joseph Gani
- Subjects
Statistics and Probability ,Discrete mathematics ,Markov chain ,Interacting particle system ,General Mathematics ,010102 general mathematics ,Discrete phase-type distribution ,Markov process ,01 natural sciences ,Stochastic ordering ,Combinatorics ,Continuous-time Markov chain ,010104 statistics & probability ,symbols.namesake ,symbols ,Examples of Markov chains ,Markov property ,0101 mathematics ,Statistics, Probability and Uncertainty ,Mathematics - Abstract
This paper considers the occurrence of patterns in sequences of independent trials from a finite alphabet; Gani and Irle (1999) have described a finite state automaton which identifies exactly those sequences of symbols containing the specific pattern, which may be thought of as the word of interest. Each word generates a particular Markov chain. Motivated by a result of Guibas and Odlyzko (1981) on stochastic monotonicity for the random times when a particular word is completed for the first time, a new level-crossing ordering is introduced for stochastic processes. A process {Yn : n = 0, 1, …} is slower in level-crossing than a process {Zn }, if it takes {Yn } stochastically longer than {Zn } to exceed any given level. This relation is shown to be useful for the comparison of stochastic automata, and is used to investigate this ordering for Markov chains in discrete time.
- Published
- 2001
13. A refinement of multivariate Bonferroni-type inequalities
- Author
-
E. Seneta and Tuhao Chen
- Subjects
Statistics and Probability ,Discrete mathematics ,Multivariate statistics ,biology ,General Mathematics ,010102 general mathematics ,Sharpening ,Bivariate analysis ,Type (model theory) ,biology.organism_classification ,01 natural sciences ,Upper and lower bounds ,Inequalities in information theory ,Combinatorics ,010104 statistics & probability ,symbols.namesake ,Bonferroni correction ,Chen ,symbols ,0101 mathematics ,Statistics, Probability and Uncertainty ,Mathematics - Abstract
Technology developed in a predecessor paper (Chen and Seneta (1996)) is applied to provide, in a unified manner, a sharpening of bivariate Bonferroni-type bounds on P(v 1≥r, v 2≥u) obtained by Galambos and Lee (1992; upper bound) and Chen and Seneta (1986; lower bound).
- Published
- 2000
14. Phase transition in the random triangle model
- Author
-
Johan Jonasson and Olle Häggström
- Subjects
Statistics and Probability ,Random graph ,Discrete mathematics ,Phase transition ,General Mathematics ,010102 general mathematics ,Duality (order theory) ,Critical value ,01 natural sciences ,Combinatorics ,010104 statistics & probability ,symbols.namesake ,symbols ,Hexagonal lattice ,Ising model ,0101 mathematics ,Statistics, Probability and Uncertainty ,Gibbs measure ,Probability measure ,Mathematics - Abstract
The random triangle model was recently introduced as a random graph model that captures the property of transitivity that is often found in social networks, i.e. the property that given that two vertices are second neighbors, they are more likely to be neighbors. For parameters p ∊ [0,1] and q ≥ 1, and a finite graph G = (V, E), it assigns to elements η of {0,1} E probabilities which are proportional to where t(η) is the number of triangles in the open subgraph. In this paper the behavior of the random triangle model on the two-dimensional triangular lattice is studied. By mapping the system onto an Ising model with external field on the hexagonal lattice, it is shown that phase transition occurs if and only if p = (q−1)−2/3 and q > q c for a critical value q c which turns out to equal It is furthermore demonstrated that phase transition cannot occur unless p = p c (q), the critical value for percolation of open edges for given q. This implies that for q ≥ q c , p c (q) = (q−1)−2/3.
- Published
- 1999
15. Duality results for block-structured transition matrices
- Author
-
Attahiru Sule Alfa, Wei Li, and Yiqiang Q. Zhao
- Subjects
Discrete mathematics ,Statistics and Probability ,Pure mathematics ,Markov chain ,General Mathematics ,010102 general mathematics ,Stochastic matrix ,Duality (optimization) ,Block matrix ,Markov process ,01 natural sciences ,Matrix (mathematics) ,symbols.namesake ,010104 statistics & probability ,Markov renewal process ,symbols ,Renewal theory ,0101 mathematics ,Statistics, Probability and Uncertainty ,Mathematics - Abstract
In this paper, we consider a certain class of Markov renewal processes where the matrix of the transition kernel governing the Markov renewal process possesses some block-structured property, including repeating rows. Duality conditions and properties are obtained on two probabilistic measures which often play a key role in the analysis and computations of such a block-structured process. The method used here unifies two different concepts of duality. Applications of duality are also provided, including a characteristic theorem concerning recurrence and transience of a transition matrix with repeating rows and a batch arrival queueing model.
- Published
- 1999
16. Asymptotic behavior of a multiplexer fed by a long-range dependent process
- Author
-
Don Towsley, Philippe Nain, Zhen Liu, and Zhi-Li Zhang
- Subjects
Discrete mathematics ,Statistics and Probability ,Exponential distribution ,Distribution (number theory) ,Stochastic process ,General Mathematics ,010102 general mathematics ,01 natural sciences ,Combinatorics ,symbols.namesake ,010104 statistics & probability ,Log-normal distribution ,symbols ,Large deviations theory ,Pareto distribution ,0101 mathematics ,Statistics, Probability and Uncertainty ,Constant (mathematics) ,Queue ,Mathematics - Abstract
In this paper we study the asymptotic behavior of the tail of the stationary backlog distribution in a single server queue with constant service capacity c, fed by the so-called M/G/∞ input process or Cox input process. Asymptotic lower bounds are obtained for any distribution G and asymptotic upper bounds are derived when G is a subexponential distribution. We find the bounds to be tight in some instances, e.g. when G corresponds to either the Pareto or lognormal distribution and c − ρ < 1, where ρ is the arrival rate at the buffer.
- Published
- 1999
17. On the Inverse of Erlang's Function
- Author
-
S. A. Berezner, Peter G. Taylor, and A. E. Krzesinski
- Subjects
Discrete mathematics ,Statistics and Probability ,Queueing theory ,021103 operations research ,General Mathematics ,Erlang distribution ,0211 other engineering and technologies ,Inverse ,02 engineering and technology ,Poisson distribution ,Upper and lower bounds ,Erlang (unit) ,01 natural sciences ,Combinatorics ,symbols.namesake ,010104 statistics & probability ,symbols ,Probability distribution ,Linear approximation ,0101 mathematics ,Statistics, Probability and Uncertainty ,Mathematics - Abstract
Erlang's functionB(λ,C) gives the blocking probability that occurs when Poisson traffic of intensity λ is offered to a link consisting ofCcircuits. However, when dimensioning a telecommunications network, it is more convenient to use the inverseC(λ,B) of Erlang's function, which gives the number of circuits needed to carry Poisson traffic λ with blocking probability at mostB. This paper derives simple bounds forC(λ,B). These bounds are close to each other and the upper bound provides an accurate linear approximation toC(λ,B) which is asymptotically exact in the limit as λ approaches infinity withBfixed
- Published
- 1998
18. Detailed probabilistic analysis of the integrated three-valued telegraph signal
- Author
-
Enzo Orsingher and Ilaria Di Matteo
- Subjects
Statistics and Probability ,Discrete mathematics ,General Mathematics ,010102 general mathematics ,Conditional probability distribution ,Conditional expectation ,01 natural sciences ,Signal ,010104 statistics & probability ,symbols.namesake ,Fourier transform ,ComputingMethodologies_DOCUMENTANDTEXTPROCESSING ,symbols ,Initial value problem ,Probabilistic analysis of algorithms ,0101 mathematics ,Statistics, Probability and Uncertainty ,Hyperbolic partial differential equation ,Algorithm ,Telegraph process ,Mathematics - Abstract
In this paper the integrated three-valued telegraph process is examined. In particular, the third-order equations governing the distributions , (where N(t) denotes the number of changes of the telegraph process up to time t) are derived and recurrence relationships for them are obtained by solving suitable initial-value problems. These recurrence formulas are related to the Fourier transform of the conditional distributions and are used to obtain explicit results for small values of k. The conditional mean values (where V(0) denotes the initial velocity of motions) are obtained and discussed.
- Published
- 1997
19. A sample path analysis of the M/M/1 queue
- Author
-
William A. Massey and François Baccelli
- Subjects
Statistics and Probability ,Discrete mathematics ,Queueing theory ,Laplace transform ,General Mathematics ,010102 general mathematics ,M/M/1 queue ,Random walk ,01 natural sciences ,Combinatorics ,010104 statistics & probability ,symbols.namesake ,Distribution (mathematics) ,Path (graph theory) ,symbols ,0101 mathematics ,Statistics, Probability and Uncertainty ,Queue ,Bessel function ,Mathematics - Abstract
The exact solution for the transient distribution of the queue length and busy period of the M/M/1 queue in terms of modified Bessel functions has been proved in a variety of ways. Methods of the past range from spectral analysis (Lederman and Reuter (1954)), combinatorial arguments (Champernowne (1956)), to generating functions coupled with Laplace transforms (Clarke (1956)). In this paper, we present a novel approach that ties the computation of these transient distributions directly to the random sample path behavior of the M/M/1 queue. The use of Laplace transforms is minimized, and the use of generating functions is eliminated completely. This is a method that could prove to be useful in developing a similar transient analysis for queueing networks.
- Published
- 1989
20. An optimal sequential policy for controlling a Markov renewal process
- Author
-
J. M. McNamara
- Subjects
Discrete mathematics ,Statistics and Probability ,Sequence ,General Mathematics ,010102 general mathematics ,Structure (category theory) ,Process (computing) ,Markov process ,Partially observable Markov decision process ,01 natural sciences ,symbols.namesake ,Continuation ,010104 statistics & probability ,Markov renewal process ,symbols ,Renewal theory ,0101 mathematics ,Statistics, Probability and Uncertainty ,Mathematics - Abstract
This paper discusses a renewal process whose time development between renewals is described by a Markov process. The process may be controlled by choosing the times at which renewal occurs, the objective of the control being to maximise the long-term average rate of reward. Let γ ∗ denote the maximum achievable rate. We consider a specific policy in which a sequence of estimates of γ ∗ is made. This sequence is defined inductively as follows. Initially an (a priori)estimate γo is chosen. On making the nth renewal one estimates γ ∗ in terms of γ o, the total rewards obtained in the first n renewal cycles and the total length of these cycles. γ n then determines the length of the (n + 1)th cycle. It is shown that γ n tends to γ ∗ as n tends to∞, and that this policy is optimal. The time at which the (n + 1)th renewal is made is determined by solving a stopping problem for the Markov process with continuation cost γ n per unit time and stopping reward equal to the renewal reward. Thus, in general, implementation of this policy requires a knowledge of the transition probabilities of the Markov process. An example is presented in which one needs to know essentially nothing about the details of this process or the fine details of the reward structure in order to implement the policy. The example is based on a problem in biology.
- Published
- 1985
21. Note on the reversible counters system of Lampard
- Author
-
R. M. Phatarfod
- Subjects
Statistics and Probability ,Discrete mathematics ,Markov sequence ,General Mathematics ,010102 general mathematics ,Negative binomial distribution ,Process (computing) ,Poisson process ,Extension (predicate logic) ,Bivariate analysis ,Poisson distribution ,01 natural sciences ,010104 statistics & probability ,symbols.namesake ,symbols ,Statistical physics ,0101 mathematics ,Statistics, Probability and Uncertainty ,Mathematics - Abstract
The paper considers an extension to the reversible counters system of Lampard [1]. In Lampard's model the input processes are two independent Poisson processes; this results in a gamma Markov sequence for the time-interval between successive output pulses and a negative binomial Markov sequence for the counts at the times of out-put pulses. We consider the input process to be a bivariate Poisson process and show that the first out-put process given above is not affected, while the second out-put-process becomes of a type studied in the theory of branching processes.
- Published
- 1974
22. Optimal list order under partial memory constraints
- Author
-
Yi C Kan and Sheldon M. Ross
- Subjects
Statistics and Probability ,Discrete mathematics ,General Mathematics ,010102 general mathematics ,Markov process ,01 natural sciences ,Combinatorics ,010104 statistics & probability ,Permutation ,symbols.namesake ,Monotone polygon ,Ranking ,Position (vector) ,Convergence (routing) ,symbols ,Order (group theory) ,0101 mathematics ,Statistics, Probability and Uncertainty ,Unit (ring theory) ,Mathematics - Abstract
The problem of interest is to determine the optimal ordering so as to minimize the long run average cost. Clearly if the P sub i were known the optimal ordering would simply be to order the elements in decreasing order of the P sub i's. In fact even if the P sub i's were unknown we could do as well asymptotically by ordering the elements at each unit of time in decreasing order of the number of previous requests for them. In this paper we first consider the case in which the only memory allowed at any time is the ordering of the elements at that time; in other words, the only type of reordering rules we allow are ones in which the reordered permutation of elements at any time is only allowed to depend on the present ordering and the position of the element requested. We also consider the above problem under the previse that additional memory is allowed. In particular we allow the decision-maker to utilize such rules as 'only make a change (according to some preassigned rule) if the same element has been requested k times in a row.' We show that as k approaches infinity we can do as well as if we knew the values of the P sub i, and in addition we show that the convergence is monotone.
- Published
- 1980
23. On sojourn time in Jackson networks of queues
- Author
-
Austin J. Lemoine
- Subjects
Statistics and Probability ,Discrete mathematics ,Recursion ,Laplace transform ,General Mathematics ,010102 general mathematics ,Markov process ,System of linear equations ,Flow network ,Residual ,01 natural sciences ,010104 statistics & probability ,symbols.namesake ,symbols ,0101 mathematics ,Statistics, Probability and Uncertainty ,Martingale (probability theory) ,Queue ,Mathematics - Abstract
This paper is about representations for equilibrium sojourn time distributions in Jackson networks of queues. For a network with N single-server nodes let hi be the Laplace transform of the residual system sojourn time for a customer ‘arriving' to node i, ‘arrival' meaning external input or internal transfer. The transforms {hi : i = 1, ···, N} are shown to satisfy a system of equations we call the network flow equations. These equations lead to a general recursive representation for the higher moments of the sojourn time variables {Ti : i = 1, ···, N}. This recursion is discussed and then, by way of illustration, applied to the single-server Markovian queue with feedback.
- Published
- 1987
24. Limit theorems for processes such as the Markov branching process
- Author
-
Andrew Barbour
- Subjects
Statistics and Probability ,Discrete mathematics ,Markov kernel ,Markov chain ,General Mathematics ,010102 general mathematics ,Markov process ,Continuous mapping theorem ,01 natural sciences ,Time reversibility ,Combinatorics ,010104 statistics & probability ,symbols.namesake ,Markov renewal process ,symbols ,Markov property ,0101 mathematics ,Statistics, Probability and Uncertainty ,Mathematics ,Branching process - Abstract
Let X(t) be a continuous time Markov process on the integers such that, if σ is a time at which X makes a jump, X(σ)– X(σ–) is distributed independently of X(σ–), and has finite mean μ and variance. Let q(j) denote the residence time parameter for the state j. If tn denotes the time of the nth jump and Xn ≡ X(tb), it is easy to deduce limit theorems for from those for sums of independent identically distributed random variables. In this paper, it is shown how, for μ > 0 and for suitable q(·), these theorems can be translated into limit theorems for X(t), by using the continuous mapping theorem.
- Published
- 1975
25. Average delay in queues with non-stationary Poisson arrivals
- Author
-
Sheldon M. Ross
- Subjects
Discrete mathematics ,Statistics and Probability ,Queueing theory ,Stochastic process ,General Mathematics ,010102 general mathematics ,Poisson distribution ,01 natural sciences ,Combinatorics ,symbols.namesake ,010104 statistics & probability ,Arrival theorem ,Compound Poisson process ,symbols ,Almost surely ,Markovian arrival process ,Fractional Poisson process ,0101 mathematics ,Statistics, Probability and Uncertainty ,Mathematics - Abstract
One of the major difficulties in attempting to apply known queueing theory results to real problems is that almost always these results assume a time-stationary Poisson arrival process, whereas in practice the actual process is almost invariably non-stationary. In this paper we consider single-server infinite-capacity queueing models in which the arrival process is a non-stationary process with an intensity function ∧(t), t ≧ 0, which is itself a random process. We suppose that the average value of the intensity function exists and is equal to some constant, call it λ, with probability 1. We make a conjecture to the effect that ‘the closer {∧(t), t ≧ 0} is to the stationary Poisson process with rate λ ' then the smaller is the average customer delay, and then we verify the conjecture in the special case where the arrival process is an interrupted Poisson process.
- Published
- 1978
26. On the characterization of point processes with the order statistic property without the moment condition
- Author
-
Prem S. Puri
- Subjects
Discrete mathematics ,Statistics and Probability ,Property (philosophy) ,General Mathematics ,Order statistic ,010102 general mathematics ,Markov process ,Characterization (mathematics) ,Poisson distribution ,01 natural sciences ,Point process ,Moment (mathematics) ,symbols.namesake ,010104 statistics & probability ,Transformation (function) ,symbols ,Applied mathematics ,0101 mathematics ,Statistics, Probability and Uncertainty ,Mathematics - Abstract
The paper characterizes point processes with the order statistic property without the unnecessary condition of finiteness of the first moment of the process, a condition imposed by previous researchers. It shows that the class of these processes is composed only of mixed Poisson processes up to a time-scale transformation and of the mixed sample processes. It also introduces a multivariate analog of the order statistic property and characterizes completely the class of multivariate point processes with this property.
- Published
- 1982
27. On the autocorrelation and spectral functions of queues
- Author
-
John F. Reynolds
- Subjects
Discrete mathematics ,Statistics and Probability ,Autocorrelation technique ,M/G/k queue ,General Mathematics ,010102 general mathematics ,M/M/1 queue ,Spectral density ,01 natural sciences ,symbols.namesake ,010104 statistics & probability ,Fourier transform ,Autocorrelation matrix ,symbols ,M/G/1 queue ,M/M/c queue ,0101 mathematics ,Statistics, Probability and Uncertainty ,Mathematics - Abstract
This paper considers the autocorrelation function of queue length and the corresponding spectral density (i.e., its Fourier transform). Some general expressions are obtained using generating functions and matrices, and applied to M/M/1 and M [x]/M/∞ queues.
- Published
- 1968
28. On the waiting time distribution in a generalized GI/G/1 queueing system
- Author
-
Jacqueline Loris-Teghem
- Subjects
Statistics and Probability ,Kendall's notation ,Discrete mathematics ,Independent and identically distributed random variables ,Queueing theory ,021103 operations research ,General Mathematics ,0211 other engineering and technologies ,Markov process ,02 engineering and technology ,01 natural sciences ,010104 statistics & probability ,symbols.namesake ,Mean value analysis ,symbols ,0101 mathematics ,Statistics, Probability and Uncertainty ,Random variable ,Bulk queue ,Queue ,Mathematics - Abstract
The model considered in this paper describes a queueing system in which the station is dismantled at the end of a busy period and re-established on arrival of a new customer, in such a way that the closing-down process consists of N1 phases of random duration and that a customer 𝒞n who arrives while the station is being closed down must wait a random time idn(i = 1, ···, N1) if the ith phase is going on at the arrival instant. (For each fixed index i, the random variables idn are identically distributed.) A customer 𝒞n arriving when the closing-down of the station is already accomplished has to wait a random time (N1 + 1)dn corresponding to the set up time of the station. Besides, a customer 𝒞n who arrives when the station is busy has to wait an additional random time 0dn. We thus have (N1 + 2) types of “delay” (additional waiting time). Similarly, we consider (N2 + 2) types of service time and (N3 + 2) probabilities of joining the queue. This may be formulated as a model with (N + 2) types of triplets (delay, service time, probability of joining the queue). We consider the general case where the random variables defining the model all have an arbitrary distribution.The process {wn}, where wn denotes the waiting time of customer 𝒞n if he joins the queue at all, is not necessarily Markovian, so that we first study (by algebraic considerations) the transient behaviour of a Markovian process {vn} related to {wn}, and then derive the distribution of the variables wn.
- Published
- 1971
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.