PC Seminar: Alice, Bob, and random coin tosses

Abstract: There are some surprises when looking for patterns in a (potentially infinite) random string of Heads and Tails (or 0 and 1). Think of the string as generated by an infinite sequence of coin tosses.

In one old problem a string A of length k is fixed. The probability that it occurs at a given position is obviously 2^{-k}, but what is the expected time until its first appearance? Perhaps surprisingly, this depends on the string A; it is 2^k for some strings but not for all.

Another well-known problem is Penney Ante. There are two players Alice and Bob having different strings A and B of the same length. The player that first sees his/her string wins. Again, the probability of winning depends on the strings and is in general not 1/2. Moreover, there is no uniformly best string; any string of length >2 is beaten by some other string of the same length.

I will mainly talk about a new version, posed by Daniel Litt in 2024. Here the number n of coin flips is fixed. Alice and Bob each score a point when their string occurs. Who is more likely to win? For large n, the probability of winning is close to 1/2, but is it larger or smaller, and by how much?

The talk is based on the paper "The generalized Alice HH vs Bob HT problem", joint work with Mihai Nica and Simon Segert, J. Theoretical Probability (2025). It uses methods from a PhD thesis from our department by Carl-Gustav Esseen (1945).

This is a seminar in our seminar series on Probability and Combinatorics (PC).