Flipping coins to win!

Few things match the romance of a valentine’s day, but winning big on coin flips is not a bad second! While it is difficult to predict the output from a single coin flip, we can, over a longer horizon, figure out which horse to bet on, that is, the coin with the largest favorable bias. But how to learn this quickly to maximize our winnings? Even such simple problems can have a complex and yet delightfully elegant solution. In this talk we outline the underlying ideas. These involve skillful use of information theory, optimization theory and probabilistic ideas including intricate concentration inequalities. As a bonus, we are able to go much beyond Bernoulli coin flips to general probability distributions. We also discuss related and more general problems in sequential learning theory and a myriad of applications based on these ideas.