6

Given an empty system at time $0$ the number of departures by time $t$ is a non homogeneous Poisson process with rate $$\lambda(t)=\lambda\int^{t}_{0}G(y)dy$$ and so the probability of no departures by time $t$ is given by: $$exp(-\lambda\int^{t}_{0}G(y)dy)$$ now if we set time $0$ to be time of the first arrival and let $G_1$ be the service time of the ...


5

More generally... one may want to keep in mind that Markov chains (in discrete time) and Markov processes (in continuous time) are different (although related) objects. 1. A Markov chain $(X_n)$, indexed by $n$ integer, is described by a transition matrix $P$, such that, for every states $(x,y)$ and every $n$, $$\Pr(X_{n+1}=y\mid X_n=x)=P_{xy}.$$ Thus: ...


5

The moment-generating function of a random variable X is $$w_{X}(s)=\mathbb{E} \!\left[e^{sX}\right]= \int_0^{\infty}p(x) e^{sx}dx$$ for $s\in \mathbb{R}$, if there is a probability density function $p$ on the nonnegative real line. The Laplace transform of a distribution with probability density function $p$ on the nonnegative real line is $${\mathcal{L}}\{...


4

HINT: In the skeleton $_J_J_J_J_J_J_J_J_$, where each J is a Jovian, the $5$ Martians must occupy $5$ different blanks.


4

First-come-first-served ensures that provided that the time between served customers is bounded, any customer who enters the queue will within a worst-case wait time that can be determined based upon the number of preceding customers. Even if the time between customers is bounded only probabilistically, the wait time will still have a reasonable ...


4

Queuing theory is primarily concerned with processes that have variability in arrival of jobs into the system. For example, jobs can be people needing service. The time taken to service these jobs is also generally variable. The result is congestion or waiting line. This can be measured by the average number of jobs in the queue and by the average ...


4

The following article considers the application of Rouché's theorem in queueing theory. Adan, van Leeuwaarden and Winands. On the application of Rouché's theorem in queueing theory For something I can really help you with if you have questions, see the proof of Lemma 4.5 in the following paper. Selen, Adan and van Leeuwaarden. Product-form solutions for ...


4

Yes. No, this means that the probability that the queue is very long goes to one, for every quantification of "very long". This happens when the queue is either null recurrent, see 3., or transient, see 4. No, this means that "this" (whatever "this" is) will happen again, but after a (finite) time whose expectation is infinite. For example, to come back to $...


4

Hint: By defining $\phi_n = \sum_{i=0}^n \pi_i$, we may express $\pi_{n+1}$ and $\phi_{n+1}$ as linear combinations of $\pi_n$ and $\phi_n$ plus constants, giving a first-order linear matrix difference equation. EDIT: The equation we end up with is of the form $$x_{(n+1)} = Ax_{(n)}+b$$ where the vectors $x_{(n)}=\begin{pmatrix}\pi_n \\ \phi_n\end{pmatrix}\...


4

I am canoeing up a river at a speed (relative to the water) of $A$ miles per hour, and the current in the other direction is $B$ miles per hour. If $A\gt B$, my speed relative to the shore line is $A-B$, so it will take me $\frac{1}{A-B}$ hours to travel $1$ mile. Or if you prefer I am running up a down escalator.


4

So, to begin with, your expectations are shifted over by one: $\frac{1}{\mu + \lambda_w}$ is the expected waiting time, given that a customer doesn't leave, when there were no other customers in line. $\frac{1}{\mu + \lambda_w} + \frac{1}{\mu + 2\lambda_w}$ is the expected waiting time, given that a customer doesn't leave, when there was one other customer ...


4

The probability to have more than one arrival is then, assuming a rate $\lambda>0$ (seen as a constant), $$\begin{align} \mathbb{P}\{ N(t,t+\varepsilon] > 1 \} &= 1 - \mathbb{P}\{ N(t,t+\varepsilon] = 0 \} - \mathbb{P}\{ N(t,t+\varepsilon] = 1 \} \\ &= 1 - e^{-\lambda \varepsilon} - e^{-\lambda\varepsilon}(\lambda\varepsilon) \\ &= \frac{\...


4

The period $\ d(i)\ $ of a state $\ i\ $ is not the shortest length of tine it takes to return to the state, but the gcd of all the times it can take to return to the state. In your example, if you start from state $2$ you can reach it again after $\ 4,6,8,\dots\ $ steps. That is $\ P^n(2,2)>0\ $ for any $\ n\ $ of the form $\ 4+2r\ $ where $\ r\ $ is ...


3

The probability of a tie is $$P_{tie}=\frac{\binom{50}{25}}{2^{50}}$$ thus the probability that neither group reaches a tie is $$P = (1-P_{tie})^2$$ (where all events are assumed to be independent). This gives $$P = \left(1 - \frac{\binom{50}{25}}{2^{50}}\right)^2 \approx \left(1 - \frac{1}{5\sqrt{\pi}}\right)^2\approx 0.79$$ where in the second step we ...


3

The average queueing delay for an M/M/1 queue is difficult to define when $\lambda=\mu$ since the length of the queue has no stationary distribution in this case. Recall that when $\lambda\lt\mu$, there exists a stationary distribution $\pi$ for the length of the queue, that the distribution of the length of the queue converges to $\pi$ for every initial ...


3

In the deterministic traffic arrival model, jobs arrive at fixed instants, for example every 10 seconds. There is no randomness in the model, jobs arrive exactly once every 10 seconds. If you have a model with deterministic services then this means the model takes a fixed amount of time to serve every job, again no randomness. In contrast, in the M models ...


3

Yes, you've got the right idea. I'm assuming you intend the $B_i$ to be iid $$ \begin{aligned}B^*(s) &= \mathbb E[ e^{sB} ]\\ &= \mathbb E[\mathbb E[e^{sB}|S]]\\ &= \mathbb E[\mathbb E[ \mathbb E[e^{s(S+\sum_{j=1}^Z B_j)}|S,Z]|S]]\\ &= \mathbb E[ e^{sS} \mathbb E[ \mathbb E[ e^{sB}|S,Z]^Z|S]]\\ &= \mathbb E[e^{sS}G(B^*(s))] \end{aligned}$...


3

The transition rate matrix is another name for the generator matrix for a continuous time markov chain. A transition matrix is for a discrete time markov chain. $M$ would be for a continuous time markov chain (the underlying process for the queue is based on Poisson processes) while $T$ would be for a discrete time markov chain (the underlying process ...


3

More generally. Let $(X_n)_{n\geqslant0}$ be defined by $X_{n+1}=G(X_n,Z_{n+1})$ for every $n\geqslant0$, where $(Z_n)_{n\geqslant1}$ is i.i.d. and independent of $X_0$. Then $(X_n)_{n\geqslant0}$ is a Markov chain. If need be, one can write down the transition probability of $(X_n)_{n\geqslant0}$ as $$P(X_{n+1}\in A\mid (X_k)_{0\leqslant k\leqslant n})=...


3

Consider a "renewal time" as a time when the number of customers goes from $1$ to $0$. After a renewal time, we wait Exponential($\lambda$) time in each of the states $0, 1_u, \ldots, (n-1)_u$: a total expected time $n/ \lambda$ of which an expected time $1/\lambda$ is spent in state $0$. Then the server becomes active, and we are in a "normal" M/M/1 queue ...


3

In an $M/M/1/K$ process, where $P_n$ is the proportion of time $n$ people are queuing or being served and $0 \le n \le K$, you can reach balance with $$P_n=\left(\dfrac{\lambda}{\mu}\right)^n P_0 $$ and, if you write $\rho = \frac{\lambda}{\mu}$ as the ratio of the arrival and service rates, then this gives $P_n=\rho^n P_0$. Since $\sum_{n=0}^K P_n=1$, ...


3

The OFRBG comment is the thing (we know the long term average departure rate must be less than or equal to the long term average arrival rate). But here is some more intuition: Consider an $M/M/1$ queue with $0 < \lambda < \mu$. Define $\rho = \lambda /\mu$. The steady state distribution is $p_k = (1-\rho)\rho^k$ for $k \in \{0, 1, 2, \ldots\}$, ...


3

Let $A$ and $B$ denote the number of requests in $(0,T]$ from clients $a$ and $b$ relatively. Then, $A$ and $B$ are Poisson random variables with parameters $\lambda_aT$ and $\lambda_bT$ respectively, and you have declared them to be independent random variables. Thus, $C = A+B$, the total number of requests received during $(0,T]$ is a Poisson random ...


3

The $\lambda$ and $\mu$ have nothing to do with the exponential distribution. It just turns out that these two parameters are most often used as the parameters of the the exponentially distributed inter-arrival time and service time. Let $A$ be the inter-arrival time and let $B$ be the service time in the $G/G/1$ queue. Then the mean inter-arrival time is $\...


3

The two systems are totally separated, as you put it. So the stationary probability \begin{equation} p(i,j) := \lim_{t \to \infty} \mathbb{P}(Z_1(t) = i, ~ Z_2(t) = j) \end{equation} can be written in product form as $p(i,j) = p_1(i) \, p_2(j)$ with \begin{equation} p_n(i) = (1 - \nu/\mu) (\nu/\mu)^i, \quad n = 1,2. \end{equation}


3

For a simpler scenario without effective incoming rate, suppose there is a queue where customers arrive at rate $\lambda$ and they go into either of two lines with equal probability $\dfrac{1}{2}$. There is one server who serves the customer at rate $\lambda$. Regardless of the number of different lines, the one server can only serve one customer at a time ...


3

What do you mean by "inter arrival rate"? If you mean that inter-arrival times are uniformly distributed, then the answer is no. The arrival process is not Poisson and the queue is a G/M/1. The arrival process is only Poisson if the inter-arrival times follow an exponential distribution.


3

By symmetry, your expression is equal to $$ \sum_{A_k} a_{i_1} \dots a_{i_k}, $$ where $A_k = \{(i_1,\dots,i_k): i_1\le M, i_1+i_2\le 2M,\dots,i_1+\dots + i_k\le kM\}$. This is nothing else but the probability that $S_1\le 0,S_2\le 0,\dots,S_n\le 0$, where $S_k = Y_1+\dots + Y_k$, $Y_k = X_k - M$, $X_k$ are iid $\mathrm{Poi}(N)$. So the probability you are ...


3

Let $\{t_1, t_2, t_3, ...\}$ be arrival times of a Poisson process of rate $\lambda>0$. Let $X(t)$ be a real-valued random process that possibly depends (causally) on the Poisson process. Assume that $\overline{X}$ is a real number such that: $$ \lim_{T\rightarrow\infty} \frac{1}{T}\int_0^T X(t)dt = \overline{X} \quad (\mbox{ with prob 1}) $$ The PASTA ...


3

Assuming you are referring to the steady state of the system, we have the balance equations \begin{align} \lambda\pi_0 &= \mu\pi_1\\ \lambda\pi_1 &= \mu\pi_2, \end{align} from which $\pi_1 = \frac\lambda\mu \pi_0$ and $\pi_2 = \left(\frac\lambda\mu\right)^2\pi_0$. Let $\rho = \frac\lambda\mu$. From $\pi_0+\pi_1+\pi_2=1$ we have $$ \pi_0(1 + \rho + \...


Only top voted, non community-wiki answers of a minimum length are eligible