0
$\begingroup$

I'm trying to sketch the Markov chain for a Random Early Discard queueing policy where customers arrive to the queue of infinite size according to a Poisson process with rate $\lambda$. Customers that arrive are entered into the queue with probability $\alpha_{n} = \frac{1}{n+1}$ and are blocked from the queue with rate $1-\alpha_{n}$. The service time is exponentially distributed with mean $\frac{1}{\mu}$.

I think the jumps from state 0 -> 1 -> 2 -> ... -> n -> n+1 should be $\alpha_{n}\lambda$ and arrows going to the same state, say 0 to 0, should be $(1-\alpha_{n})\lambda$, and arrows going successively backward between states would be $\mu$. Is this correct or am I misunderstanding how this works? I learned some introductory stuff about Markov chains in probability, but the arrows were always labeled as probabilities that added to 1 instead of rates of arrivals per second.

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Your thoughts are correct, although the notion of $n \to n$ transition rate is superfluous for the continuous time Markov process. One could think of a discrete time-step Markov chain, in which case the "arrows" probabilities do need to add to $1$, but for this continuous-time model, the concept of probability rates is the applicable one.

One thing to point out: Since the rates depend on the size of the queue, your usual queueing theory results do not hold. In particular, for $\lambda > \mu$ an ordinary queue ($\forall n : \alpha_n = 1$) almost surely grows to infinity; but for your example $\alpha_n$ the queue will not grow indefinitely; its asymptotic distribution for large $t$ is largest near $$ \frac{1}{n+1}\lambda = \mu \implies n = \frac{\lambda}{\mu}-1 $$ The actual asymptotic distribution is interesting and non-trivial.

$\endgroup$
4
  • $\begingroup$ So for the balance equations, for instance looking at the rate in = rate out for state 1, why is it that some authors include all the ins and outs, while some only include the in's and outs going to/from the s+1 state? $\endgroup$
    – Austin
    Feb 21, 2016 at 18:58
  • $\begingroup$ Some authors have $n=0$ as the lowest state, in which case you need to do all the ins and outs from state $1$ (but not from state $0$. Some have $n=1$ as the lowest state, in which case, you only need the ins and outs to state $2$. $\endgroup$
    – Mark Fischler
    Feb 22, 2016 at 1:05
  • $\begingroup$ But for two markov chains that both have an n=0 state, Ive seen one author for the S1 balance equation only do the arrows going to and from S2, whereas another author for S1 balance equation included the arrows to and from S2 as well as the arrows to and from S0. I was wondering if there's some property I was unaware of that allows you to not include the S0 arrows connecting to S1 while doing the S1 balance equation. $\endgroup$
    – Austin
    Feb 22, 2016 at 1:09
  • 1
    $\begingroup$ @Larry The rate going into and coming out of a set of states is equal. One author probably takes the set $\{i\}$ and then computes all the rates going into the state (from $i - 1$ and from $i + 1$) and out of that state (from $i$ to all other states). On the other hand, if you take the set of states to be $\{0,1,\ldots,i\}$, then the rate going into that set of states is only from state $i + 1$ and the rate of leaving that set of states is from $i$ to $i + 1$. $\endgroup$
    – Ritz
    Feb 26, 2016 at 8:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .