2

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.

kjetil b halvorsen
  • 63,378
  • 26
  • 142
  • 467
Nilabja Ray
  • 61
  • 1

1 Answers1

1

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

kjetil b halvorsen
  • 63,378
  • 26
  • 142
  • 467