Dear Tarra

you have posted a very interesting question. The best framework to look into is Bernoulli Trials and ultimately Random Walks.

The problem is very close to the one attributed to Banach: a matematician picks randomly one of the two matchboxes that in the beginning contained 50 matches each. Sooner or later he will produces from his pocket an empty matchbox. Find the probability that at this moment the other box will contain r matches.

The problem is described in W.Feller An Introduction to Probability Theory and its Application, v1, J.Wiley & Sons, NY, second edition, Chapter VI as an example. Chapter III of the book contains a very relevant material on Random Walks.

The difference between yours and Banach's is that you check emptiness of a box immediately after removing a match whereas Banach checks it before retrieving a match. Thus starting with 3 matches the sequence (in your notations)

yyyx

would be illegitimate for your problem but quite acceptable to Banach.

You must be able to get your probabilities as alternating series of Banach's as done with a series of telescoping sets.

The problem falls into the Random Walk framework the following way. Let A and B be the number of sticks in the two packs. Consider f=A-B. In the beginning f=0. On every step, f either increases or decreases by 1. You can represent this graphically as a broken line consisting of straight line segments with slopes of 45^o and -45^o. The question is "In how many ways one can get from the point (0,0) to the point (2n-r,r), where n is the starting amount of matches (sticks) in a box (pack)?"

As a variation, you may express interest only in the walks in which r is attained the very first time or the line stays at all times above the time axis. Banach would not care but you are interested in the walks that do not along the way spuriously solve your problem for any other (larger) r.

In addition to Feller's you may want to look into

1. Graham, Knuth, Patashnick, Concrete Mathematics, Addison-Wesley, 1994 (Chapters 7 (Generating Functions) and 8 (Discrete Probability)).
2. M.Gardner, Time Travel and ..., W.H.Freeman & Co., 1988, Chapter 20 (Catalan Numbers).

I would be very grateful if you keep me informed of your progress.

Sincerely,
Alexander

Copyright © 1996-2008 Alexander Bogomolny

29706376