*************************************************************************

                Department of Mathematical Sciences
                   The Johns Hopkins University

                             SEMINAR

*************************************************************************

Jim Fill                                               March 14, 2002
Department of Mathematical Sciences                    304 Whitehall Hall 
The Johns Hopkins University                           Refreshments: 3:30 PM 
                                                       Seminar: 4:00 PM 

*************************************************************************

       KNOCKING PROBABILITY DOWN TO A THIRD-GRADER'S LEVEL


*************************************************************************

                               ABSTRACT

A simple game called "Knock 'em Down" can be played between two
players as follows.  There are  k  labeled bins, and each player is
given  n  tokens to be allocated freely (once and for all) among
these bins.  Independently repeated draws are then made from a fixed
probability distribution  p = (p_1, ..., p_k)  on the bins; when a
bin is drawn, each player may remove one of her or his tokens, if
any, from that bin.  The object of the game is to be the first to
remove all of one's tokens from the bins.  We present an analysis of
the game for fixed  p, asymptotically as  n  becomes large; despite
the game's simple nature, there are some subtleties in its analysis.
We will discuss at least the following two variants: the payoff to
the winner is (i) the difference in the numbers of draws required to
remove the player's tokens; or (ii) one monetary unit (with no money
exchanged when the players tie).  Our analysis both builds upon and
diverges from earlier analysis of Arthur T. Benjamin, Matthew T.
Fluet, and Mark L. Huber.

Knock 'em Down was played on November 29, 2001 in Jonah Scheinerman's
third-grade math class.  An email message on that date from Ed
Scheinerman to me about the game was the impetus for the research I
will describe.  The research involves ideas from probability, game
theory, optimization, combinatorics, and statistics.

(This is joint work with David Bruce Wilson.)