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.
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.