3
$\begingroup$

There are $K$ checkout counters in the mall, and there are $N$ shoppers in the queue waiting for a checkout counter. Initially all counters are empty. Whenever a counter is empty, the next shopper in queue will go ahead and use it.

Every shopper will take a random amount of time to finish their checkout process. The amount of time taken is a random integer between $1$ and $M$. The amount of time taken by different shoppers is independent of each other. The first $K$ shoppers in the queue will have to wait for $0$ time, since there are $K$ empty counters initially.

Calculate the expected amount of time each shopper in the queue will have to wait.

So far, I've been able to derive a formula using the three parameters for the random variable of the $K+1$th shopper (the minimum of $K$ discrete uniform random variables $U(1,M)$), but I can't think of any way how to generalise this for all customers.

This question is taken from hacker-rank and I've spent a significant amount of time trying to solve it successfully, and although my solution works for some cases, I am very much more interested in the general solution. I am not interested in the code for this, but rather an expression for each random variable $X_i$ for $i \in [1..N]$ i.e. the distribution of time each customer has to wait.

$\endgroup$
1
$\begingroup$

The hacker-rank formulation has the additional constraint $M,K\le5$. That makes it feasible to model this as a Markov chain with $(M+1)^K$ states. You can augment the distribution vector by an expected time component that keeps track of the expected time so far. As an example, with $M=K=2$ you'd have the states $(i,j)$ with $0\le i,j\le2$ that reflect the times that the two shoppers currently at the counters will take to finish their checkout process. The initial state is $(0,0)$, so you'd start out with the vector $(1,0,0,0,0,0,0,0,0,0)$ (where the last component is the expected time component). The transition matrix would be

$$ \pmatrix{ 0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0\\ \frac12&0&0&0&\frac12&0&0&0&\frac12&0\\ 0&\frac12&0&\frac12&0&\frac12&0&\frac12&0&0\\ 0&0&\frac12&\frac12&0&0&0&\frac12&0&0\\ \frac12&0&0&0&\frac12&0&0&0&\frac12&0\\ 0&\frac12&0&0&0&\frac12&\frac12&0&0&0\\ 0&0&\frac12&0&0&0&\frac12&0&0&0\\ 0&0&0&0&1&1&0&1&2&1\\ }\;, $$

where the states are ordered $(0,0)$, $(0,1)$, $(0,2)$, $(1,0)$, etc., and I arbitrarily filled the first counter if both counters become available simultaneously. Each application of the transition matrix corresponds to one customer going to a counter. After $m$ applications, the last component of the vector will contain the expected time the $m$-th customer has to wait in the queue (not including the expected serving time $(M+1)/2$ at the counter). You can compute the $N$ applications individually to get the expected waiting time for each customer (which is feasible since $N\le3000$), or you can use the singular value decomposition of the transition matrix to calculate the expected waiting time of some particular customer.

As an optimisation, you can merge all states that differ only by a permutation of the counters, but given the constraints on the parameters, that's probably not necessary.

$\endgroup$
  • $\begingroup$ Why is the matrix 10x10 in this case ( rather than 9x9 if we have $2^3+1$)? I presume the 1/2 is because we have $K=2$ in this case. $\endgroup$ – baibo Apr 2 '16 at 22:43
  • $\begingroup$ @bvborisov: Sorry, it should have been $(M+1)^K$, not $M^{K+1}$; I've corrected it. ($M+1$ for the values from $0$ to $M$.) No, the $\frac12$ is because $M=2$, so the next customer can come to the counter with a service time of $1$ or $2$ with equal probability. $\endgroup$ – joriki Apr 2 '16 at 22:45
  • $\begingroup$ Sorry for asking another question, but how did you fill up the transition matrix? I've done Markov Processes for continuous times for a course at university and I remember that diagonal entries had to be equal to the negative sum of all other entries on the same row link . Also, how do we do the mapping between $(0,0)$ and $(1,0,0,0,0,0,0,0,0,0)$ i.e. between the global states and the vectors? $\endgroup$ – baibo Apr 3 '16 at 12:52
  • $\begingroup$ @bvborisov: That document talks about infinitesimal generator matrices, a different setting. The transition matrix of a discrete Markov process is a stochastic matrix. I should have said that I wrote the matrix that you'd need to apply from the left to a column vector, even though I wrote the state vector as a row vector; sorry about that. That's why it's left stochastic. Equivalently you can multiply the column state vector from the right by its transpose, which is right stochastic. $\endgroup$ – joriki Apr 3 '16 at 12:59
  • $\begingroup$ @bvborisov: I set up the matrix by going through and figuring out which states a state can transition to. For instance, from $(1,2)$, it takes $1$ unit of time until a counter frees up, so there's a $1$ in the last row of the corresponding column (the sixth). Then we've reached $(0,1)$ and fill up the $0$ with a new customer, who has probability $\frac12$ each of taking $1$ or $2$ units of time to be served. Thus with probability $\frac12$ the state transitions to $(1,1)$ or $(2,1)$, corresponding to the fifth and eighth rows, respectively. $\endgroup$ – joriki Apr 3 '16 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.