Menu
Consider a queue of \(N\) customers waiting to purchase an item that costs \(1\) dollar. Of them, \(m\) customers have a \(1\)-dollar bill and \(n\) customers have only a \((1+\mu)\) dollar bill, where \(\mu\) is a positive integer. The latter need to get change in the amount of \(\mu\) dollars. If at the time of their service, the cashier has less than \(\mu\) \(1\)-dollar bills, they have to wait for change according to some queue discipline. It is assumed that the cashier has no initial change, and that all the queue arrangements are equi-probable. Using transformations of lattice graphs, we derive the probability distribution of the number of customers who will have to wait for change under a queue discipline that corresponds to the ballot problem. Limiting results and other applications are also given.