THE EXACT TAIL ASYMPTOTICS BEHAVIOUR OF THE JOINT STATIONARY DISTRIBUTIONS OF THE GENERALIZED JOIN THE SHORTEST QUEUEING MODEL by ZAFAR ZAFARI B.Sc., Amirkabir University of Technology (Tehran Polytechnic), 2010 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in THE COLLEGE OF GRADUATE STUDIES (Mathematics) THE UNIVERSITY OF BRITISH COLUMBIA (Okanagan) April 2012 c©Zafar Zafari, 2012Abstract Parallel queueing networks have advantage over single server queue- ing networks, because when some servers simultaneously serve the customers in the line, the efficiency increases. Therefore, in the real world parallel queueing servers such as computer networks and mul- tiple parallel processors, have become common. Since then many scientists have been studying the analysis of parallel queueing net- works to give the exact practical models for the real world queueing problems. One of the topics in parallel queueing networks is the two-dimensional random walk, which recently have been studied by many scientists. The formulation for a random walk model in the first quadrant has been already studied by Fayolle, Malyshev and Iasnogorodski [19]. In this thesis I extend the formulation of a general random walk model to the half plane, including the first and fourth quadrants, and by using kernel method and Tauberian-like Theorem I inves- tigate the exact tail asymptotic behaviour of the joint stationary distribution of the generating functions. In addition, I apply the results of the formulation of a general ran- dom walk model in the half plane to the Generalized-JSQ model, which is a queueing system with two parallel servers that have three streams of arrivals, two of which are dedicated to each servers, and the third one joins the shorter queue. Suppose that arrivals are independent Poisson processes, and service times have identical ex- ponential distributions. Although this queueing model has been al- ready studied by Zhao and Grassmann [75], and M. Miyazawa, [56], in this thesis I will use a different method named kernel method to investigate the exact tail asymptotic behaviour of the generat- iiing functions. The kernel method is simpler and faster than other methods, since in this method we are not dealing with the explicit expressions in terms of generating functions, but we only discuss the dominant singularity and its location. iiiTable of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . ii Table of Contents . . . . . . . . . . . . . . . . . . . . iv Acknowledgements . . . . . . . . . . . . . . . . . . . . vi Dedication . . . . . . . . . . . . . . . . . . . . . . . . vii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Motivation and Contribution . . . . . . . . . . . . . . 1 1.2 Literature Review . . . . . . . . . . . . . . . . . . . . 2 1.3 Organization . . . . . . . . . . . . . . . . . . . . . . . 3 2 Background . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1 Queueing Theory . . . . . . . . . . . . . . . . . . . . . 5 2.1.1 Counting Process . . . . . . . . . . . . . . . . . 5 2.1.2 Poisson Process . . . . . . . . . . . . . . . . . . 6 2.1.3 Markov Chain . . . . . . . . . . . . . . . . . . . 6 2.1.4 Champan-Kolmogorov Equations . . . . . . . . . 8 2.1.5 Queueing Models . . . . . . . . . . . . . . . . . . 8 2.2 Transition Probabilities . . . . . . . . . . . . . . . . . 9 2.3 Random Walk in the Quarter Plane . . . . . . . . . . . 10 2.4 Generating Functions . . . . . . . . . . . . . . . . . . . 11 2.4.1 Queueing Examples . . . . . . . . . . . . . . . . 14 2.5 Stability Condition . . . . . . . . . . . . . . . . . . . . 18 2.6 Riemann Surfaces . . . . . . . . . . . . . . . . . . . . . 22 2.6.1 Genus 1 or Genus 0 . . . . . . . . . . . . . . . . 24 2.7 Analysis of the Kernel . . . . . . . . . . . . . . . . . . 24 iv2.7.1 Queueing Examples . . . . . . . . . . . . . . . . 25 3 Exact Tail Asymptotic Analysis of a General Ran- dom Walk Model Using Kernel Method . . . . . . . 28 3.1 Kernel Method and Generating Functions . . . . . . . 28 3.2 Key Kernel . . . . . . . . . . . . . . . . . . . . . . . . 34 3.3 Asymptotic Analysis of P0(x), Q0(y) and Q(−)0 (y) . . . 38 3.4 Tauberian-Like Theorem . . . . . . . . . . . . . . . . . 40 3.5 Exact Tail Asymptotic for P0(x) . . . . . . . . . . . . 41 3.6 Exact Tail Asymptotic for Q0(y) . . . . . . . . . . . . 60 4 Exact Tail Asymptotic Behaviour of the Joint Sta- tionary Distributions of Generalized-JSQ with Ker- nel Method . . . . . . . . . . . . . . . . . . . . . . . . 66 4.1 Generalized-JSQ Model and Kernel Method . . . . . . 66 4.2 Branch Points and Branches . . . . . . . . . . . . . . . 70 4.3 Asymptotic Analysis of P0(x) of the Generalized-JSQ . 71 4.4 Asymptotic Analysis of Q0(y) of the Generalized-JSQ . 73 4.5 Asymptotic Analysis of Q(−)0 (y) of the Generalized-JSQ 74 4.6 Exact Tail Asymptotic for P0(x) of the Generalized-JSQ 75 4.7 Exact Tail Asymptotic for Q0(y) of the Generalized-JSQ 78 5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 80 Bibliography . . . . . . . . . . . . . . . . . . . . . . . 82 vAcknowledgements I offer my enduring gratitude to my supervisor, Dr. Javad Tavakoli, and my co-supervisor, Dr. Winfried K. Grassmann, who have in- spired me to continue my work in this field. I owe particular thanks to Dr. Yiqiang Q. Zhao, whom I have spent a great time doing research with in summer 2011 at Carleton university. This dis- sertation would not have been possible without his guidance and support. I would like to thank Dr. Edward Butz for his support during past two years. I offer my best and special thanks to my parents, best friends of my life, who have supported me morally and financially throughout my years of education. Lastly, I thank my wonderful wife, who is the most valuable asset of my life. viDedication I lovingly dedicate this thesis to my father, who was the first teacher of my life, to my mother, whose love and kindness never ends, and also to my wonderful wife, whose love and encouragements are al- ways with me. viiChapter 1 Introduction 1.1 Motivation and Contribution Previously, the formulation for a random walk model in the first quadrant, (x ≥ 0, y ≥ 0), was studied by Fayolle, Malyshev and Iasnogorodski [19]. In chapter 3 of this thesis I will extend the formulation of a general random walk model to the half plane, in- cluding the first quadrant (x ≥ 0, y ≥ 0) and the fourth quadrant (x ≥ 0, y ≤ 0), and by using the kernel method and Tauberian-like Theorem I investigate the exact tail asymptotic behaviour of the joint stationary distribution of the generating functions, which can be used as a reference for the one who is interested in analysing any random walk model in the half plane. In addition, in chapter 4, I will apply the result of the formulation of a general random walk model in the half plane to a real queueing model, the Generalized-JSQ, which is a queueing system with two parallel servers that have three streams of arrivals, two of which are dedicated to each servers, and the third one joins the shorter queue upon arrival. We assume that arrivals are independent Poisson pro- cesses, and service times have identical exponential distributions. Although this queueing model already has been studied by Zhao and Grassmann [75], and M. Miyazawa, [56], in this thesis I will use a different method named the kernel method, which is a sim- pler and faster method for investigating the exact tail asymptotic behaviour, due to the fact that in the kernel method we are not 1dealing with the explicit expressions in terms of generating func- tions, and we only discuss the dominant singularity and its location compared with other singularities to figure out that how far we may expect to extend the radius of convergence in generating functions. 1.2 Literature Review Parallel queueing networks have advantages over single server queue- ing networks, because when some servers simultaneously serve the customers in the line, the efficiency increases. Therefore, using parallel queueing servers such as computer networks and multiple parallel processors has become common. As a consequence many scientists and engineers have been studying parallel queueing net- works in order to give the exact practical models for these queueing problems. We will see some of the works done in this area in the following paragraph. In the early 1960s and 1970s, the diffusion approximation method for queueing systems has been discussed by Cox and Miller [13], and later on by Gaver [30]. In 1990-1991 Adan et al. [3] intro- duced the compensation method which was useful for some spe- cific two-dimensional queueing models. In 1987 and 1990 Blanc [7], and in 1988 Hooghiemstra, Keane, and Van de Ree [35] pro- posed a new technique which was based on the power-series expan- sion of the state probabilities. In 1995 B. Blaszczyszyn, A. Frey, and V. Schmidt [5] applied the factorial moment expansion in or- der to get the approximate formula for stationary characteristics of the multi-server queue with Markov-modulated arrival process and FIFO (first in first served) discipline. In 2005 the large devi- ation method was applied to modified Jackson Network by Foley and David R. McDonald [15], which is a good tool for analysing the multi-server queueing models. Later in 2008 the large deviation method was used on infinite dimensional stochastic dynamical sys- tems by Amarjit Budhiraja, Paul Dupuis and Vasileios Maroulas [6]. In the first years of 1970s, V. A. Malyshev [60] [61] [62], and also in 21977 L. Flatto and H. P. McKean proposed the generating function method in order to get the asymptotic behaviour of the stationary probabilities of a random walk in the quarter plane containing the points with integer coordinates, Z2+ = {(i, j) : i, j = 0, 1, 2, ...}. In 1994 J. W. Cohen [11] used the generating function method in two- dimensional random walk. In 1999 G. Fayolle, R. Iasnogorodski, and V. Malyshev [19] published a book called “Random Walks in the Quarter-plane”, in which they have applied many different mathe- matical tools in order to get the explicit expressions for generating functions of the two-dimensional random walk in the quarter-plane. Halfin [34], Mitzenmacher [63], and Winston [73] have been gain- ing valuable results for the parallel queues. Although over the past years many researchers have published papers in the area of par- allel queues, still JSQ model has lots of problems that need to be worked on. Some work has been done on the stability problems of the JSQ model including Foley and McDonald [16], Foss and Cher- nova [27] [28], Kurkova [44], Sharifnia [66], Suhov and Vvedenskaya [67], Tandra, Hemachandra and Manjunath [69], Vvedenskaya and Suhov [71], Vvedenskaya, Dobrushin and Karpelevich [72]. 1.3 Organization In chapter 2 of this thesis, I will give some basic definitions and concepts relating to queueing systems; In addition, I will go through the two-dimensional random walks, generating functions, stability conditions for a random walk model, and the analysis of kernel in a fundamental form. Moreover, some real world queueing examples are given for each area. In chapter 3, I will get the formula for analysis of the exact tail asymptotic behaviour of the stationary probabilities in a general two-dimensional random walk model in the first and fourth quadrants using the kernel method. In chapter 4, I use the results of chapter 3 to apply the kernel method to the Generalized-JSQ (Join the Shortest Queue) model in order to obtain the exact tail asymptotic behaviour of the Generalized-JSQ’s joint 3stationary probability distributions, and finally in the last chapter, I will summarize my main findings and achievements and give some suggestions in the area of random walk to the motivated readers for further studies in this area. 4Chapter 2 Background 2.1 Queueing Theory In this section, I will review some definitions and basic concepts from Queueing Theory. A queueing system includes customers ar- riving at random times to a system and depart after receiving ser- vice. Queueing systems are classified according to : (1) the input process, the probability distribution of arrival of cus- tomers in time; (2) the service time distribution, the probability distribution of the time to serve the customers; (3) the queueing discipline, the order in which customers are served; (4) the number of servers. A very basic queueing formula is L = λW , where L = the average number of customers in the system, λ = the arrival rate of customers to the system, W = the average waiting time for each customer in the system. 2.1.1 Counting Process A stochastic process {N(t), t ≥ 0} is called a counting process when N(t) represents the total number of events that have occurred by time t. N(t) must satisfy: (i) N(t) ≥ 0 (ii) N(t) is integer valued. 5(iii) if s < t, then N(s) ≤ N(t) (monotonicity). (iv) For s < t, N(t) − N(s) represents the number of events that have occurred in the interval (s, t). 2.1.2 Poisson Process One of the simplest counting processes is the Poisson process. Definition 2.1. The counting process {N(t), t ≥ 0} is called a Pois- son process having rate λ, λ > 0, if (i) N(0) = 0. (ii) The process has independent increments. (iii) The number of events in any interval t is Poisson distributed with mean λt, for all s, t ≥ 0. P{N(t+ s)−N(s) = n} = e−λt (λt) n n! , n = 0, 1, ... Definition 2.2. A counting process is called a process with station- ary increments if the distribution of the number of events occurring in any time interval only depends on the length of the interval. That is, the process has stationary increments if the number of events in the time interval (t1 + a, t2 + a) has the same distribution as the number of events in the time interval (t1, t2). 2.1.3 Markov Chain In this section we consider a discrete stochastic process {Xn, n = 0, 1, 2, ...} that takes on a countable number of possible values in the state space A. If Xn = i, then the process is in state i at time n. The notation pij means the probability of moving from state i to j. If we have the following condition, P{Xn+1 = j|Xn = i, Xn−1 = in−1, ..., X1 = i1, X0 = i0} = P{Xn+1 = j| Xn = i} = pi,j, (2.1) for all states i0, i1, ..., in−1, i, j and all n ≥ 0, then stochastic process is called discrete-time Markov chain. Equation (2.1) indicates that 6the next state in Markov chain only depends on its current state, and does not depend on any previous states. A discrete-time homogeneous Markov chain is characterized by the stochastic matrix P = ||pi,j||, i, j ∈ A, such that pi,j ≥ 0, ∑ j pi,j = 1, ∀i ∈ A. The matrix elements of P n are denoted by p(n)i,j . Definition 2.3. A Markov chain is called irreducible if, for every i, j, there exists m, depending on (i, j) such that p(m)i,j 6= 0. A Markov chain is called aperiodic if, for some i, j ∈ A, the set {n : p(n)i,j 6= 0} has greatest common divisor equal to 1. Definition 2.4. An irreducible aperiodic Markov chain is called ergodic if, and only if, the equation piP = pi, where pi is the vector pi = {piα, α ∈ A}, has a unique l1-solution up to a multiplicative factor, which can be chosen ∑ α piα = 1, piα > 0. The piα’s are called stationary probabilities. A continuous-time Markov process is the continuous-time version of a Markov chain. Hence, it is a stochastic process {X(t) : t ≥ 0}, which satisfies the Markovian property or memoryless property, and can only take on values from a state space set A. For tm > tn > 0, the Markov property says that the conditional probability of an event at time tm, given the probabilities of that event for all times up to and including time tn, is only depending on time tn. The continuous-time Markov chain has many application in queueing systems. 72.1.4 Champan-Kolmogorov Equations We have already defined the one-step transition probabilities, pi,j, now we want to define the n-step transition probabilities denoted by p(n)i,j , which indicates the probability that a process in state i will be in state j after n transitions. That is, p(n)i,j = p{Xn+m = j|Xm = i}, n ≥ 0, i, j ≥ 0. (2.2) Obviously p(1)i,j = pi,j. The Chapman-Kolmogorov equations provide a method to compute the n-step transition probabilities. These equations are, p(n+m)i,j = ∞∑ k=0 p(n)i,k p (m) k,j (2.3) for all n,m ≥ 0, and all i, j. More information about Chapman- Kolmogorov equation can be found in [65]. 2.1.5 Queueing Models In this section we provide basic information on some well-known queueing models. 1. M/M/s model: The arrivals form a Poisson process, and the service times are exponentially distributed. In this model, there are s servers. The queueing parameters, W , the mean waiting time, and L, the mean queue length, are as follows, 8W = (n−1∑ j=0 1 j!( λ µ )j + (λ µ n ) s!(1− λ sµ ) )−1( λ sµ )λs λ s! µs(1− λ µ )2 + 1 µ , (2.4) L = (n−1∑ j=0 1 j!( λ µ )j + (λ µ n ) s!(1− λ sµ ) )−1( λ sµ )λs s! µs(1− λ µ )2 + λ µ . (2.5) 2. M/G/1: Like in the previous model, arrivals follow a Poisson process with rate λ, while service time has an arbitrary distribution, G(y) = Pr{Yk ≤ y} with finite mean service time ν = E[Yk]. Also, the service rate is µ = 1 ν . In this model there is one server. 3. M/G/∞: It is like the M/G/1 model except that in this model there is infinite number of servers instead of one server. 2.2 Transition Probabilities In this section we introduce the transition probabilities for the first and fourth quadrants of a two-dimensional random walk plane. A two-dimensional transition probability is the probability of mov- ing from state, (m, n), to another state, (m + i, n + j), which is independent of m and n. The maximum step in any dimension is ±1. Transition probabilities depend only on step sizes, except for 9boundaries. Therefore, we define pi,j as follows, ¯P(m,n),(m+i,n+j) = pi,j if m ≥ 1 and n ≥ 1, −1 ≤ i, j ≤ 1, p(0)i,j if (m, n) = (0, 0), −1 ≤ i, j ≤ 1, p(1)i,j if m ≥ 1 and n = 0, −1 ≤ i, j ≤ 1, p(2)i,j if m = 0 and n ≥ 1, −1 ≤ i, j ≤ 1, p(−)i,j if m ≥ 1 and n ≤ −1, −1 ≤ i, j ≤ 1, p(−2)i,j if m = 0 and n ≤ −1, −1 ≤ i, j ≤ 1, where pi,j, p(0)i,j , p (1) i,j , p (2) i,j , p (−2) i,j , and p (−) i,j are non negative real num- bers in [0, 1]. Since in this thesis we are dealing with discrete-time Markov chains which are homogeneous random walks, we have ∑ i,j=0,1 p(0)i,j = 1, ∑ i=0,±1,j=0,1 p(1)i,j = 1, ∑ i,j=0,1 p(−)i,j = 1, ∑ i=0,1,j=0,±1 p(2)i,j = 1, ∑ i=0,±1,j=0,±1 pi,j = 1. ∑ i,j=0,1 p(−2)i,j = 1. 2.3 Random Walk in the Quarter Plane Discrete-timeMarkov chains which are homogeneous two-dimensional random walks, have three main properties as follows, 1. The state space is two-dimensional, and consists of points with non-negative integer coordinates. So the state space is A = Z2+ = {(i, j) : i, j ≥ 0 are integers} 2. Because of the boundaries, we partition Z2+ as follows Z2+ = S ∪ S(1) ∪ S(2) ∪ {(0, 0)}, where S = {(i, j) : i, j > 0}, S(1) = {(i, 0) : i > 0}, S(2) = {(0, j) : j > 0}. 3. We assume that jumps are bounded. Therefore, 10p(i,j)(i+α,j+β) = 0, unless −1 ≤ α, β ≤ 1, Next we introduce an important theorem which indicates the sta- bility conditions for a random walk model in first quadrant (x ≥ 0, y ≥ 0). Theorem 2.1. Let M , M (1) and M (2) be as follows M = (Mx,My) = (∑ ipij,∑ jpij) M (1) = (M (1)x ,M (1)y ) = (∑ ip(1)ij , ∑ jp(1)ij ) M (2) = (M (2)x ,M (2)y ) = (∑ ip(2)ij , ∑ jp(2)ij ) then when M 6= 0, a random walk is ergodic if, and only if, one of the following conditions holds, (i) Mx < 0, My < 0 MxM (1)y −MyM (1)x < 0, MyM (2)x −MxM (2)y < 0; (ii) Mx < 0, My ≥ 0, MyM (2)x −MxM (2)y < 0; (iii) Mx ≥ 0, My < 0, MxM (1)y −MyM (1)x < 0; Proof. The probabilistic proof of this theorem is given in [19]. 2.4 Generating Functions In this section we introduce the generating functions and the fun- damental form for a random walk in the quarter plane which play an important role in the kernel analysis. As stated in section 2.3, because of the boundaries, the state space of two-dimensional random walk can be written as the union of disjoint classes as follows, Z2+ = S ∪ S(1) ∪ S(2) ∪ {(0, 0)}, 11As discussed earlier, two states of the same class have the same transition probabilities. Let Xn denote the state of the random walk at time n. Now we define two complex variables, u1, and u2, one for each direction. The variable u is the vector of complex variables in C2 as u = (u1, u2), |ui| = 1, ui ∈ C, i = 1, 2, and the jump generating functions are as follows P1(u) = E[uXn+1−Xn|Xn = z ∈ S], P2(u) = E[uXn+1−Xn|Xn = z ∈ S(1)], P3(u) = E[uXn+1−Xn|Xn = z ∈ S(2)], P4(u) = E[uXn+1−Xn|Xn = z ∈ {(0, 0)}]. (2.6) Here uz = 2∏ n=1 uznn , where un, zn, n = 1, 2, are coordinates of the vector u and z respec- tively. Therefore we have E[uXn+1] =E[uXnuXn+1−Xn] =E[uXn1{Xn∈S}]P1(u) + E[uXn1{Xn∈S(1)}]P2(u)+ E[uXn1{Xn∈S(2)}]P3(u) + E[uXn1{Xn∈{(0,0)}}]P4(u). (2.7) Now we introduce the generating function pi1(u) = ∑ z∈S pizu z , pi2(u) = ∑ z∈S(1) pizu z , pi3(u) = ∑ z∈S(2) pizu z , pi4(u) = pi0,0, (2.8) 12where piz indicates the stationary probability of being in state z. Using (2.8) and taking the limit as n→∞ in (2.7), we get 4∑ r=1 [1− Pr(u)]pir(u) = 0. (2.9) We can rewrite (2.9) as −h(x, y)pi(x, y) = h1(x, y)pi(x) + h2(x, y)pi˜(y) + pi0,0h0(x, y), (2.10) which is called fundamental form, where pi(x, y) = ∞∑ i,j=1 pii,jxi−1yj−1, pi(x) = ∑ i≥1 pii,0x i−1 , pi˜(y) = ∑ j≥1 pi0,jyj−1, (2.11) and h(x, y) = xy( 1∑ i=−1 1∑ j=−1 pi,jxiyj − 1) = a(x)y2 + b(x)y + c(x) = a˜(y)x2 +˜b(y)x+ c˜(y), (2.12) h1(x, y) = x( 1∑ i=−1 1∑ j=0 p(1)i,j xiyj − 1) = (p(1) −1,0 + p (1) 0,0x+ p (1) 1,0x 2) + (p(1) −1,1 + p (1) 0,1x+ p (1) 1,1x 2)y − x, (2.13) h2(x, y) = y( 1∑ i=0 1∑ j=−1 p(2)i,j xiyj − 1) = (p(2)0,−1 + p(2)0,0y + p(2)0,1y2) + (p(2)1,−1 + p(2)1,0y + p(2)1,1y2)x− y, (2.14) 13h0(x, y) = x( 1∑ i=0 1∑ j=0 p(0)i,j xiyj − 1) = (p(0)0,0 + p(0)1,0x+ p(0)0,1y + p(0)1,1xy)− 1, (2.15) with a(x) = −(p −1,1 + p0,1x+ p1,1x2), (2.16) b(x) = −(p −1,0 + (p0,0 − 1)x+ p1,0x2), (2.17) c(x) = −(p −1,−1 + p0,−1x+ p1,−1x2), (2.18) a˜(y) = −(p1,−1 + p1,0y + p1,1y2), (2.19) ˜b(y) = −(p0,−1 + (p0,0 − 1)y + p0,1y2), (2.20) 2.4.1 Queueing Examples Here we give some examples of random walks in queueing systems and their corresponding generating functions. 1. The Symmetric Join the Shortest Queue Model In this queueing model, customers arrive to system with the rate of λ. Upon arrival, customers determine which server has the shorter queue, and then join the shorter one. Also service rates of customers from both servers have the same value of µ. If the length of the both server’s queues are the same, an arriving customer will join either queue with the probability of 1/2. In this queueing model, the random walk probabilities are as follows, p −1,1 = µ, p0,−1 = µ, p1,−1 = λ, p(1) −1,1 = 2µ, p (1) 0,1 = λ, p(2)0,−1 = µ, p (2) 1,−1 = λ, p (2) 0,0 = µ, p(0)0,1 = λ, p (0) 0,0 = 2µ. 14For this model the generating functions are h(x, y) = xy − µy2 − µx− λx2, h1(x, y) = 2µy + λxy − x, h2(x, y) = µy + µ+ λx− y, h0(x, y) = 2µ+ λy − 1. 2. Symmetric Join the Shorter Queue with Coupled processor This model is similar to the Symmetric JSQ with the difference that whenever the length ofQi is zero, the service rate for the other queue will be changed from µj to µj + µ∗i . In this queueing model when x-axis represents min {Q1, Q2}, and y-axis represents the |Q2−Q1|, the transition probabilities of random walk are as follows, p1,−1 = λ, p0,−1 = µ, p−1,1 = µ, p(1)0,1 = λ, p (1) −1,1 = 2µ, p(2)1,−1 = λ, p (2) 0,−1 = µ+ µ ∗ , p(2)0,0 = 1− (λ+ µ+ µ∗), p(0)0,1 = λ, p (0) 0,0 = 2µ, And with respect to the transition probabilities, the generating functions are as follows, h(x, y) = xy − µy2 − µx− λx2, h1(x, y) = 2µy + λxy − x, h2(x, y) = µy + µ+ λx− y, h0(x, y) = 2µ+ λy − 1. 3. The Pre-Emptive Priority Queueing System In this example we consider theM/M/1 pre-emptive queueing model. In this queue we have two classes of customers with different priority of being served. Higher and lower priority customers arrivals occur according to a Poisson process with rates of λ1 and λ2 respectively. The service rule is FIFO (first in first served), and it is preemptive. 15That is, if a lower priority customer is being served, his service is interrupted upon arrival of a higher priority customer to system, and the lower priority customer is waiting at the head of the queue until the service of the higher priority customer is completed and his service continues again. There is one server with exponential service time in this model, which may have different service rates, µ1, and µ2 when serving respectively the higher priority customer or lower one. Without loss of generality we assume that λ1+λ2+µ1+µ2 = 1. The transition probabilities of the random walk of the quarter plane in which the x-axis corresponds to the length of the queue of higher priority customers, and y-axis corresponds to the queue length of lower priority customers are given by, p1,0 = λ1, p0,1 = λ2, p−1,0 = µ1, p0,0 = µ2 p(1)1,0 = λ1, p (1) 0,1 = λ2, p (1) −1,0 = µ1, p (1) 0,0 = µ2, p(2)1,0 = λ1, p (2) 0,1 = λ2, p (2) 0,0 = µ1, p (2) 0,−1 = µ2, p(0)1,0 = λ1, p (0) 0,0 = µ1 + µ2, p (0) 0,1 = λ2. According to the transition probabilities above, we have the fol- lowing generating functions for the pre-emptive priority queueing system, h(x, y) = xy − [λ1x2 + (µ2 + λ2y)x+ µ1]y, h1(x, y) = [λ1x2 + (µ2 + λ2y)x+ µ1]− x, h2(x, y) = [λ1xy + λ2y2 + µ1y + λ2]− y, h0(x, y) = [λ1x+ λ2y + µ1 + µ2]− 1. 4. The Restricted Jackson Network In this queueing model, we have two queues, qi, i = 1, 2. Each of them has an external arrival stream which is a Poisson process with rate of λi. The service times in both queues are exponential, and departures from the servers while busy occur at rate of µi, i = 1, 2. Each customer who completes his service in the qi has two options, either he gets out of the system with probability of ri,0, or 16he joins the other queue with probability of rij. Also without loss of generality we assume that λ1 + λ2 + µ1 + µ2 = 1. For this queueing model, the transition probabilities are given by, p1,0 = λ1, p0,1 = λ2, p−1,1 = r12µ1, p−1,0 = r10µ1, p0,−1 = r20µ2, p1,−1 = r21µ2, p(1)1,0 = λ1, p (1) 0,1 = λ2, p (1) −1,1 = r12µ1, p (1) −1,0 = r10µ1, p (1) 0,0 = µ2, p(2)1,0 = λ1, p (2) 0,1 = λ2, p (2) 0,0 = µ1, p (2) 0,−1 = r20µ2, p (2) 1,−1 = r21µ2, p(0)1,0 = λ1, p (0) 0,1 = λ2, p (0) 0,0 = µ1 + µ2. According to transition probabilities the generating functions are, h(x, y) =xy − (λ1x2y + r21µ2x2 + λ2xy2 + r20µ2x+ r12µ1y2+ r10µ1y), h1(x, y) =(r12µ1 + λ2x)y + (r10µ1 + µ2x+ λ1x2)− x, h2(x, y) =(r21µ2 + λ1y)x+ (r20µ2 + µ1y + λ2y2)− y, h0(x, y) =λ1x+ λ2y + µ1 + µ2 − 1. 5. The Classical Tandem Queueing Model In this model, there are two servers in tandem. Customers are arriving to the first server with rate of λ1, and being served with rate of µ1. After completion of their service in the first server, they go to the second server to receive service with rate of µ2, and after completion of the their second service with server two, they leave the system. Without loss of generality we assume that λ+µ1 +µ2 = 1. The transition probabilities for the classical Tandem queue are given by, p1,0 = λ, p−1,1 = µ1, p0,−1 = µ2, p(1)1,0 = λ, p (1) −1,1 = µ1, p (1) 0,0 = µ2, p(2)1,0 = λ, p (2) 0,0 = µ1, p (2) 0,−1 = µ2, p(0)1,0 = λ, p (0) 0,0 = µ1 + µ2. 17Using the above transition probabilities, one can find the generating function as follows, h(x, y) = xy − (µ1y2 + λx2y + µ2x), h1(x, y) = (λx2 + µ2x+ µ1y)− x, h2(x, y) = (λxy + µ2 + µ1y)− y, h0(x, y) = λx+ µ1 + µ2 − 1. 6. Two Demands Queueing System In this queueing model, there is one stream of customers with arrival rate λ. The server of qi, i = 1, 2 has service rate of µi, with an exponential service time independent of arrival rate λ. The stability conditions in this model are λ < µ1, and λ < µ2. Without loss of generality we assume that λ + µ1 + µ2 = 1. The transition probabilities for this queue are p1,1 = λ, p−1,0 = µ1, p0,−1 = µ2, p(1)1,1 = λ, p (1) −1,0 = µ1, p (1) 0,0 = µ2, p(2)1,1 = λ, p (2) 0,0 = µ1, p (2) 0,−1 = µ2), p(0)1,1 = λ, p (0) 0,0 = µ1 + µ2. Knowing the transition probabilities for this queue, one can get the following generating functions, h(x, y) = xy − (µ1y + λx2y2 + µ2x), h1(x, y) = λx2y + µ2x+ µ1 − x, h1(x, y) = λy2x+ µ2 + µ1y − y, h0(x, y) = λxy + µ1 + µ2 − 1. 2.5 Stability Condition In this section we will derive the stability conditions of some well- known queueing examples by using the theorem (2.1) by Fayolle, Iasnogorodski, and Malyshev. 181. The Symmetric Join the Shortest Queue Model Considering the transition probabilities for the Symmetric JSQ model, we have Mx = λ− µ, My = −µ, M (1)x = −2µ, M (1)y = λ, M (2)x = λ, M (2)y = −λ. So by using the theorem (2.1), we have the following situations, (i) (1) λ < µ, − µ < 0, (2) λ(λ− µ)− 2µ2 < 0, ⇒ (λ+ µ)(λ− 2µ) < 0 ⇒ λ < 2µ, (3) (λ− µ)µ− λµ < 0, ⇒ −µ2 < 0, (ii) λ < µ1, −µ ≥ 0, (not possible) (iii) µ ≤ λ, −µ1 < 0, ⇒ (µ+ λ)(λ− 2µ) < 0 ⇒ λ < 2µ. Therefore, this queue is ergodic and stable when λ < µ. 2. Symmetric Join the Shorter Queue with Coupled processor From theorem (2.1) we have Mx = λ− µ, My = −µ, M (1)x = −2µ, M (1)y = λ, M (2)x = λ, M (2)y = −µ− µ∗. Hence, the stability conditions are as follows, 19(i) (1) λ < µ, − µ < 0, (2) λ(λ− µ)− 2µ2 < 0, ⇒ (λ+ µ)(λ− 2µ) < 0 ⇒ λ < 2µ, (3) (λ− µ)(µ+ µ∗)− λµ < 0, ⇒ (λ− µ)µ∗ − µ2 < 0, (ii) λ < µ1, −µ ≥ 0, (not possible) (iii) µ ≤ λ, −µ1 < 0, ⇒ (µ+ λ)(λ− 2µ) < 0 ⇒ λ < 2µ. Therefore, considering the conditions above, this queue is ergodic if λ < 2µ. 3. The Pre-Emptive Priority Queueing System For this queueing model we have Mx = λ1 − µ1, My = λ2, M (1)x = λ1 − µ1, M (1)y = λ2, M (2)x = λ1, M (2)y = λ2 − µ2. Hence, the stability conditions are as follows, (i) (1) λ < µ1, λ2 < 0, (not possible) (2) (λ1 − µ1)λ2 − λ2(λ1 − µ1) < 0, (3) λ2λ1 − (λ1 − µ1)(λ2 − µ2) < 0, (ii) λ < µ1, λ2 ≥ 0, λ2λ1 − (λ1 − µ1)(λ2 − µ2) < 0, ⇒ λ1µ2 + λ2µ1 − µ1µ2 < 0 ⇒ λ1 µ1 + λ2 µ2 < 1, (iii) λ ≥ µ1, λ2 < 0. (not possible) Therefore, this queue is ergodic if, and only if ρ = ρ1 + ρ2 < 1, where, 20ρ1 = λ1 µ1 , and ρ2 = λ2 µ2 . 4. The Restricted Jackson Network In this queue matrix M is Mx = λ1 + r21µ2 − r12µ1 − r10µ1, My = λ2 + r12µ1 − r21µ2 − r20µ2, M (1)x = λ1 − (r10µ1 + r12µ1), M (1)y = λ2 + r12µ1, M (2)x = λ1 + r21µ2, M (2)y = λ2 − r21µ2. With respect to the matrix M above, and also considering theo- rem (2.2) we have the stability condition for the restricted Jackson network as follows, ρ1 < 1, and ρ2 < 1. 5. The Classical Tandem Queueing Model For Tandem queue is matrix M is Mx = λ− µ1, My = µ1 − µ2 M (1)x = λ− µ1, M (1)y = µ1, M (2)x = λ, M (2)y = −µ2. Therefore, by applying theorem (2.1) this queue is ergodic if, and only if λ < µ1, and λ < µ2. 6. Two Demands Queueing System With respect to the transition probabilities for Two demands queue- ing system we have Mx = λ− µ1, My = λ− µ2 M (1)x = λ− µ1, M (1)y = λ, M (2)x = λ, M (2)y = λ− µ2. 21Hence, by applying theorem (2.1) this queue is ergodic if, and only if λ < min {µ1, µ2}. 2.6 Riemann Surfaces Here we provide a summary of algebraic functions and Riemann sur- faces which we need for our later discussions. An important class of complex variable functions are algebraic functions and their inte- grals. An analytic function y = y(x) is called an algebraic function if it satisfies the following equation, a0(x)yn + a1(x)yn−1 + ...+ an(x) = 0, a0(x) 6= 0, (2.21) where ai(x), i = 0, 1, 2, ..., n is a polynomial in x with complex coefficients. Furthermore, a rational function of x and y is of the form, R(x, y) = b0(x)y m + b1(x)ym−1 + ...+ bm(x) c0(x)yk + c1(x)yk−1 + ...+ ck(x) , (2.22) where bi, i = 1, 2, ..., m, and ci, i = 1, 2, ..., k, are polynomials in x with complex coefficients, and the denominator is not identically zero. The region on which an algebraic function is defined and single valued is a Riemann surface. The simplest algebraic functions are of the form a0(x)y + a1(x) = 0, (2.23) where a0(x) and a1(x) are polynomials in x with complex coeffi- cients. Hence, y = −a1(x) a0(x) is a rational function of x. In this thesis we are dealing with algebraic functions of the form h(x, y) = a0(x)y2 + a1(x)y + a2(x), (2.24) 22where ai(x), for i = 0, 1, 2 are polynomials in x, and a0(x) 6= 0. In this case we change the variable by ζ = 2a0(x)y + a1(x), (2.25) to get ζ2 − p(x) = 0, (2.26) where p(x) = a21(x)− 4a0(x)a2(x). A two-dimensional manifold M is a topological space, if every point of that is surrounded by a neighbourhood, which is homeomorphic to an open disk in the complex plane C. A pair {U, ϕ}, which is formed by neighbourhood U ⊆ M and its associated homeomor- phism ϕ is called a chart. The mapping, Φ : U → C, defines a system of local coordinated in U . A collection of charts {(Ui, ϕi), i ∈ I}, where for some index set I, {Ui, i ∈ I} is an open covering of M, is called Atlas A. A connected two-dimensional manifold M is Riemann surface S, if there exists an atlas AS with the following property: For any pair {U, ϕ}, {V, ϕ} of charts in AS, such that U ∩V 6= φ, the mapping ϕ o ψ−1 is holomorphic in ψ(U ∩ V ) ⊂ C. The classical notion of holomoorphic functions can be generalized to the case of Riemann surfaces. Let S be a Riemann surface, AS its atlas, and Y ⊂ S an open connected set of S. A function f : Y → C is holomorphic in Y , if, for any chart {U, ϕ} in AS, the mapping f o ϕ−1 : ϕ(U) → C is holomorphic in the normal sense in the open set ϕ(U) ⊂ C. Now let S and T be two Riemann surfaces. The mapping f : S → T is holomorphic if, for any pair of charts {U, ϕ}, {V, ϕ} belonging to AS and AT respectively, with f(U) ⊂ V , the mapping ψ o f ϕ−1 is holomorphic in Φ(U) ⊂ C. The uniqueness theorem remains valid: if f1 and f2 are two holomorphic functions from S to T , which are equal on an infinite compact set of S, then they must be equal everywhere. 232.6.1 Genus 1 or Genus 0 The Riemann surfaces which are generated by fundamental form and generating functions are divided into 2 cases, genus 1 or genus 0. In fact, Riemann surface has genus 0 if, and only if the discriminant, D(x) = b2(x) − 4a(x)c(x) = d4x4 + d3x3 + d2x2 + d1x + d0, of the generating function equation, Q(x) = a(x)y2 + b(x)y + c(x) = 0, has multiple zeros. That is, whenever the number of zeros of the discriminant is 1 or 2 the Riemann surface is of genus 0 which creates sphere, and when the number of discriminant’s zeros is 3 or 4 the Riemann surface is of genus 1 which creates torus. For further studies one can refer to [19]. The following lemma gives the explicit classification of genus 1 and 0. Lemma 2.1. (Fayolle, Iasnogorodski, Malyshev) For all non sin- gular random walks, a Riemann surface has genus 0 if, and only if one the following holds, Mx = My = 0, p1,0 = p1,1 = p0,1 = 0, p1,0 = p1,−1 = p0,−1 = 0, p −1,0 = p−1,−1 = p0,−1 = 0, p0,1 = p−1,0 = p−1,1 = 0. 2.7 Analysis of the Kernel The equation, h(x, y) = 0, is called kernel equation. It is usually a quadratic equation in terms of x and y. If we want to solve the kernel equation for y, we see that for each value of x, there are two values for y. The solutions of this equation gives us a Riemann surface. Whenever the delta of D(x) or D(y) has three or four distinct zeros, then the Riemann surface will be of genus 1, which yields a torus. However, if D(x) or D(y) has one, or two distinct roots, then the Riemann surface will be of genus 0, which yields a 24sphere. We denote the roots of D(x) by x1, x2, x3, and x4. There is an important lemma by Fayolle, Iasnogorodski, and Malyshev [19], which indicates the relationship between xi, i = 1, 2, 3, 4, under different conditions. Here we state the lemma. Lemma 2.2. (Fayolle, Iasnogorodski, and Malyshev) A non-singular random walk with My 6= 0, y(x) has two real branch points x1 and x2 inside the unit circle, and two real branch points, x3 and x4, out- side of the unit circle. The following classifications hold for the pair (x3, x4). 1. If p1,0 > 2√p1,1p1,−1, then 1 < x3 < x4 <∞; 2. If p1,0 = 2√p1,1p1,−1, then 1 < x3 < x4 = ∞; 3. If p1,0 < 2√p1,1p1,−1, then 1 < x3 ≤ −x4 < ∞; Also for the pair (x1, x2) we have 4. If p −1,0 > 2 √p −1,1p−1,−1, then 0 < x1 < x2 < 1; 5. If p −1,0 = 2 √p −1,1p−1,−1, then x1 = 0 and 0 < x2 < 1; 6. If p −1,0 < 2 √p −1,1p−1,−1, then 0 < −x1 ≤ x2 < 1. Proof of this lemma can be found in [19]. Lemma 2.3. (Fayolle, Iasnogorodski, and Malyshev) For non- singular random walks with My = 0, one of the branch points of y(x) is 1. Furthermore, if Mx < 0, two branch points have a modulus greater than 1, and the remaining ones have a modulus less than 1, and if Mx > 0, two branch points have a modulus less than 1, and the other ones have a modulus greater than 1. 2.7.1 Queueing Examples In this section we provide some queueing examples to see how the above lemma works for some queueing models. Since in all queueing examples we will study My 6= 0, then we have 0 ≤ x1 < x2 < 1 < x3 < x4, or 0 ≤ x1 < x2 < 1 < x3 < x4 = ∞. 251. The symmetric JSQ Model and the JSQ Model with Coupled Pro- cessors Referring to the transition diagrams for the Symmetric JSQ model, and JSQ model with coupled processors, we have p1,0 = p1,1 = p−1,0 = p−1,−1 = 0, p1,−1 = λ, p−1,1 = µ. Therefore, according to lemma (2.2) and (2.3), we obtain 0 = x1 < x2 < 1 < x3 < x4 = ∞. 2. The Pre-Emptive Priority Queueing System The Pre-emptive priority queueing model is singular, and so its corresponding Riemann surface is of genus 0. Since we are dealing with the non-singular random walks, we can not discuss this here. 3. The Restricted Jackson Network From transition diagrams for these two queueing model we have p1,0 = λ1, p1,−1 = r21µ2, p−1,0 = r10µ1, p−1,1 = r12µ1, p1,1 = p −1,−1 = 0. Therefore, according to the lemmas (2.2) and (2.3), we have 0 < x1 < x2 < 1 < x3 < x4. 4. The Classical Tandem Queues According to the transition probabilities for Tandem queue, we obtain p1,1 = p1,−1 = p−1,0 = p−1,−1 = 0, p1,0 = λ, p−1,1 = µ1. Hence, referring to the two lemmas (2.2) and (2.3), we have 0 = x1 < x2 < 1 < x3 < x4. 265. The Queueing Systems with Two Demands From transition probabilities for Two demand queueing model, we obtain p1,0 = p1,−1 = p−1,0 = p−1,1 = p−1,−1 = 0, p1,1 = λ. Therefore, from the two lemmas (2.2) and (2.3) above, we have 0 < x1 < x2 < 1 < x3 < x4 = ∞. 27Chapter 3 Exact Tail Asymptotic Analysis of a General Random Walk Model Using Kernel Method 3.1 Kernel Method and Generating Functions The kernel method was first introduced by Knuth [38] and then was developed by Banderier et al [4]. Suppose we have a fundamental form A(x, y)F (x, y) = B(x, y)G(x) + C(x, y), where F (x, y), and G(x) are unknown, and A(x, y), B(x, y), and C(x, y) are known two-variable complex functions. The main idea of the kernel method is to find the solutions of the equation F (x, y) = 0. Suppose x and Y0(x) is the solutions of F (x, y) = 0, then obviously, G(x) = −C(x, Y0(x)) B(x, Y0(x)) . In kernel method, finding the location of poles of the unknown functions, as well as determination of the dominant singularities of the generating functions are sufficient for the exact tail asymptotics analysis. In this section we provide the generating functions for a general random walk model in the first and fourth quadrants of the two- dimensional random walk. The generating functions are listed as follows, 28(1) generating functions for the first quadrant: Pn(x) = ∑ m≥1 pim,nx m , Q0(y) = ∑ n≥1 pi0,nyn, Qm(y) = ∑ n≥1 pim,nyn, P (x, y) = ∑ m≥1,n≥1 pim,nx myn, (3.1) (2) generating functions for the fourth quadrant: P (−)n (x) = ∑ m≥1 pim,nx m , Q(−)0 (y) = ∑ n≤−1 pi0,ny−n, Q(−)m (y) = ∑ n≤−1 pim,ny−n, P (−)(x, y) = ∑ m≥1,n≤−1 pim,nx my−n, (3.2) (3) generating functions for the boundary x-axis: P0(x) = ∑ m≥1 pim,0x m . (3.3) Using the generating functions defined above, we can write the bal- ance equations for the first and fourth quadrants of the plane in order to find the fundamental forms of a random walk model. Bal- ance equation describes that the probability of leaving each station- ary state is equal to the probability of moving to that state. We categorize the balance equations as follows, (1) for the boundary on x-axis: 29if m ≥ 2 and n = 0, pim,0 = 1∑ i=−1 pim+i,−1 p (−1) −i,1 + 1∑ i=−1 pim+i,1 p−i,−1 + ∑ i=−1,1 pim+i,0 p (1) −i,0+ pim,0 p0,0, (3.4) if m = 1 and n = 0, pi1,o = 2∑ i=1 pii,−1 p (−) −i+1,1 + 2∑ i=1 pii,1 p−i+1,−1 + pi0,−1 p (2−) 1,1 + pi0,1 p (2) 1,−1+ pi0,0 p (0) 1,0 + pi2,0 p (1) −1,0, (3.5) if m = 0 and n = 0, pi0,0 = pi0,−1 p (−2) 0,1 + pi1,−1 p (−) −1,1 + pi1,0 p (1) −1,0 + pi1,1 p−1,−1 + pi0,1 p (2) 0,−1+ pi0,0 p (0) 0,0, (3.6) (2) for the boundary on y-axis: if m = 0 and n ≥ 2, pi0,n = 1∑ i=−1 pi0,n+i p (2) 0,−i + 1∑ i=−1 pi1,n+i p−1,−i, (3.7) if m = 0 and n = 1, pi0,1 = 2∑ i=1 pi1,i p−1,−i+1 + 2∑ i=1 pi0,i p (2) 0,−i+1 + pi0,0 p (0) 0,1 + pi1,0 p (1) −1,1, (3.8) if m = 0 and n = −1, pi0,−1 = −1∑ i=−2 pi1,i p (−) −1,−i−1 + −1∑ i=−2 pi0,i p (2−) 0,−i−1 + pi0,0 p (0) −1,0 + pi1,0 p (1) −1,−1, (3.9) 30if m = 0 and n ≤ −2, pi0,n = 1∑ i=−1 pi0,n+i p (2−) 0,−i + 1∑ i=−1 pi1,n+i p (−) −1,−i, (3.10) (3) for the interior of the first quadrant: if m ≥ 2 and n = 1, pim,1 = 1∑ i=−1 pim+i,0 p (1) −i,1 + 1∑ i=−1 pim+i,2 p−i,−1 + ∑ i=−1,1 pim+i,0 p−i,0+ pim,1 p0,0, (3.11) if m ≥ 2 and n ≥ 2, pim,n = 1∑ i=−1 pim+i,n−1 p−i,1 + 1∑ i=−1 pim+i,n+1 p−i,−1 + ∑ i=−1,1 pim+i,n p−i,0+ pim,n p0,0, (3.12) if m = 1 and n ≥ 2, pi1,n = 1∑ i=−1 pi0,n+i p (2) 1,−i + 1∑ i=−1 pi2,n+i p−1,−i + ∑ i=−1,1 pi1,n+i p0,−i, (3.13) if m = 1 and n = 1, pi1,1 = 2∑ i=1 pii,0 p (1) −i+1,1 + 2∑ i=1 pi0,i p (2) 1,−i+1 + 2∑ i=1 pi2,i p−1,−i+1+ pi0,0 p (0) 1,1 + pi1,2 p0,−1, (3.14) (4) for the interior of the fourth quadrant: if m ≥ 2 and n = −1, pim,−1 = 1∑ i=−1 pim+i,0 p (1) −i,−1 + 1∑ i=−1 pim+i,−2 p (−) −i,1 + ∑ i=−1,1 pim+i,−1 p (−) −i,0 + pim,−1 p0,0, (3.15) 31if m ≥ 2 and n ≤ −2, pim,n = 1∑ i=−1 pim+i,n−1 p (−) −i,1 + 1∑ i=−1 pim+i,n+1 p (−) −i,−1 + ∑ i=−1,1 pim+i,n p (−) −i,0 + pim,n p0,0, (3.16) if m = 1 and n ≤ −2, pi1,n = 1∑ i=−1 pi0,n+i p (2−) 1,−i + 1∑ i=−1 pi2,n+i p (−) −1,−i + ∑ i=−1,1 pi1,n+i p (−) 0,−i, (3.17) if m = 1 and n = −1, pi1,−1 = 2∑ i=1 pii,0 p (1) −i+1,−1 + −1∑ i=−2 pi0,i p (2−) 1,−i−1 + −1∑ i=−2 pi2,i p (−) −1,−i−1+ pi0,0 p (0) 1,−1 + pi1,−2 p (−) 0,1 + pi1,−1 p (−) 0,0 . (3.18) Now according to the above balance equations one can get the fol- lowing fundamental forms. For the first quadrant, fundamental form is P (x, y)h(x, y) = P0(x)h1(x, y) +Q0(y)h2(x, y) + pi0,0h0(x, y)+ P −1(x)A(x) + pi0,−1B(x), (3.19) 32where h(x, y) = 1− 1∑ i=−1 1∑ j=−1 pi,jxiyj , h1(x, y) = 1∑ i=−1 1∑ j=0 p(1)i,j xiyj − 1, h2(x, y) = 1∑ i=0 1∑ j=−1 p(2)i,j xiyj − 1, h0(x, y) = 1∑ i=0 1∑ j=0 p(0)i,j xiyj − 1, A(x) = 1∑ i=−1 p(−)i,1 xi, B(x) = p(−)0,1 + p(2−)1,1 x. (3.20) For the fourth quadrant, fundamental form is P (−)(x, y)h(−)(x, y) = P0(x)h(−)1 (x, y) +Q(−)0 (y)h(−)2 (x, y)+ pi0,0h(−)0 (x, y) + P−1(x)A(−)(x) + pi0,−1B(−)x, (3.21) where 33h(−)(x, y) = 1− 1∑ i=−1 1∑ j=−1 p(−)i,j xiy−j, h1(x, y) = 1∑ i=−1 p(1)i,−1xiy, h(−)2 (x, y) = 1∑ i=0 1∑ j=−1 p(2−)i,j xiy−j − 1, h(−)0 (x, y) = 1∑ i=0 p(0)i,−1xiy, A(−)(x) = −A(x) = − 1∑ i=−1 p(−)i,1 xi, B(−)(x) = −B(x) = −p(−)0,1 + p(2−)1,1 x. (3.22) Lemma 3.1. For |x| ≤ 1 and |y| ≤ 1, we have the following two expressions for generating functions as follows, P (x, y)h(x, y)+P (−)(x, y)h(−)(x, y) = P0(x)H1(x, y)+Q0(y)h2(x, y)+ Q(−)0 (y)h(−)2 (x, y) + pi0,0H0(x, y), where H1(x, y) = h1(x, y) + h(−)1 (x, y), and H0(x, y) = h0(x, y) + h(−)0 (x, y). Proof. This follows from equations (3.19) and (3.21). 3.2 Key Kernel For the first quadrant of the random walk plane, the kernel equa- tion, h(x, y) = 0, gives an algebraic curve which turns out to be a Riemann surface. The zeros of the kernel equation are called branches of the fundamental form. In this section we analyse the kernel equation. For the first quadrant, the kernel equation becomes 34a quadratic equation in terms of y, which is h(x, y) = a(x)y2 + b(x)y + c(x) = 0, (3.23) where a(x) = −p1,1x2 − p0,1x− p−1,1, b(x) = −p1,0x2 + x− p−1,0, c(x) = −p1,−1x2 − p0,−1x− p−1,−1. (3.24) Therefore, the branches of the fundamental form are, Y±(x) = −b(x)± √ D(x) 2a(x) , (3.25) where D(x) = b2(x)− 4a(x)c(x) (3.26) Among the zeros, Y±(x), the one with smaller modulus is denoted by Y0(x) and the one with greater modulus is denoted by Y1(x). Therefore, Y0(x) = { Y − (x) if |Y − (x)| ≤ |Y+(x)|, Y+(x) if |Y+(x)| ≤ |Y−(x)|. (3.27) The zeros of the equation D(x) = b2(x)− 4a(x)c(x) = 0 are called branch points. In our case there are at most four branch points denoted by x1, x2, x3, and x4. As mentioned earlier, when the number of branch points are one or two, the corresponding Riemann surface of kernel equation is sphere, and when the number of branch points are three ot four, the corresponding Riemann surface will be torus. We also can express h(x, y) in quadratic form of x as follows, h(x, y) = a˜(y)x2 +˜b(y)x+ c˜(y) = 0, (3.28) 35where a˜(y) = −p1,1y2 − p1,0y − p1,−1, ˜b(y) = −p0,1y2 + y − p0,−1, c˜(y) = −p −1,1y2 − p−1,0y − p−1,−1. (3.29) Hence, the solutions of kernel equation are X±(y) = − ˜b(y)± √ ˜D(y) 2a˜(y) , (3.30) where ˜D(y) = ( ˜b(y) )2 − 4a˜(y)c˜(y). (3.31) There are at most four branch points for D(y) denoted by y1, y2, y3, and y4. Similar to (3.27), Among the roots X±(y), the one with smaller modulus is denoted by X0(y) and the one with greater modulus is denoted by X1(y). Therefore, X0(y) = { X − (y) if |X − (y)| ≤ |X+(y)|, X+(y) if |X+(y)| ≤ |X−(y)|. (3.32) If we write the kernel equation for the fourth quadrant, we get h(−)(x, y) = a(−)(x)y2 + b(−)(x)y + c(−)(x) = 0, (3.33) where a(−)(x) = −p(−)1,1 x2 − p(−)0,1 x− p(−)−1,1, b(−)(x) = −p(−)1,0 x2 + x− p(−)−1,0, c(−)(x) = −p(−)1,−1x2 − p(−)0,−1x− p(−)−1,−1. (3.34) The solutions for kernel equation are now, Y (−)± (x) = −b (−)(x)±√D(−)(x) 2a(−)(x) , (3.35) 36where D(−)(x) = (b(−))2(x)− 4a(−)(x)c(−)(x). (3.36) We can also write the kernel equation of the fourth quadrant as follows, h(x, y) = a˜(−)(y)x2 + ˜b(−)(y)x+ c˜(−)(y) = 0, (3.37) where a˜(−)(y) = −p(−)1,1 y2 − p(−)1,0 y − p(−)1,−1, ˜b(−)(y) = −p(−)0,1 y2 + y − p(−)0,−1, c˜(−)(y) = −p(−) −1,1y 2 − p(−) −1,0y − p (−) −1,−1. Hence, the solutions of kernel equation are X(−)± (y) = − ˜b(−)(y)± √ ˜D(−)(y) 2a˜(−)(y) , (3.38) where ˜D(−)(y) = (˜b(−))2(y)− 4a˜(−)(y)c˜(−)(y). In this thesis, we define [x3, x4] = [−∞, x4]∪ [x3,∞] when x4 < −1, similarly we define [y3, y4] = [−∞, y4] ∪ [y3,∞] when y4 < −1. Since all the generating functions are defined in the complex plane, to ensure the continuity or to avoid the transition from one branch to another, we consider the following cut planes ˜Cx = Cx − [x3, x4], ˜ ˜Cx = Cx − [x1, x2] ∪ [x3, x4], ˜Cy = Cy − [y3, y4], ˜ ˜Cy = Cy − [y1, y2] ∪ [y3, y4]. (3.39) Lemma 3.2. The function Y0(x) and Y1(x) are meromorphic in cut plane ˜Cx, Moreover, 37(i) Y0(x) has one zero and no poles. Hence, Y0(x) is analytic in ˜Cx. (ii) Y1(x) has two poles and no zeros. (iii) |Y0(x)| < |Y1(x)| on the whole cut plane ˜˜Cx, and |Y0(x)| = |Y1(x)| only on cuts. (iv) If |x| = 1, then |Y0(x)| ≤ 1. Moreover, Y0(1) = 1. Proof. Since we are in the cut plane ˜˜Cx, which excludes the case of b(x) = 0, we have Y0(x) = 2c(x) −b(x) +√D1(x), if −b(x) > 0, 2c(x) −b(x)−√D1(x), if −b(x) < 0, Y0(x)Y1(x) = c(x) a(x), hence, it is clear that (i) Y0(x) has one zero and no poles, and (ii) Y1(x) has two poles and no zeros. (iii) is true according to the definition of Y0(x) and Y1(x). (iv) It is proved in lemma 2.3.4. of Fayolle, Iasnogorodski, and Malyshev [19]. 3.3 Asymptotic Analysis of P0(x), Q0(y) and Q(−)0 (y) In this section we find the singularities of the generating functions, P0(x), Q0(y) and Q(−)0 (y) in order to find the asymptotic behaviour of them. Let f(x) = −Q0(Y0(x))h2(x, Y0(x)), f (−)(x) = −Q(−)0 (Y (−)0 (x))h(−)2 (x, Y (−)0 (x)), g0(x) = −pi0,0Q0(x), g1(x) = h1(x, Y0(x)) + h(−)1 (x, Y (−)(x)). (3.40) 38From lemma 3.1. and equations (3.40) we have, P0(x) = f(x) + f (−)(x) + g0(x) g1(x) , (3.41) Let x∗ be the zero of g1(x). Hence, g1(x∗) = h1(x∗, Y0(x∗)) + h(−)1 (x∗, Y (−)(x∗)) = 0. Now for analysing the singularity for Q0(y) we need the following notations. Let l1(y) =− P0(X0(y))h1(X0(y), y), l2(y) =− pi0,0 h0(X0(y), y)− P−1(X0(y)) A(X0(y))− pi0,−1 B(X0(y)), g2(y) =h2(X0(y), y). (3.42) Hence, from equations (3.19) and (3.42) we have, Q0(y) = l1(y) + l2(y)g2(y) (3.43) Now let y∗ be the zero of g2(y). Hence, g2(y∗) = h2 ( X0(y∗), y∗ ) = 0. Also for asymptotic analysing of the Q(−)0 we need the following notations. Let l(−)1 (y) =− P0(X(−)0 (y))h(−)1 (X(−)0 (y), y), l(−)2 (y) =− pi0,0 h(−)0 (X(−)0 (y), y)− P−1(X(−)0 (y)) A(−)(X(−)0 (y))− pi0,−1 B(−)(X0(y)), g(−)2 (y) =h(−)2 (X(−)0 (y), y). (3.44) Therefore, from equations (3.21) and (3.44) we have, Q0(y) = l (−) 1 (y) + l(−)2 (y) g(−)2 (y) (3.45) 39In this equation let y∗(−) be the zero of g (−) 2 (y). Therefore, g(−)2 (y) = h(−)2 ( X(−)0 (y∗(−)), y∗(−) ) = 0. The following theorem is proved by H. Li and Y. Zhao in [50]. Theorem 3.1. Let z be a pole of P0(x) with the smallest modulus in the disk |x| < x3. Then one of the following three cases must hold: 1. z is a zero of h1(x, Y0(x)); 2. y∗ = Y0(z) is a zero of h2(X0(y), y) and |y∗| > 1; or 3. z∗ = X0(y∗) is a zero of h1(x, Y0(x)) and |z∗| > 1. Using theorem 3.1, it is easily shown that x∗, x˜1, x˜1(−), x3, and x(−)3 are singularities of P0(x), where x˜1 = X1(y∗), and x˜1(−) = X(−)1 (y∗(−)). The singularity with smallest modulus greater than 1 will be called the dominant singularity for P0(y), and consequently the radius of convergence of P0(y) can be extended to this point by analytic continuation [19]. Similarly, according to (3.42) and (3.43), y∗, y˜1, y3 are singularities ofQ0(y), where y˜1 = Y1(x∗), and according to (3.44) and (3.45), y∗(−), y˜1(−), and y(−)3 are singularities of Q(−)0 (x), where y˜1(−) = Y (−)1 (x∗). 3.4 Tauberian-Like Theorem In this section we recall the Tauberian-like theorem which is an im- portant tool for our calculation of asymptotic analysis of generating functions, P0(x), Q0(y) and Q(−)0 (y). Theorem 3.2. Assume that C(z) is an analytic function defined on 4(φ, ) = {z : z ≤ (1 + ), ≥ 0, < φ < pi 2 }, except at z = 1. Suppose C(z) = ∑ n≥0 cnz n , and a is the dominant singularity of C(z) 40on the convergence circle, and limz→a(1− z a )h C(z) = b. then cn ∼ b nRe(h)−1 Re(a)nΓ ( Re(h) ) as n→∞. (3.46) 3.5 Exact Tail Asymptotic for P0(x) In this section we will find the exact tail asymptotic behaviour of the marginal stationary distribution along x-axis, with applying the Tauberian-like theorem to the generating function P0(x). For this purpose we need the following equations. Since Y0(x) and Y (−)0 (x) can be written as Y0(x) = a(x) + b(x) √ 1− x x3 , Y (−)0 (x) = a(−)(x) + b(−)(x) √ 1− x x (−) 3 , (3.47) we can write the following equations, g1(x) = a1(x) + b1(x) √ 1− x x3 + b2(x) √ 1− x x (−) 3 , Y0(x3)− Y0(x) = (1− x x3 )a∗(x)− b(x) √ 1− x x3 , Y (−)0 (x(−)3 )− Y (−)0 (x) = (1− x x (−) 3 )a(−)∗(x)− b(−)(x) √ 1− x x (−) 3 , g1(x)− g1(x3) = (1− x x3 )a∗1(x) + b1(x) √ 1− x x3 , g1(x)− g1(x(−)3 ) = (1− x x (−) 3 )a(−)∗1 (x) + b1(x) √ 1− x x (−) 3 . (3.48) 41To simplify our later calculations let α(x) = (√ 1− x x3 a∗(x)− b(x) ) , α(−)(x) = (√ 1− x x (−) 3 a(−)∗(x)− b(−)(x) ) , β(x) = (√ 1− x x3 a∗1(x)− b1(x) ) , β(−)(x) = (√ 1− x x (−) 3 a (−)∗ 1 (x)− b(−)1 (x) ) , (3.49) Hence, according to (3.49) we can rewrite (3.48) as Y0(x3)− Y0(x) = √ 1− x x3 α(x), Y (−)0 (x(−)3 )− Y (−)0 (x) = √ 1− x x (−) 3 α(−)(x), g1(x)− g1(x3) = √ 1− x x3 β(x), g1(x)− g1(x(−)3 ) = √ 1− x x (−) 3 β(−)(x). (3.50) According to (3.40), (3.41), and (3.50), we divide the asymptotic behaviour of pim,0 into five cases: (1) exact geometric decay rate, (2) exact geometric decay rate with factor m−1/2, (3) exact geometric decay rate with factor m1/2, (4) exact geometric decay rate with factor m, and (5) exact geometric decay rate with factor m−3/2. Next, we will show the details on the five cases above. Case 1. If xdom = x∗, or xdom = x˜1, or xdom = x˜1(−), or xdom = x˜1 = x˜1 (−) , or xdom = x˜1 = x (−) 3 , or xdom = x˜1 (−) = x3, or xdom = x ∗ = x˜1 = x3, or xdom = x ∗ = x˜1 (−) = x (−) 3 , or xdom = x˜1 = x˜1 (−) = x3, or xdom = x˜1 = x˜1 (−) = x (−) 3 , or xdom = x ∗ = x˜1 = x3 = x (−) 3 , or xdom = x ∗ = x˜1 (−) = x3 = x (−) 3 , or xdom = x ∗ = x˜1 = x˜1 (−) = x3 = 42x (−) 3 holds, then pim,0 ∼ L (xdom)m , (3.51) where L is a constant, and xdom is dominant singularity of P0(x). We will prove it in the following conditions. Condition 1.1. If xdom = x∗, then P0(x) = f(x) + f (−)(x) + g0(x) (x− xdom) g∗1(x) , ⇒ lim x→xdom (1− x xdom )P0(x) = f(x ∗) + f (−)(x∗) + g0(x∗) x∗ g∗1(x∗) = L1, Therefore, applying theorem 3.2 we get pim,0 ∼ L1 (x∗)m . Condition 1.2. If xdom = x˜1, then P0(x) = f(x) (1− Y0(x) y∗ ) (1− Y0(x) y∗ ) + f (−)(x) + g0(x) g1(x) , ⇒ lim x→xdom (1− x xdom )P0(x) = y∗f(x˜1)(1− Y0(x˜1)y∗ ) x˜1 Y ′ 0(x˜1) g1(x˜1) = L2, Therefore, applying theorem 3.2 we get pim,0 ∼ L2 (x˜1)m . Condition 1.3. If xdom = x˜1(−), then 43P0(x) = f(x) + f (−)(x) (1− Y (−) 0 (x) y∗(−) ) (1− Y (−) 0 (x) y∗(−) ) + g0(x) g1(x) , ⇒ lim x→xdom (1− x xdom )P0(x) = y∗(−) f (−)(x˜1(−))(1− Y0(x˜1 (−)) y∗ ) x˜1 (−) dY (−) 0 (x) dx |x=x˜1(−) g1(x˜1 (−)) = L3, Therefore, applying theorem 3.2 we get pim,0 ∼ L3 (x˜1(−))m . Condition 1.4. If xdom = x˜1 = x˜1(−), then P0(x) = f(x) (1− Y0(x) y∗ ) (1− Y0(x) y∗ ) + f (−)(x) (1− Y (−) 0 (x) y∗(−) ) (1− Y (−) 0 (x) y∗(−) ) + g0(x) g1(x) , ⇒ lim x→xdom (1− x xdom )P0(x) = y∗ x dY0(x) dx f(x)(1− Y0(x) y∗ ) + y ∗(−) x dY (−)0 (x) dx f (−)(x)(1− Y (−) 0 (x) y∗(−) ) g1(x) ∣∣∣∣ x=x˜1 = L4, 44Therefore, applying theorem 3.2 we get pim,0 ∼ L4 (x˜1)m . Condition 1.5. If xdom = x˜1 = x(−)3 , then P0(x) = f(x) (1− Y0(x) y∗ ) (1− Y0(x) y∗ ) + f (−)(x) + g0(x) g1(x) , ⇒ lim x→xdom (1− x xdom )P0(x) = y∗ f(x)(1− Y0(x) y∗ ) x dY0(x) dx g1(x) ∣∣∣∣ x=x˜1 = L5, Therefore, applying theorem 3.2 we get pim,0 ∼ L5 (x˜1)m . Condition 1.6. If xdom = x˜1(−) = x3, then P0(x) = f(x) + f (−)(x) (1− Y (−) 0 (x) y∗(−) ) (1− Y (−) 0 (x) y∗(−) ) + g0(x) g1(x) , ⇒ lim x→xdom (1− x xdom )P0(x) = y∗(−) f (−)(x)(1− Y (−) 0 (x) y∗(−) ) x dY (−)0 (x) dx g1(x) ∣∣∣∣ x=x˜1 (−) = L6, 45Therefore, applying theorem 3.2 we get pim,0 ∼ L6 (x3)m . Condition 1.7. If xdom = x∗ = x˜1 = x3, P0(x) = y∗(1− Y0 y∗ ) f(x) √ 1− x xdom α(x) + f (−)(x) + g0(x) √ 1− x xdom β(x) , ⇒ lim x→xdom (1− x xdom )P0(x) = y∗ f(x)(1− Y0(x) y∗ ) α(x) β(x) ∣∣∣∣ x=x∗ = L7, Therefore, applying theorem 3.2 we get pim,0 ∼ L7 (x∗)m . Condition 1.8. If xdom = x∗ = x˜1(−) = x(−)3 , P0(x) = y∗(−)(1− Y (−) 0 (x) y∗(−) ) f (−)(x) √ 1− x xdom α(−)(x) + f(x) + g0(x) √ 1− x xdom β(−)(x) , ⇒ lim x→xdom (1− x xdom )P0(x) = y∗(−) f(x)(1− Y (−) 0 (x) y∗(−) ) α(−)(x) β(−)(x) ∣∣∣∣ x=x∗ = L8, 46Therefore, applying theorem 3.2 we get pim,0 ∼ L8 (x∗)m . Condition 1.9. If xdom = x˜1 = x˜1(−) = x3, then P0(x) = f (−)(x) ( 1− Y (−)0 (x) y∗(−) ) ( 1− Y (−)0 (x) y∗(−) ) + y∗ f(x) ( 1− Y0(x) y∗ ) √ 1− x xdom α(x) + g0(x) g1(x) , ⇒ lim x→xdom (1− x xdom )P0(x) = y∗ f (−)(x) ( 1− Y (−)0 (x) y∗(−) ) x dY (−)0 (x) dx g1(x) ∣∣∣∣ x=x˜1 = L9, Therefore, by theorem 3.2 we get pim,0 ∼ L9 (x3)m . Condition 1.10. If xdom = x˜1 = x˜1(−) = x(−)3 , then P0(x) = f(x) ( 1− Y0(x) y∗ ) ( 1− Y0(x) y∗ ) + y∗(−) f (−)(x) ( 1− Y (−)0 (x) y∗(−) ) √ 1− x xdom α(−)(x) + g0(x) g1(x) , ⇒ lim x→xdom (1− x xdom )P0(x) = y∗ f(x) ( 1− Y0(x) y∗ ) x dY0(x) dx g1(x) ∣∣∣∣ x=x˜1 = L10, 47Therefore, by theorem 3.2 we get pim,0 ∼ L10 (x˜1)m . Condition 1.11. If xdom = x∗ = x˜1 = x3 = x(−)3 , then P0(x) = y∗ f(x) ( 1− Y0(x) y∗ ) √ 1− x xdom α(x) + f (−)(x) + g0(x) √ 1− x xdom β(x) , ⇒ lim x→xdom (1− x xdom )P0(x) = y∗ f(x) ( 1− Y0(x) y∗ ) α(x) β(x) ∣∣∣∣ x=x∗ = L11, Therefore, by theorem 3.2 we get pim,0 ∼ L11 (x∗)m . Condition 1.12. If xdom = x∗ = x˜1(−) = x3 = x(−)3 , then P0(x) = y∗(−) f (−)(x) ( 1− Y (−)0 (x) y∗(−) ) √ 1− x xdom α(−)(x) + f(x) + g0(x) √ 1− x xdom β(x) , ⇒ lim x→xdom (1− x xdom )P0(x) = y∗(−) f (−)(x) ( 1− Y (−)0 (x) y∗(−) ) α(−)(x) β(x) ∣∣∣∣ x=x∗ = L12, 48Therefore, by theorem 3.2 we get pim,0 ∼ L12 (x∗)m . Condition 1.13. If xdom = x∗ = x˜1 = x˜1(−) = x3 = x(−)3 , then P0(x) = y∗ f(x) ( 1− Y0(x) y∗ ) √ 1− x xdom α(x) + y∗(−) f (−)(x) ( 1− Y (−)0 (x) y∗(−) ) √ 1− x xdom α(−)(x) √ 1− x xdom β(x) + g0(x)√ 1− x xdom β(x) , ⇒ lim x→xdom (1− x xdom )P0(x) = (y∗ f(x)(1− Y0(x) y∗ ) α(x) β(x) + y∗(−) f (−)(x) ( 1− Y (−)0 (x) y∗(−) ) α(−)(x) β(x) )∣∣∣∣ x=x∗ = L13, Therefore, by theorem 3.2 we get pim,0 ∼ L13 (x∗)m . Case 2. If xdom = x∗ = x3, or xdom = x∗ = x(−)3 , or xdom = x˜1 = x3, or xdom = x˜1 (−) = x (−) 3 , or xdom = x ∗ = x3 = x (−) 3 , or xdom = x˜1 = x3 = x (−) 3 , or xdom = x˜1 (−) = x3 = x (−) 3 holds, then pim,0 ∼ u m−1/2√ pi(xdom)m . (3.52) 49where u is a constant, and xdom is dominant singularity for P0(x). The proofs are given in the following conditions. Condition 2.1. If xdom = x∗ = x3, then P0(x) = f(x) + f (−)(x) + g0(x)√ 1− x xdom β(x) , ⇒ lim x→xdom √ 1− x xdom P0(x) = f(x) + f (−)(x) + g0(x) β(x) ∣∣∣∣ x=x∗ = u1, Therefore, by theorem 3.2 we get pim,0 ∼ u1 m −1/2 √ pi(x∗)m . Condition 2.2. If xdom = x∗ = x(−)3 , then P0(x) = f(x) + f (−)(x) + g0(x)√ 1− x xdom β(−)(x) , ⇒ lim x→xdom √ 1− x xdom P0(x) = f(x) + f (−)(x) + g0(x) β(−)(x) ∣∣∣∣ x=x∗ = u2, Therefore, by theorem 3.2 we get pim,0 ∼ u2 m −1/2 √ pi(x∗)m . Condition 2.3. If xdom = x˜1 = x3, then P0(x) = y∗ f(x) ( 1− Y0(x) y∗ ) √ 1− x xdom α(x) + f (−)(x) + g0(x) g1(x) , 50⇒ lim x→xdom √ 1− x xdom P0(x) = y∗ f(x) ( 1− Y0(x) y∗ ) α(x) g1(x) ∣∣∣∣ x=x˜1 = u3, Therefore, by theorem 3.2 we get pim,0 ∼ u3 m −1/2 √ pi(x3)m . Condition 2.4. If xdom = x˜1(−) = x(−)3 , then P0(x) = y∗(−) f (−)(x) ( 1− Y (−)0 (x) y∗(−) ) √ 1− x xdom α(−)(x) + f(x) + g0(x) g1(x) , ⇒ lim x→xdom √ 1− x xdom P0(x) = y∗(−) f (−)(x) ( 1− Y (−)0 (x) y∗(−) ) α(−)(x) g1(x) ∣∣∣∣ x=x˜1 (−) = u4, Therefore, by theorem 3.2 we get pim,0 ∼ u4 m −1/2 √ pi(x(−)3 )m . Condition 2.5. If xdom = x∗ = x3 = x(−)3 , then P0(x) = f(x) + f (−)(x) + g0(x)√ 1− x xdom β(x) , ⇒ lim x→xdom √ 1− x xdom P0(x) = f(x) + f (−)(x) + g0(x) β(x) ∣∣∣∣ x=x∗ = u5, 51Therefore, by theorem 3.2 we get pim,0 ∼ u5 m −1/2 √ pi(x∗)m . Condition 2.6. If xdom = x˜1 = x3 = x(−)3 , then P0(x) = y∗ f(x) ( 1− Y0(x) y∗ ) √ 1− x xdom α(x) + f (−)(x) + g0(x) g1(x) , ⇒ lim x→xdom √ 1− x xdom P0(x) = y∗ f(x) ( 1− Y0(x) y∗ ) α(x) g1(x) ∣∣∣∣ x=x˜1 = u6, Therefore, by theorem 3.2 we get pim,0 ∼ u6 m −1/2 √ pi(x3)m . Condition 2.7. If xdom = x˜1(−) = x3 = x(−)3 , then P0(x) = y∗(−) f (−)(x) ( 1− Y (−)0 (x) y∗(−) ) √ 1− x xdom α(−)(x) + f(x) + g0(x) g1(x) , ⇒ lim x→xdom √ 1− x xdom P0(x) = y∗(−) f (−)(x) ( 1− Y (−)0 (x) y∗(−) ) α(−)(x) g1(x) ∣∣∣∣ x=x˜1 (−) = u7, 52Therefore, by theorem 3.2 we get pim,0 ∼ u7 m −1/2 √ pi(x3)m . Case 3. If xdom = x∗ = x˜1 = x(−)3 , or xdom = x∗ = x˜1(−) = x3, or xdom = x ∗ = x˜1 = x˜1 (−) = x3, or xdom = x ∗ = x˜1 = x˜ (−) 1 = x (−) 3 holds, then pim,0 ∼ n m1/2√ pi 2 (xdom)m . (3.53) where n is a constant, and xdom is dominant singularity for P0(x). The proofs are given in the following conditions. Condition 3.1 If we have xdom = x∗ = x˜1 = x(−)3 , then P0(x) = f(x) ( 1− Y0(x) y∗ ) ( 1− Y0(x) y∗ ) + f (−)(x) + g0(x) √ 1− x xdom β(−)(x) , lim x→xdom ( 1− x xdom )3/2 P0(x) = y∗ f(x) ( 1− Y0(x) y∗ ) x dY0(x) dx β (−)(x) ∣∣∣∣ x=x∗ = n1, Therefore, using theorem 3.2 we get pim,0 ∼ n1 m 1/2 √ pi 2 (x∗)m . Condition 3.2. If xdom = x∗ = x˜1(−) = x3, then we have 53P0(x) = f (−)(x) ( 1− Y (−)0 (x) y∗(−) ) ( 1− Y (−)0 (x) y∗(−) ) + f(x) + g0(x) √ 1− x xdom β(x) , lim x→xdom ( 1− x xdom )3/2 P0(x) = y∗(−) f (−)(x) ( 1− Y (−)0 (x) y∗(−) ) x dY (−)0 (x) dx β(x) ∣∣∣∣ x=x∗ = n2, Therefore, using theorem 3.2 we get pim,0 ∼ n2 m 1/2 √ pi 2 (x∗)m . Condition 3.3. If we have xdom = x∗ = x˜1 = x˜1(−) = x3, then P0(x) = f (−)(x) ( 1− Y (−)0 (x) y∗(−) ) ( 1− Y (−)0 (x) y∗(−) ) + y∗ f(x) ( 1− Y0(x) y∗ ) √ 1− x xdom α(x) + g0(x) √ 1− x xdom β(x) , lim x→xdom ( 1− x xdom )3/2 P0(x) = y∗(−) f (−)(x) ( 1− Y (−)0 (x) y∗(−) ) x dY (−)0 (x) dx β(x) ∣∣∣∣ x=x∗ = n3, 54Therefore, using theorem 3.2 we get pim,0 ∼ n3 m 1/2 √ pi 2 (x∗)m . Condition 3.4. If xdom = x∗ = x˜1 = x˜(−)1 = x (−) 3 , then we have P0(x) = f(x) ( 1− Y0(x) y∗ ) ( 1− Y0(x) y∗ ) + y∗(−) f (−)(x) ( 1− Y (−)0 (x) y∗(−) ) √ 1− x xdom α(−)(x) + g0(x) √ 1− x xdom β(−)(x) , lim x→xdom ( 1− x xdom )3/2 P0(x) = y∗ f(x) ( 1− Y0(x) y∗ ) x dY0(x) dx β (−)(x) ∣∣∣∣ x=x∗ = n4, Therefore, using theorem 3.2 we get pim,0 ∼ n4 m 1/2 √ pi 2 (x∗)m . Case 4. If xdom = x∗ = x˜1, or xdom = x∗ = x˜1(−), or xdom = x∗ = x˜1 = x˜1 (−) holds, then pim,0 ∼ r m (xdom)m , (3.54) where r is a constant, and xdom is dominant singularity of P0(x). We will give the proofs in the following cases. 55Condition 4.1. If we have xdom = x∗ = x˜1, then P0(x) = f(x) ( 1− Y0(x) y∗ ) ( 1− Y0(x) y∗ ) + f (−)(x) + g0(x) ( x− xdom ) g∗1(x) , lim x→xdom ( 1− x xdom )2 P0(x) = y∗ f(x) ( 1− Y0(x) y∗ ) x2 dY0(x) dx g ∗ 1(x) ∣∣∣∣ x=x∗ = r1, Therefore, using theorem 3.2 we get pim,0 ∼ r1 m (x∗)m . Condition 4.2. If we have xdom = x∗ = x˜1(−), then P0(x) = f (−)(x) ( 1− Y (−)0 (x) y∗(−) ) ( 1− Y (−)0 (x) y∗(−) ) + f(x) + g0(x) ( x− xdom ) g∗1(x) , lim x→xdom ( 1− x xdom )2 P0(x) = y∗(−) f (−)(x) ( 1− Y (−)0 (x) y∗(−) ) x2 dY (−)0 (x) dx g ∗ 1(x) ∣∣∣∣ x=x∗ = r2, Therefore, using theorem 3.2 we get pim,0 ∼ r2 m (x∗)m . 56Condition 4.3. If xdom = x∗ = x˜1 = x˜1(−), then we have P0(x) = f(x) ( 1− Y0(x) y∗ ) ( 1− Y0(x) y∗ ) + f (−)(x) ( 1− Y (−)0 (x) y∗(−) ) ( 1− Y (−)0 (x) y∗(−) ) + g0(x) ( x− xdom ) g∗1(x) , lim x→xdom ( 1− x xdom )2 P0(x) = (y∗ f(x)(1− Y0(x) y∗ ) x2 dY0(x) dx g ∗ 1(x) + y∗(−) f (−)(x) ( 1− Y (−)0 (x) y∗(−) ) x2 dY (−)0 (x) dx g ∗ 1(x) )∣∣∣∣ x=x∗ = r3, Therefore, using theorem 3.2 we get pim,0 ∼ r3 m (x∗)m . Case 5. If xdom = x3, or xdom = x(−)3 , or xdom = x3 = x (−) 3 holds, then pim,0 ∼ s m−3/2√ pi(xdom)m , (3.55) where s is a constant, and xdom is the dominant singularity of P0(x). The proofs are given in the following conditions, but first we need to define the following functions in order to simplify the later cal- culations. Let L(x) =− h2(x, Y0(x))dQ0(Y0(x))dx +( −Q0(Y0(x))dh2(x, y)dy − pi0,0 dh0(x, y) dy )∣∣∣∣ y=Y0(x) , 57L(−)(x) =− h(−)2 (x, Y (−)0 (x))dQ (−) 0 (Y (−)0 (x)) dx +( −Q(−)0 (Y (−)0 (x))dh (−) 2 (x, y) dy − pi0,0 dh(−)0 (x, y) dy )∣∣∣∣ y=Y (−)0 (x) , N(x) =− ( Q0(Y0(x))dh2(x, y)dx + pi0,0 dh0(x, y) dx )∣∣∣∣ y=Y0(x) + − ( Q(−)0 (Y (−)0 (x))dh (−) 2 (x, y) dx + pi0,0 dh(−)0 (x, y) dx )∣∣∣∣ y=Y (−)0 (x) , O(x) = dh1(x, y)dy ∣∣∣∣ y=Y0(x) , O(−)(x) = dh (−) 1 (x, y) dy ∣∣∣∣ y=Y (−)0 (x) , Z(x) = dh1(x, y)dx ∣∣∣∣ y=Y0(x) + dh(−)1 (x, y) dx ∣∣∣∣ y=Y (−)0 (x) , M(x) = L(x)g1(x)− O(x) ( f(x) + f (−)(x) + g0(x) ) , M (−)(x) = L(−)(x)g1(x)−O(−)(x) ( f(x) + f (−)(x) + g0(x) ) , U(x) = N(x)g1(x)− Z(x) ( f(x) + f (−)(x) + g0(x) ) , K(x) = da(x)dx + db(x) dx √ 1− x x3 , K(−)(x) = da (−)(x) dx + db(−)(x) dx √ 1− x x (−) 3 . (3.56) Condition 5.1. If we have xdom = x3, we write, 58dP0(x) dx = ( K(x)− b(x) 2x3 √ 1− x x3 ) M(x) ( g1(x) )2 + ( K(−)(x)− b (−)(x) 2x(−)3 √ 1− x x (−) 3 ) M (−)(x) + U(x) ( g1(x) )2 , (3.57) lim x→xdom √ 1− x xdom d ( P0(x) ) dx = −b(x) M(x) 2x ( g1(x) )2 ∣∣∣∣ x=x3 = s1, Therefore, using theorem 3.2 we get pim,0 ∼ s1 m −3/2 √ pi(x3)m . Condition 5.2. If xdom = x(−)3 , according to (3.57) we have, lim x→xdom √ 1− x xdom d ( P0(x) ) dx = −b(−)(x) M (−)(x) 2x ( g1(x) )2 ∣∣∣∣ x=x (−) 3 = s2, Therefore, using theorem 3.2 we get pim,0 ∼ s2 m −3/2 √ pi(x(−)3 )m . bf Condition 5.3. If we have xdom = x3 = x(−)3 , according to (3.57) 59we have, lim x→xdom √ 1− x xdom d ( P0(x) ) dx = −b(x) M(x)− b(−)(x) M (−)(x) 2x ( g1(x) )2 ∣∣∣∣ x=x3 = s3, Therefore, using theorem 3.2 we get pim,0 ∼ s3 m −3/2 √ pi(x3)m . 3.6 Exact Tail Asymptotic for Q0(y) In this section we find the exact tail asymptotic behaviour of the marginal stationary distribution along y-axis with applying theorem 3.2 to the generating function Q0(y). From (3.42) and (3.43) we have Q0(y) = l1(y) + l2(y)g2(y) . Since X0(y) can be written as X0(y) = c(y) + d(y) √ 1− y y3 , (3.58) we can write the following equations g2(y) = c1(y) + d1(y) √ 1− y y3 , X0(y3)−X0(y) = (1− yy3)c ∗(y)− d(y) √ 1− y y3 , g2(y3)− g2(y) = c∗1(y)(1− yy3 )− d1(y) √ 1− y y3 . (3.59) Hence, according to (3.42), (3.43), and (3.59), we characterize the exact tail asymptotic behaviour of pi0,n into four cases: (1) exact 60geometric decay rate, (2) exact geometric decay rate with factor n−1/2, (3) exact geometric decay rate with factor n−3/2, and (4) exact geometric decay rate with factor n. In the following we will show the details on the cases above. Case 1. If the conditions, |ydom| = y∗ < min {y˜1, y3}, or |ydom| = y∗ = y˜1 = y3, or |ydom| = y˜1 < min {y∗, y3} hold, then pi0,n ∼ c (ydom)n , (3.60) where c is a constant, and ydom is the dominant singularity of Q0(y). We will give the proof in the following conditions. Condition 1.1. If |ydom| = y∗ < min {y˜1, y3}, then we have Q0(y) = l1(y) + l2(y)(y − ydom)g∗2(y), ⇒ lim y→ydom ( 1− y ydom ) Q0(y) = l1(y) + l2(y)g∗2(y) ∣∣∣∣ y=y∗ = c1. Therefore, using theorem 3.2 we get pi0,n ∼ c1 (y∗)n . Condition 1.2. If |ydom| = y∗ = y˜1 = y3, then Q0(y) = x∗ l1(y) ( 1− X0(y) x∗ ) √ 1− y ydom (√ 1− y ydom c∗(y)− d(y) ) + l2(y) √ 1− y ydom (√ 1− y ydom c∗1(y)− d1(y) ) , ⇒ lim y→ydom ( 1− y ydom ) Q0(y) = 61x∗ l1(y) ( 1− X0(y) x∗ ) (√ 1− y ydom c∗(y)− d(y) )(√ 1− y ydom c∗1(y)− d1(y) )∣∣∣∣ y=y∗ = c2. Therefore, using theorem 3.2 we get pi0,n ∼ c2 (y∗)n . Condition 1.3. If |ydom| = y˜1 < min {y∗, y3}, then Q0(y) = l1(y) ( 1− X0(y) x∗ ) ( 1− X0(y) x∗ ) + l2(y) g2(y) , ⇒ lim y→ydom ( 1− y ydom ) Q0(y) = x∗ l1(y) ( 1− X0(y) x∗ ) y dX0(y) dy g2(y) ∣∣∣∣ y=y˜1 = c3. Therefore, using theorem 3.2 we get pi0,n ∼ c3 (y˜1)n . Case 2. If the conditions, |ydom| = y∗ = y3 < y˜1, or |ydom| = y˜1 = y3 < y∗ hold, then pi0,n ∼ t n−1/2√ pi(ydom)n , (3.61) where t is a constant, and ydom is the dominant singularity of Q0(y). The proofs are given in the following conditions. Condition 2.1. If |ydom| = y∗ = y3 < y˜1, then Q0(y) = l1(y) + l2(y)√ 1− y ydom (√ 1− y ydom c∗1(y)− d1(y) ) , 62⇒ lim y→ydom √ 1− y ydom Q0(y) = l1(y) + l2(y)(√ 1− y ydom c∗1(y)− d1(y) )∣∣∣∣ y=y∗ = t1. Therefore, using theorem 3.2 we get pi0,n ∼ t1 n−1/2√ pi(y∗)n . Condition 2.2. If |ydom| = y˜1 = y3 < y∗, then Q0(y) = x∗ l1(y) ( 1− X0(y) x∗ ) √ 1− y ydom (√ 1− y ydom c∗(y)− d(y) ) + l2(y) g2(y) , ⇒ lim y→ydom √ 1− y ydom Q0(y) = x∗ l1(y) ( 1− X0(y) x∗ ) (√ 1− y ydom c∗(y)− d(y) ) g2(y) ∣∣∣∣ y=y˜1 = t2. Therefore, using theorem 3.2 we get pi0,n ∼ t2 n−1/2√ pi(y3)n . Case 3. If the condition |ydom| = y3 < min {y˜1, y∗} holds, then pi0,n ∼ u n−3/2√ pi(ydom)n , (3.62) where u is a constant, and ydom is the dominant singularity of Q0(y). The proof is given in the following condition, but first we need the following assigned notations in order to simplify the calculations. 63In (3.19) let C(x) = P −1(x)A(x) + pi0,−1B(x). Therefore, according to (3.42) we have Q0(y) = l1(y)− pi0,0h0(X0(y), y)− C(X0(y))g2(y) . (3.63) Also lets define D(y) =− h1(X0(y), y)dP0(X0(y))dx − dC(X0(y)) dx −( P0(X0(y))dh1(x, y)dx + pi0,0 dh0(x, y) dx )∣∣∣∣ x=X0(y) , E(y) = − ( P0(X0(y))dh1(x, y)dy + pi0,0 dh0(x, y) dy )∣∣∣∣ x=X0(y) , I(y) = dh2(x, y)dx ∣∣∣∣ x=X0(y) , J(y) = dh2(x, y)dy ∣∣∣∣ x=X0(y) , V (y) = D(y)g2(y)− I(y) ( l1(y) + l2(y) ) , W (y) = E(y)g2(y)− J(y) ( l1(y) + l2(y) ) , R(y) = dc(y)dy + d d(y) dy √ 1− y y3 . (3.64) Condition 3.1. If |ydom| = y3 < min {y˜1, y∗}, then dQ0(y) dy = ( R(y)− d(y) 2y3 √ 1− y y3 ) V (y) +W (y) ( g2(y) )2 , ⇒ lim y→ydom √ 1− y ydom dQ0(y) dy = −d(y)V (y) 2y3 ( g2(y) )2 ∣∣∣∣ y=y3 = u1. 64Therefore, using theorem 3.2 we get pi0,n ∼ u1 n −3/2 √ pi(y3)n . Case 4. If the condition |ydom| = y∗ = y˜1 < y3 holds, then pi0,n ∼ v n (ydom)n , (3.65) where v is a constant, and ydom is the dominant singularity of Q0(y). The proof is given below. Condition 4.1. If |ydom| = y∗ = y˜1 < y3, then Q0(y) = l1 ( 1− X0(y) x∗ ) ( 1− X0(y) x∗ ) + l2(y) (y − ydom) g∗2(y) , ⇒ lim y→ydom ( 1− y ydom )2 Q0(y) = x∗ l1(y) ( 1− X0(y) x∗ ) y2 dX0(y) dy g ∗ 2(y) ∣∣∣∣ y=y∗ = v1. Therefore, using theorem 3.2 we get pi0,n ∼ v1 n (y∗)n . Because of the symmetry, the exact tail asymptotic behaviour of the marginal stationary distribution along −y-axis is similar to the asymptotics behaviour of pi0,n. Therefore, we are not going through the details of the analysis of Q(−)0 (y). 65Chapter 4 Exact Tail Asymptotic Behaviour of the Joint Stationary Distributions of Generalized-JSQ with Kernel Method 4.1 Generalized-JSQModel and Kernel Method In this section we describe the Generalized-JSQ model with two servers. We will model this queue as a two-dimensional random walk in the first and fourth quadrant of the random walk plane, and for each quadrant we will write a specific fundamental form. In the Generalized-JSQ model we have three arrival streams. The first stream is a Poisson process with rate of λ1, which is dedicated to server 1. That is, this stream only goes to server 1. The second stream is a Poisson process with rate of λ2, which is dedicated to server 2, and the third stream is a Poisson process with rate of λ, which is called smart stream. That is, this stream determines the shorter queue, and joins that queue. We have exponential distribu- tions for service times, where the rate of service in server 1 is µ1, and in server 2 is µ2. Since G-JSQ is a two-dimensional random walk model, and we as- sume that random walks are considered to be without jumps, that is, the maximum step in any direction is 1. Therefore, the transition 66probabilities for the Generalized-JSQ model are as follows, ¯P(a,b),(a+i,b+j) = pi,j if a ≥ 1 and b ≥ 1, −1 ≤ i, j ≤ 1, p0i,j if (a, b) = (0, 0), −1 ≤ i, j ≤ 1, p(1)i,j if a ≥ 1 and b = 0, −1 ≤ i, j ≤ 1, p(2)i,j if a = 0 and b ≥ 1, −1 ≤ i, j ≤ 1, p(2−)i,j if a = 0 and b ≤ −1, −1 ≤ i, j ≤ 1, p(−)i,j if a ≥ 1 and b ≤ −1, −1 ≤ i, j ≤ 1, where pi,j, p(0)i,j , p (1) i,j , p (2) i,j , p (−) i,j , and p (2−) i,j are non-negative real num- bers having the following property, ∑ i,j=0±1 pi,j = 1, ∑ i,j=0,±1 p(1)i,j = 1, ∑ i=0,1,j=0,±1 p(0)i,j = 1, ∑ i=0,1,j=0,±1 p(2)i,j = 1, ∑ i=0,1,j=0,±1 p(2−)i,j = 1, and ∑ i,j=0,±1 p(−)i,j = 1. By modelling the Generalized-JSQ into the first and fourth quad- rant of the random walk plane, where x-axis corresponds to min{Q1, Q2} and y-axis corresponds to (Q1 −Q2), we have the following proba- bilities, p1,−1 = λ1 + λ, p0,1 = λ2, p−1,1 = µ1, p0,−1 = µ2, p(1)0,1 = λ2 + λ/2, p(1)−1,1 = µ1, p(1)0,−1 = λ1 + λ/2, p(1)−1,−1 = µ2, p(2)0,1 = λ2, p (2) 1,−1 = λ1 + λ, p (2) 0,−1 = µ2, p (2) 0,0 = µ1, p(0)0,1 = λ2 + λ/2, p(0)0,−1 = λ1 + λ/2, p(0)0,0 = µ2 + µ2, p(−)1,−1 = λ1 + λ, p (−) 0,1 = λ1, p (−) −1,1 = µ2, p (−) 0,−1 = µ1, p(2−)1,−1 = λ2 + λ, p (2−) 0,1 = λ1, p (2−) 0,−1 = µ1, p (2−) 0,0 = µ2. (4.1) From the transition probabilities, one can write the balance equa- tions as follows, (1) for interior of the first quadrant: if n = 1, then pim,1 = µ2pim,2 + (λ1 + λ)pim−1,2 + (λ2 + λ/2)pim,0 + µ1pim+1,0, 67if n ≥ 2, then pim,n = (λ1 + λ)pim−1,n+1 + µ2pim,n+1 + µ1pim+1,n−1 + λ2pim,n−1, (2) for the boundary on x-axis: if n = 0, then pim,0 = (λ1 + λ)pim−1,1 + µ2pim,1 + µ1pim,−1 + (λ2 + λ)pim−1,−1, (3) for interior of the fourth quadrant: if n = −1, then pim,−1 = (λ1 + λ/2)pim,0 + (λ2 + λ)pim−1,−2 + µ2pim+1,0 + µ1pim,−2, if n ≤ −2, then pim,n = λ1pim,n+1 + (λ2 + λ)pim−1,n−1 + µ2pim+1,n+1 + µ1pim,n−1. (4.2) Hence, by using the generating functions (3.1), (3.2), (3.3), and balance equations (4.2), we can derive two fundamental forms in- cluding one equation for the first quadrant , and one equation for the fourth quadrant as follows, (1) for the first quadrant, P (x, y)h(x, y) =P0(x)h1(x, y) +Q0(y)h2(x, y) + pi0,0h0(x, y)+ pi0,−1B(x) + p−1(x)A(x), (4.3) (2) and for the fourth quadrant, P (−)(x, y)h(−)(x, y) =P0(x)h(−)1 (x, y) +Q(−)0 (y)h(−)2 (x, y)+ pi0,0h(−)0 (x, y)− pi0,−1B(x) + µ1)− p −1(x)A(x), 68where, h(x, y) = ( 1− µ2y−1 − x(λ1 + λ)y−1 − µ1x−1y − λ2y ) , h(−)(x, y) = ( 1− µ1y−1 − (λ2 + λ)xy−1 − µ2x−1y − λ1y ) , h1(x, y) = ( µ1x−1y + (λ2 + λ/2)y − 1 ) , h(−)1 (x, y) = ( µ2x−1y + (λ1 + λ/2)y ) , h2(x, y) = ( (λ1 + λ)xy−1 + λ2y + µ2y−1 + µ1 − 1 ) , h(−)2 (x, y) = ( (λ2 + λ)xy−1 + λ1y + µ1y−1 + µ2 − 1 ) , h0(x, y) = ( (λ2 + λ/2)y + µ1 + µ2 − 1 ) , h(−)0 (x, y) = ( (λ1 + λ/2)y ) , A(x) = ( (λ2 + λ)x+ µ1 ) , B(x) = ( (λ2 + λ)x+ µ1 ) . (4.4) Therefore, according to lemma 3.1. the fundamental form for the both first and fourth quadrant is P (x, y)h(x, y) + P (−)(x, y)h(−)(x, y) = P0(x)H1(x, y)+ Q0(y)h2(x, y) +Q(−)0 (y)h(−)2 (x, y) + pi0,0H0(x, y), (4.5) where, H1(x, y) = h1(x, y) + h(−)1 (x, y), H0(x, y) = h0(x, y) + h(−)0 (x, y). (4.6) 694.2 Branch Points and Branches In this section we introduce the kernel equation for the Generalized- JSQ model, and provide details on properties of branches and branch points of the kernel equation. The polynomial h(x, y) is called ker- nel. Therefore, according to (3.23), for the generalized-JSQ model, kernel equation is h(x, y) = a(x)y2 + b(x)y + c(x) = 0, where a(x) = ( − λ2x− µ1 ) , b(x) = x, c(x) = ( − (λ1 + λ)x2 − µ2x ) . (4.7) from (3.25), the branches of the kernel equation, h(x, y) = 0, are Y±(x) = −b(x)± √ D1(x) 2a(x) , where D1(x) = b(x)2 − 4a(x)c(x). Furthermore, as stated in (3.28), kernel equation for the first quad- rant can be written as, h(x, y) = a˜(y)x2 +˜b(y)x+ c˜(y) = 0, where a˜(y) = ( − λ1 − λ ) , ˜b(y) = ( − λ2y2 + y − µ2 ) , c˜(y) = ( − µ1y2 ) . (4.8) 70from (3.30), the solutions for x are, X±(y) = − ˜b(y)±√D2(y) 2a˜(y) , where D2(y) = ˜b(y)2 − 4a˜(y)c˜(y), Similarly as stated in (3.33), kernel equation of the fourth quadrant is h(−)(x, y) = a(−)(x)y2 + b(−)(x)y + c(−)(x) = 0, where a(−)(x) = (−λ1x− µ2), b(−)(x) = x, c(−)(x) = (−(λ2 + λ)x2 − µ1x), (4.9) and from (3.37), the kernel equation for the fourth quadrant can be written as h(−)(x, y) = a˜(−)(y)x2 +˜b(−)(y)x+ c˜(−)(y) = 0, where a˜(−)(y) = (−λ2 − λ), ˜b(−)(y) = (−λ1y2 + y − µ1), c˜(−)(y) = (−µ2y2). (4.10) 4.3 Asymptotic Analysis of P0(x) of the Generalized- JSQ In this section we make P0(x) of the G-JSQ in terms of other gener- ating functions from the fundamental forms. For simplification and reducing the unknown generating functions, we make the kernel 71polynomial zero by substituting the branches of kernel polynomial of the Generalized-JSQ into the fundamental form of the first and fourth quadrant, and consequently get the simpler expression for P0(x). Therefore, recalling (4.6) we have P0(x) ( h1(x, Y0(x)) + h(−)1 (x, Y (−)0 (x)) ) +Q0(Y0(x))h2(x, Y0(x))+ Q(−)0 (Y (−)0 (x))h(−)2 (x, Y (−)0 (x))+ pi0,0 ( h0(x, Y0(x)) + h(−)0 (x, Y (−)0 (x)) ) = 0, (4.11) where h1(x, Y0(x)), h2(x, Y0(x)), h(−)1 (x, Y (−)0 (x)), h(−)2 (x, Y (−)0 (x)), h0(x, Y0(x)), and h(−)0 (x, Y0(x)) can be found from (4.5). In order to analyse the asymptotic behaviour of P0(x), we need to get information about the dominant singularity of P0(x). The following lemma gives the solutions of the equation ( h1(x, Y0(x))+ h(−)1 (x, Y (−)0 (x)) ) = 0, which is one of the singularities of P0(x). Lemma 4.1. Suppose the following two inequalities hold, (1) µ1 − µ2 − 2µ1µ2 + 2λ2µ21 + 2λ2µ22 + 2µ1µ22 + 4µ21µ2 − 3µ21+ 2µ31 + µ22 + 4λ2µ1µ2 < 0, (2) µ1 − µ2 − 2µ1µ2 + 2λ2µ21 + 2λ2µ22 + 2λµ21 + 2λµ22 + 2µ1µ22+ 4µ21µ2 − 3µ21 + 2µ31 + µ22 + 4λ2µ1µ2 + 4λµ1µ2 > 0, then x∗ = (1 ρ )2 = ( µ1 + µ2λ1 + λ2 + λ) 2 is the solution of h1(x, Y0(x))+ h(−)1 (x, Y (−)0 (x)) = 0. Proof. If the first inequality holds, we have Y0(ρ−2) = ρ−1. Also from the second inequality we have Y (−)0 (ρ−2) = ρ−1. Therefore, h1(ρ−2, Y0(ρ−2)) + h(−)1 (ρ−2, Y (−)0 (ρ−2)) = 0. This completes the proof. From now on let x∗ be the solution of h1(x, Y0(x))+h(−)1 (x, Y (−)0 (x)) = 0, with the smallest modulus greater than 1. Hence, h1(x∗, Y0(x∗))+ h(−)1 (x∗, Y (−)0 (x∗)) = 0, for |x∗| > 1. 724.4 Asymptotic Analysis of Q0(y) of the Generalized- JSQ Recall (4.3), which gives the fundamental form for the first quad- rant. Now with replacing x by X0(y) in (4.3) we get, Q0(y) =−P0(X0)h1(X0, y)− pi0,0h0(X0, y)h2(X0, y) − (P −1(X0) + pi0,−1)((λ2 + λ)X0 + µ1) h2(X0, y) . (4.12) Now for finding the solution of h2(X0, y) = 0 with the smallest modulus greater than 1, we define the function, f(y) = a˜(y)h2(X0, y)h2(X1, y). Hence, we have the following lemma. Lemma 4.2. y = µ2λ2 is the number with the smallest modulus greater than 1 which makes f(y) = 0. Proof. Equation f(y) = a˜(y)h2(X0, y)h2(X1, y) = 0 implies, −(λ1 + λ)µ1y(y − 1)(λ2y − µ2) = 0. Therefore, y = µ2λ2 is the zero of f(y) with the smallest modulus greater than 1. Lemma 4.3. y = µ2λ2 = y∗ is the zero of h2(X0(y), y). Proof. From (4.11) one can get D2(µ2λ2 ) = µ22(2µ1 + µ2 + λ2 − 1)2 λ22 , since we assumed the stability conditions for the system, (µ1 > λ1 +λ), which implies the inequality, 2µ1 +µ2 +λ2 > 1, from (4.11) one can get 73X+(µ2λ2 ) = µ2 λ2 , and X − (µ2λ2 ) = µ2µ1 λ2(λ1 + λ). With the above stability condition it is straight forward to see that X0(µ2λ2 ) = µ2 λ2 , Therefore, h2 ( X0(µ2λ2 ), µ2 λ2 ) = (λ1 + λ)µ2λ2 + λ2( µ2 λ2 )2 + µ2 + (µ1 − 1)µ2λ2 = 0. From now on we denote the solution of h2(X0(y), y) = 0 with the smallest modulus greater than 1 by y∗. 4.5 Asymptotic Analysis of Q(−)0 (y) of the Generalized- JSQ In this section, in order to analyse the asymptotic behaviour of Q(−)0 (y) of the Generalized-JSQ, we replace x by X(−)0 (y) in (4.4) to get, Q(−)0 (y) =−P0(X (−) 0 (y))h(−)1 (X(−)0 (y), y)− pi0,0h(−)0 (X(−)0 (y), y) h(−)2 (X(−)0 (y), y) + −(P −1(X(−)0 (y)) + pi0,−1)((λ2 + λ)X(−)0 (y) + µ1) h(−)2 (X(−)0 (y), y) . Lemma 4.4. Let g(y) = a˜(−)(y)h(−)2 (X(−)0 (y), y)h(−)2 (X(−)1 (y), y), then y = µ1 λ1 is a solution of g(y) = 0, with the smallest modulus greater than 1. Proof. If g(y) = a˜(−)(y)h(−)2 (X(−)0 (y), y)h(−)2 (X(−)1 (y), y) = 0, then −(λ2 + λ)µ2y(y − 1)(λ1y − µ1) = 0. Therefore, y = µ1λ1 is a solution of g(y) = 0, with the smallest modulus greater than 1. 74Lemma 4.5. y = µ1λ1 is a solution of h(−)2 (X(−)0 (y), y) = 0. Proof. From (4.15) we can get D(−)2 (µ1λ1 ) = µ21(µ2 − λ2 − λ)2 λ21 . By using (4.15) and assuming the stability condition, which is (µ2 > λ2 + λ), we can get X(−)+ (µ1λ1 ) = µ1 λ1 , and X(−) − (µ1λ1 ) = µ1µ2 λ1(λ2 + λ). Therefore, h(−)2 (X(−)0 (µ1λ1 ), µ1 λ1 ) = (λ2 + λ)µ1λ1 + λ1( µ1 λ1 )2 + µ1 + (µ2 − 1)µ1λ1 = 0. From now on we denote the solution of h(−)2 (X(−)0 (y), y) = 0 with the smallest modulus greater than 1 by y∗(−). 4.6 Exact Tail Asymptotic for P0(x) of the Generalized- JSQ In this section according to the results of the section 3.5 of this thesis, we find the exact tail asymptotics behaviour of pim,0 of the generalized-JSQ by applying the theorem 3.2 to P0(x). If the in- equalities of lemma 4.1. and two stability conditions, µi > λi+λ for i = 1, 2 hold, then the results of the section 3.5, indicate that the dominant singularity of P0(x) can be either (1ρ) 2 = ( µ1 + µ2λ1 + λ2 + λ) 2 , or X1( 1ρ2 ) = X1( µ2 λ2 ), or X(−)1 ( 1ρ1) = X (−) 1 (µ1λ1 ), or x3, the third branch point of h(x, y), or x(−)3 , the third branch point of h(−)(x, y). Therefore, we can characterize the exact tail asymptotic behaviour of P0(x) of the Generalized-JSQ into 5 cases: (1) exact geometric decay rate, (2) exact geometric decay rate with factor m−1/2, (3) exact geometric decay rate with factor m1/2, (4) exact geometric decay rate with factor m, and (5) exact geometric decay rate with factor m−3/2. Next, we will show the details on the five cases above. 75Case 1. If xdom = (1ρ) 2 , or xdom = X1( 1ρ2 ), or xdom = X (−) 1 ( 1ρ1 ), or xdom = X1( 1ρ2 ) = X (−) 1 ( 1ρ1 ), or xdom = X1( 1 ρ2 ) = x(−)3 , or xdom = X(−)1 ( 1ρ1) = x3, or xdom = ( 1 ρ )2 = X1( 1ρ2 ) = x3, or xdom = ( 1 ρ )2 = X(−)1 ( 1ρ1) = x (−) 3 , or xdom = X1( 1ρ2 ) = X (−) 1 ( 1ρ1 ) = x3, or xdom = X1( 1ρ2) = X (−) 1 ( 1ρ1) = x (−) 3 , or xdom = (1ρ) 2 = X1( 1ρ2) = x3 = x (−) 3 , or xdom = (1ρ) 2 = X(−)1 ( 1ρ1 ) = x3 = x (−) 3 , or xdom = (1ρ) 2 = X1( 1ρ2) = X(−)1 ( 1ρ1) = x3 = x (−) 3 holds, then pim,0 ∼ L (xdom)m , where (limx→xdom(1 − xxdom )P0(x) = L) is a constant, and xdom is dominant singularity of P0(x), which can be obtained from case 1 of section 3.5. Case 2. If xdom = (1ρ) 2 = x3, or xdom = (1ρ) 2 = x (−) 3 , or xdom = X1( 1ρ2) = x3, or xdom = X (−) 1 ( 1ρ1) = x (−) 3 , or xdom = (1ρ) 2 = x3 = x (−) 3 , or xdom = X1( 1ρ2) = x3 = x (−) 3 , or xdom = X (−) 1 ( 1ρ1) = x3 = x (−) 3 holds, then pim,0 ∼ u m−1/2√ pi(xdom)m , where (limx→xdom √ 1− x xdom P0(x) = u) is a constant, and xdom is dominant singularity for P0(x), which can be obtained from case 2 of section 3.5. Case 3. If xdom = (1ρ) 2 = X1( 1ρ2 ) = x (−) 3 , or xdom = (1ρ) 2 = 76X(−)1 ( 1ρ1) = x3, or xdom = ( 1 ρ )2 = X1( 1ρ2 ) = X (−) 1 ( 1ρ1) = x3, or xdom = (1ρ) 2 = X1( 1ρ2) = X (−) 1 ( 1ρ1 ) = x (−) 3 holds, then pim,0 ∼ n m1/2√ pi 2 (xdom)m , where (limx→xdom ( 1− x xdom )3/2 P0(x) = n) is a constant, and xdom is dominant singularity for P0(x), which can be obtained from case 3 of section 3.5. Case 4. If xdom = (1ρ) 2 = X1( 1ρ2), or xdom = ( 1 ρ )2 = X(−)1 ( 1ρ1), or xdom = (1ρ) 2 = X1( 1ρ2) = X (−) 1 ( 1ρ1 ) holds, then pim,0 ∼ r m (xdom)m , where (limx→xdom ( 1− x xdom )2 P0(x) = r) is a constant, and xdom is dominant singularity of P0(x), which can be obtained from case 4 of section 3.5. Case 5. If xdom = x3, or xdom = x(−)3 , or xdom = x3 = x (−) 3 holds, then pim,0 ∼ s m−3/2√ pi(xdom)m , where (limx→xdom √ 1− x xdom d ( P0(x) ) dx = s) is a constant, and xdom is the dominant singularity of P0(x), which can be obtained from case 5 of section 3.5. 774.7 Exact Tail Asymptotic for Q0(y) of the Generalized- JSQ In this section we determine the exact tail asymptotic behaviour of pi0,n for Generalized-JSQ with applying the theorem 3.2 to the generating function Q0(y). If the inequalities of lemma 4.1 and two stability conditions, µi > λi + λ for i = 1, 2, hold, then due to the results of the section 3.6, the dominant singularity of Q0(x) is either 1 ρ2 = µ2 λ2 , or Y1( 1ρ2) = Y1(( µ1 + µ2 λ1 + λ2 + λ )2), or y3, the third branch point of h(x, y). Hence, according to section 3.6, we can categorize the exact tail asymptotic behaviour for the Q0(y) of the generalized JSQ into 4 cases: (1) exact geometric decay rate, (2) exact geometric decay rate with factor n−1/2, (3) exact geometric decay rate with factor n−3/2, and (4) exact geometric decay rate with factor n. In the following we will show the details on the cases above. Case 1. If the conditions, |ydom| = 1ρ2 < min {Y1( 1 ρ2 ), y3}, or |ydom| = 1ρ2 = Y1( 1 ρ2 ) = y3, or |ydom| = Y1( 1ρ2 ) < min { 1 ρ2 , y3} hold, then pi0,n ∼ c (ydom)n , where ( lim y→ydom ( 1 − y ydom ) Q0(y) = c) is a constant, and ydom is the dominant singularity of Q0(y), which can be obtained from case 1 of section 3.6. Case 2. If the conditions, |ydom| = 1ρ2 = y3 < Y1( 1 ρ2 ), or |ydom| = Y1( 1ρ2) = y3 < 1 ρ2 hold, then pi0,n ∼ t n−1/2√ pi(ydom)n , 78where ( lim y→ydom √ 1− y ydom Q0(y) = t) is a constant, and ydom is the dominant singularity of Q0(y), which can be obtained from case 2 of section 3.6. Case 3. If the condition |ydom| = y3 < min {Y1( 1ρ2 ), 1 ρ2 } holds, then pi0,n ∼ u n−3/2√ pi(ydom)n , where ( lim y→ydom √ 1− y ydom dQ0(y) dy = u) is a constant, and ydom is the dominant singularity of Q0(y), which can be obtained from case 3 of section 3.6. Case 4. If the condition |ydom| = 1ρ2 = Y1( 1 ρ2 ) < y3 holds, then pi0,n ∼ v n (ydom)n , where ( lim y→ydom ( 1− y ydom )2 Q0(y) = v) is a constant, and ydom is the dominant singularity of Q0(y), which can be obtained from case 4 of section 3.6. Because of the symmetry, the exact tail asymptotics behaviour of pi0,−n for n = 1, 2, 3, ... is similar to pi0,n for n = 1, 2, 3, ..., and so we are not going through the details of the analysis of Q(−)0 (y). 79Chapter 5 Conclusion In this thesis, I extended the idea of a random walk model in the first quadrant by Fayolle, Malyshev, and Iasnogorodski [19], to find the general formulation for the generating functions, and fundamental form for a general random walk model in the first quadrant and fourth quadrant of the plane. In addition, I extended the results of the kernel method in the random walk plane by Li and Zhao [50], to investigate the exact tail asymptotics behaviour of a general random walk model in the first and fourth quadrant of the plane. Moreover, I found the exact tail asymptotics behaviour of the Generalized-JSQ, which is a two-dimensional queueing model in the first and fourth quadrant of the plane by using the kernel method. This model was already studied by Li, Miyazawa, and Zhao [45], and Zhao and Grassmann [75]. But the advantage of the kernel method is that it is a simpler and faster method compared with other methods. Although many studies have been done in the area of random walks, this research field has still a lot of problems to be solved and dis- covered. Here I give some suggestions for future investigations in this area: (1) Studying the exact tail asymptotics behaviour of the generating functions in the three-dimensional random walk model using the kernel method, which has a large application in the manufacturing, communication, and healthcare industry. As an example one can work on parallel queueing problem with three servers. 80(2) Studying the exact tail asymptotics behaviour of the two-dimensional queueing problems modelled in the first and fourth quadrants of the random walk plane with jump steps bounded by two instead of jump steps bounded by one. 81Bibliography [1] Abate, J. and Whitt, W. (1997) Asymptotics for M/G/1 low- priority waiting-time tail probabilities, Queueing Systems, 25, 173-233. [2] Adan, I., Foley, R.D. and McDonald, D.R. (2009) Exact asymptotics for the stationary distribution of a Markov chain: a production model, Queueing Systems, 62, 311-344. [3] IJBF Adan, J. Wessels, and WHM Zijm, Analysis of the Sym- metric Shortest Queue Problem, Stochastic Models, 6:691-713, 1990. [4] Banderier, C., Bousquet-Mlou, M., Denise, A., Flajolet, P., Gardy, D. and Gouyou- Beauchamps, D. (2002). Generating functions for generating trees, (Formal Power Series and Alge- braic Combinatorics, Barcelona, 1999), Discrete Math. 246:1- 3, 29-55. [5] B. Blaszczyszyn, A. Frey and V. Schmidt, Light Traffic Approximation for Markov-Modulated Mulriserver Queues, Stochastic Models, Vol. 11, p. 423-445, 1995. [6] Amarjit Budhiraja, Paul Dupuis, and Vasileios Matoulas, Large Deviations for Infinite Dimensional Stochastic Dynam- ical Systems, Annals of Probability, Vol. 6, No. 4, 1390-1420, 2008. [7] J.P.C. Blanc, A note on waiting times in systems with queues in parallel, Journal of Applied Probability. Vol. 24, p. 540-546, 1987. 82[8] Bender, E. (1974) Asymptotic methods in enumeration, SIAM Review, 16, 485-513. [9] Borovkov, A.A. and Mogul’skii, A.A. (2001) Large deviations for Markov chains in the positive quadrant, Russian Math. Surveys, 56, 803-916. [10] Bousquet-Melou, M. (2005)Walks in the quarter plane: Krew- eras algebraic model, Annals of Applied Probability, 15, 1451- 1491. [11] J. W. Cohen, Analysis of a Two-Dimensional Algebraic Nearest-Neighbour Random Walk (Queue with Paired Ser- vices), Technical Report BS-R9437, CWI, Amsterdam, 1994. [12] Cohen, J. W. and Boxma, O. J. (1983) Boundary Value Prob- lems in Queueing System Analysis, North-Holland, Amster- dam. [13] D. R. Cox and H. D. Miller, The Theory of Stochastic Pro- cesses, John Wiley and Sons Inc., New York 1965, Chapter 2 and 5. [14] Dai, J. and Miyazawa, M. (2010) Reflecting Brownian mo- tion in two dimensions: Exact asymptotics for the stationary distribution, submitted. [15] Robert D. Foley and David R. McDonald, Large Deviation of a Modified Jackson Network: Stability and Rough Asymptotics, The Annals of Applied Probability. Vol. 15, No. 1B, 519C541, 2005. [16] Foley, R.D. and McDonald, R.D. (2001). Join-the-shortest- queue: Stability and exact asymptotics. Ann. Appl. Probab. 11, 569-607. [17] Foley, R.D. and McDonald, D.R. (2001) Join the shortest queue: stability and exact asymptotics, Annals of Applied Probability, 11, 569-607. 83[18] Foley, R.D. and McDonald, R.D. (2005) Bridges and networks: exact asymptotics, Annals of Applied Probability, 15, 542-586. [19] G. Fayolle, R. Iasnogorodski and V. Malyshev, Random Walks in the Quarter Plane, Springer, Berlin, 1999. [20] Fayolle, G. and Iasnogorodski, R. (1979) Two coupled pro- cessors: the reduction to a Riemann- Hilbert problem, Z. Wahrscheinlichkeitsth, 47, 325-351. [21] Fayolle, G., King, P.J.B. and Mitrani, I. (1982) The solution of certain two-dimensional Markov models, Adv. Appl. Prob., 14, 295-308. [22] Flajolet, P. and Odlyzko, A. (1990) Singularity analysis of generating functions, SIAM J. Disc. Math., 3, 216-240. [23] Flajolet, F. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press. [24] Flatto, L. and McKean, H.P. (1977) Two queues in parallel, Comm. Pure Appl. Math., 30, 255-263. [25] Flatto, L. and Hahn, S. (1984) Two parallel queues created by arrivals with two demands I, SIAM J. Appl. Math., 44, 1041-1053. [26] Flatto, L. (1985) Two parallel queues created by arrivals with two demands II, SIAM J. Appl. Math., 45, 861-878. [27] Foss, S., and Chernova, N. (1991). On the ergodicity of multi- channel not fully accessible communication systems. Problems of Information Transmission, 27, 94-99. [28] Foss, S., and Chernova, N. (1998). On the stability of partially accessible queue with state-dependent routing. Queueing Sys- tems, 29, 55-73. [29] Guillemin, F. and Leeuwarden, J. (2009) Rare event asymp- totics for a random walk in the quarter plane, submitted. 84[30] D. P. Gaver, Diffusion Approximation and Models for Certain Congestion Problems, Journal of Applied Probability, Vol. 5, p. 607-1968. [31] Haque, L. (2003) Tail Behaviour for Stationary Distributions for Two-Dimensional Stochastic Mod- els, Ph.D. Thesis, Car- leton University, Ottawa, ON, Canada. [32] Haque, L., Liu, L. and Zhao, Y.Q. (2005) Sucient conditions for a geometric tail in a QBD process with countably many levels and phases, Stochastic Models, 21(1), 77-99. [33] He, Q., Li, H. and Zhao, Y.Q. (2009) Light-tailed behaviour in QBD process with countably many phases, Stochastic Models, 25, 50-75. [34] Halfin, S. (1985). The shortest queue problem. J. Appl. Probab. 22, 865-878. [35] G. Hooghiemstra, M. Keane and S. Van de Ree, Power Se- ries for Stationary Distributions of Coupled Processor Models, SIAM J. Appl. Math. Vol. 48, 1159-1166, 1988. [36] Khanchi, Aziz (2008) State of a network when one node over- loads, Ph.D. Thesis, University of Ottawa. [37] Khanchi, Aziz (2009) Asymptotic hitting distribution for a reflected random walk in the positive quardrant, submitted. [38] D. E. Knuth, The art of computer programming, vol. 1: Fun- damental Algorithms, Addison-Wesley, 1973, Third edition, 1997. [39] Kobayashi, M. and Miyazawa, M. (2010) Tail asymptotics of the stationary distribution of a two dimensional re-acting ran- dom walk with unbounded upward jumps, submitted. [40] Kobayashi, M. and Miyazawa, M. (2011) Tail asymptotics of the stationary distribution of a two dimensional reflecting ran- dom walk with unbounded upward jumps, submitted. 85[41] Kobayashi, M., Miyazawa, M. and Zhao, Y.Q. (2010) Tail asymptotics of the occupation measure for a Markov additive process with an M/G/1-type background process, accepted by Stochastic Models. [42] Kroese, D.P., Scheinhardt, W.R.W. and Taylor, P.G. (2004) Spectral properties of the tandem Jackson network, seen as a quasi-birth-and-death process, Annals of Applied Probability, 14(4), 2057-2089. [43] Kurkova, I.A. and Suhov, Y.M. (2003) Malyshev’s theory and JS-queues. Asymptotics of stationary probabilities, The An- nals of Applied Probability, 13, 1313-1354. [44] Kurkova, I.A. (2001). A load-balanced network with two servers. Queueing Systems, 37, 379-389 [45] Li, L., Miyazawa, M. and Zhao, Y. (2007) Geometric decay in a QBD process with countable background states with appli- cations to a join-the-shortest-queue model, Stochastic Models, 23, 413-438. [46] Li, H. and Zhao, Y.Q. (2005) A retrial queue with a constant retrial rate, server break downs and impatient customers, Stochastic Models, 21, 531-550. [47] Li, H. and Zhao, Y.Q. (2009) Exact tail asymptotics in a prior- ity queue-characterizations of the preemptive model, Queue- ing Systems, 63, 355-381. [48] Li, H. and Zhao, Y.Q. (2011) Exact tail asymptotics in a pri- ority queue—characterizations of the non-preemptive model, Queueing Systems, accepted. [49] Li, H. and Zhao, Y.Q. (2011) Tail asymptotics for a general- ized two demand queueing model-A kernel method, Queueing Systems, accepted. 86[50] Li, H., Yiqiang Q. Zhao, A Kernel Method for Exact Tail Asymptotics-Random Walks in the Quater Plane, submitted. [51] Lieshout, P. and Mandjes, M. (2008) Asymptotic analysis of Levy-driven tandem queues, Queueing Systems, 60, 203-226. [52] Liu, L., Miyazawa, M. and Zhao, Y.Q. (2008) Geometric de- cay in level-expanding QBD models, Annals of Operations Research, 160, 83-98. [53] Mishna, M. (2009) Classifying lattice walks restricted to the quarter plane, Journal of Combinatorial Theory, Series A, 116, 460-477. [54] Miyazawa, M. (2004) The Markov renewal approach to M/G/1 type queues with countably many background states, Queueing Systems, 46, 177-196. [55] Miyazawa, M. (2007) Doubly QBD process and a solution to the tail decay rate problem, in Proceedings of the Second Asia- Pacific Symposium on Queueing Theory and Network Appli- cations, Kobe, Japan. [56] Miyazawa, M. (2009) Two sided DQBD process and solutions to the tail decay rate problem and their applications to the generalized join shortest queue, in Advances in Queueing The- ory and Network Applications, edited by W. Yue, Y. Taka- hashi and H. Takaki, 3-33, Springer, New York. [57] Miyazawa, M. and Zhao, Y.Q. (2004) The stationary tail asymptotics in the G/I/G1 type queue with countably many background states, Adv. in Appl. Probab., 36(4), 1231-1251. [58] Morrison, J.A. (2007) Processor sharing for two queues with vastly different rates, Queueing Systems, 57, 19-28. [59] Motyer, Allan J. and Taylor, Peter G. (2006) Decay rates for quasi-birth-and-death process with countably many phases 87and tri-diagonal block generators, Advances in Applied Prob- ability, 38, 522-544. [60] V. A. Malyshev, Random Walks. The Wiener-Hopf Equations in Quadrant of the Plane. Galois Automorphisms. Moscow Univ., Press, 1970. (In Russian) [61] V. A. Malyshev, Analytic Method in the Theory of Two- Dimensional Random Walks, Sib, Math. J. 13 1314-1327, 1972. [62] V. A. Malyshev, Asymptotic Behaviour of Stationary Prob- abilities for Two-Dimensional Positive Random Walks, Sib. Math. J. 14 156-169, 1973. [63] Mitzenmacher, M.D. (1996). The power of two choices in ran- domized load balancing. PhD thesis. University of California at Berkeley. [64] Raschel, K. (2010) Green functions and Martin compactifica- tion for killed random walks related to SU(3), Elect. Comm. in Probab., 15, 176-190. [65] Sheldon M. Ross, Introduction to Probability Models (8th Edition), 2003. [66] Sharifnia, A. (1997). Instability of the join-the-shortest-queue and FCFS policies in queueing systems and their stabilization. Operations Research, 45, 309-314. [67] Suhov, Yu.M., and Vvedenskaya, N.D. (2002). Fast Jackson networks with dynamic routing. Probl. Inform. Transmission, 38, 136-159. [68] Takahashi, Y., Fujimoto, K. and Makimoto, N. (2001) Ge- ometric decay of the steady-state probabilities in a quasi- birth-and-death process with a countable number of phases, Stochastic Models, 17(1), 1-24. 88[69] Tandra, R., Hemachandra, N. and Manjunath, D. (2004). Job minimum cost queue for multiclass customers. Stability and Performance bounds. Probability in the Engineering and in- formational Sciences, 18, 445-472. [70] Tang, J. and Zhao, Y.Q. (2008) Stationary tail asymptotics of a tandem queue with feedback, Annals of Operations Re- search, 160, 173-189. [71] Vvedenskaya, N.D. and Suhov, Yu.M. (2004). Functional equations in asymptotic problems of queueing theory. Jour- nal of Mathematical Sciences (N.Y.), 120, 1255-1276. 22 ABRAMOV. [72] Vvedenskaya, N.D., Dobrushin, R.L., and Karpelevich, F.I. (1996). A queueing system with selection the shortest of two queues: An asymptotic approach. Probl. Inform. Transmis- sion, 32, 15-27. [73] Winston, W. (1977). Optimality of the shortest line discipline. J. Appl. Probab. 14, 181-189. [74] Wright, P. (1992) Two parallel processors with coupled inputs, Adv. Appl. Prob., 24, 986-1007. [75] Yiqiang Zhao, Winfried K. Grassmann. 1995. Queueing Anal- ysis of a Jockeying Model. Operations Research 43, 520-529. 89
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- The exact tail asymptotics behaviour of the joint stationary...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
The exact tail asymptotics behaviour of the joint stationary distributions of the generalized join the.. Zafari, Zafar 2012
pdf
Page Metadata
Item Metadata
Title | The exact tail asymptotics behaviour of the joint stationary distributions of the generalized join the shortest queueing model |
Creator |
Zafari, Zafar |
Publisher | University of British Columbia |
Date | 2012 |
Date Issued | 2012-05-16 |
Description | Parallel queueing networks have advantage over single server queueing networks, because when some servers simultaneously serve the customers in the line, the efficiency increases. Therefore, in the real world parallel queueing servers such as computer networks and multiple parallel processors, have become common. Since then many scientists have been studying the analysis of parallel queueing networks to give the exact practical models for the real world queueing problems. One of the topics in parallel queueing networks is the two-dimensional random walk, which recently have been studied by many scientists. The formulation for a random walk model in the first quadrant has been already studied by Fayolle, Malyshev and Iasnogorodski [19]. In this thesis I extend the formulation of a general random walk model to the half plane, including the first and fourth quadrants, and by using kernel method and Tauberian-like Theorem I investigate the exact tail asymptotic behaviour of the joint stationary distribution of the generating functions. In addition, I apply the results of the formulation of a general random walk model in the half plane to the Generalized-JSQ model, which is a queueing system with two parallel servers that have three streams of arrivals, two of which are dedicated to each servers, and the third one joins the shorter queue. Suppose that arrivals are independent Poisson processes, and service times have identical exponential distributions. Although this queueing model has been already studied by Zhao and Grassmann [75], and M. Miyazawa, [56], in this thesis I will use a different method named kernel method to investigate the exact tail asymptotic behaviour of the generating functions. The kernel method is simpler and faster than other methods, since in this method we are not dealing with the explicit expressions in terms of generating functions, but we only discuss the dominant singularity and its location. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Collection |
Electronic Theses and Dissertations (ETDs) 2008+ |
Date Available | 2012-05-16 |
Provider | Vancouver : University of British Columbia Library |
DOI | 10.14288/1.0072787 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Irving K. Barber School of Arts and Sciences (Okanagan) |
Degree Grantor | University of British Columbia |
Graduation Date | 2012-11 |
Campus |
UBCO |
Scholarly Level | Graduate |
URI | http://hdl.handle.net/2429/42327 |
Aggregated Source Repository | DSpace |
Download
- Media
- [if-you-see-this-DO-NOT-CLICK]
- ubc_2012_fall_zafari_zafar.pdf [ 426.75kB ]
- Metadata
- JSON: 1.0072787.json
- JSON-LD: 1.0072787+ld.json
- RDF/XML (Pretty): 1.0072787.xml
- RDF/JSON: 1.0072787+rdf.json
- Turtle: 1.0072787+rdf-turtle.txt
- N-Triples: 1.0072787+rdf-ntriples.txt
- Original Record: 1.0072787 +original-record.json
- Full Text
- 1.0072787.txt
- Citation
- 1.0072787.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Country | Views | Downloads |
---|---|---|
United States | 21 | 5 |
Canada | 8 | 2 |
China | 7 | 0 |
Austria | 5 | 0 |
France | 4 | 0 |
Germany | 3 | 8 |
Russia | 2 | 0 |
United Kingdom | 2 | 0 |
City | Views | Downloads |
---|---|---|
Ashburn | 21 | 0 |
Unknown | 11 | 8 |
Shenzhen | 6 | 0 |
Vancouver | 6 | 0 |
Innsbruck | 5 | 0 |
Kelowna | 2 | 2 |
Beijing | 1 | 0 |
{[{ mDataHeader[type] }]} | {[{ month[type] }]} | {[{ tData[type] }]} |
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0072787/manifest