Identifying the deviator.

Abstract: 

Alice and Bob control a random walk: alternately, each of them flips a fair coin, is supposed to report the outcome, and the random work advances according to the report. Suppose that the random walk did not return to the origin infinitely often. We suspect that one of Alice and Bob misreported the outcomes of her or his coin. Can we identify the deviator?

More generally, several players are supposed to follow a prescribed profile of strategies (e,g, select each of Right and Left with probability 1/2). If they follow this profile, they will reach a given target (e.g., the random walk returns to the origin infinitely often). We show that if the target is not reached because some player deviates, then an outside observer can identify the deviator. We also construct identification methods in two nontrivial cases.

Posted on Dec 1, 2025 in ACGO, Seminars