This is the exact question text:

$2n$ children are waiting in a queue for movie ticket. Tickets are priced at a quarter each. Each child pays for the ticket either with a quarter or with half dollar coin. If before starting any transaction the cashier had $2 k$ quarters, what is the probability that no one will have to wait for change?

It is basically a simple random walk problem with shifted origin. If I can compute the probability of reaching 0 for the first time at $i^{\;th}$ step of the walk, I am done. Does anyone know the formula?

Also the problem is given in the basic combinatorics chapter, so if anyone can solve it without applying any random walk formula, it will be the best.


closed as off-topic by Juho Kokkala, Michael Chernick, Peter Flom Jun 10 '18 at 11:38

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Self-study questions (including textbook exercises, old exam papers, and homework) that seek to understand the concepts are welcome, but those that demand a solution need to indicate clearly at what step help or advice are needed. For help writing a good self-study question, please visit the meta pages." – Juho Kokkala, Michael Chernick, Peter Flom
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ You should add the [self-study] tag! Also, we really need the probability that a child pays with a quarter. $\endgroup$ – kjetil b halvorsen Jun 9 '18 at 11:23

Since this looks like self-study I will only give some ideas. First notation. $p$ is the probability that a child pays with a quarter( maybe $p=1/2$ was intended?). Let $X_i$ be the number of quarters the cashier has after child $i$ has paid, $X_0=2 k$. Then, $X_0, X_1, X_2, \dotsc, X_{2n}$ is a Markov chain. To assure that this is defined at all times, we postulate that if the cashier has no quarters left, he pais preliminary with a "debt certificate" and count that a a negative quarter. So we are interested in the probability that $$ \min(X_0, X_1, \dotsc, X_{2n}) \ge 0 $$
If we now reformulate, declaring $-1$ to be an absorbing state, and stop the chain if it is absorbed, then we are interested in the probability that the chain is never absorbed (before or at time $2n$). Some post which might be of help is Given two absorbing Markov chains, what is the probability that one will terminate before the other?, Expected number of times you spent in a state of an absorbing markov chain, given the eventual absorbing state


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