Anne Condon (University of British Columbia)
Arthur and Merlin take a walk
Arthur-Merlin games model situations in which Merlin must devise a strategy to win against Arthur, who merely flips a coin to determine his moves. In
this talk, we consider the following very simple example of such a game. Merlin is placed at the left end of a finite set of points on a line, and will perform
a random walk on the points. A finite set U of probabilities is given. Before starting, Merlin can choose, for each point r, a probability p(r) from the set U.
The mapping p from the set of points on the line to U is called Merlin's strategy; if there are k points, then Merlin has |U|^k possible strategies. Once the
strategy is fixed, the walk proceeds as follows. When Merlin is on point r, Arthur flips a coin which produces heads with probability p(r). Then Merlin
moves left if the outcome is heads and moves right otherwise. Let's suppose that Merlin's goal is to fall off the left end of the line before falling off the
right end. Typically, one is interested in knowing what strategy Merlin would use to maximize his probability of success. If, for example, U = {1/3, 3/4},
the answer is easily found: obviously Merlin would choose to move left from every point with probability 3/4, and a gambler's ruin analysis would reveal
the probability of success. The question we ask is different. We consider the set S U(n) of Merlin's success probabilities, taken over all possible strategies
on a line with n points. We ask: does S U(n) tend to a limit (suitably defined for sets) as n goes to infinity? In the talk we describe the answer to this
question, motivate why we are interested in this problem, and introduce several related open problems.
This is joint work with Michael Saks and Joseph
Wong.