Deeper Dive
My project, “On Group-Theoretic Extensions of Penney’s Game,” is on a system known as Penney’s game. Two players bet on two words consisting of Hs and Ts, then flip a coin to see which word appears first. For instance, if Alice bets on THH, Bob bets on HHH, and the coin flips HTTHTHTTHH, then Alice wins. Counterintuitively, the odds of winning are not always 50-50; for instance, in THH versus HHH, Alice wins 87.5% of the time (try it!). The game is related to the study of word correlation, which measures the similarity between two words. My project generalizes the game by replacing words THH with patterns, which are collections of similar words like {THH, HTT}. This does two things: it dramatically changes the structure of the game, and it connects the game to other seemingly unrelated problems in representation theory, unavoidability, and analytic combinatorics.
The main bottleneck of the project was characterizing how word correlation generalizes for patterns. Instead of analyzing the similarity between two words, I had to analyze the similarity between each pair of words among two sets. There were a lot of moving parts! Programming and writing out examples helped a ton, and ultimately, I found that the underlying structure of the alphabet has a nice property known as commutativity. Of course, my work would not have been possible without my fantastic mentor, Dr. Tanya Khovanova of MIT, who provided high-level insight and gave myriads of advice on exposition. I also must thank Dr. Kenneth Ribet of UC Berkeley, under whom I studied many algebraic structures which ended up in my project. I am grateful to the MIT PRIMES-USA program and its directors, Dr. Slava Gerovitch and Dr. Pavel Etingof, for allowing me to research, even during the pandemic. Finally, I am indebted to my parents for their unconditional support for me every step of the way.
My project shows new connections between complex algebraic structures, like group representations and semigroups, and Penney’s game. By better understanding how patterns appear in randomly generated strings, we can develop better pattern-finding algorithms, which help us find special keywords in large amounts of data (like needles in a haystack!). For instance, my work helps us find certain cytogenetic locators in genomic sequences and develop more efficient ways to compress data. My work also paves a new way to understand unavoidability, an unsolved problem that asks whether certain patterns are unavoidable, like in the case of data collisions or scheduling conflicts. Plus, now people know what the game is—all you need is a coin, paper, and a pen, and voila! You are already experimenting with very interesting mathematics.