UCSB CS Theory Colloquium Series

Fall 2022

CS-PSTAT Distinguished Lecture

Persi Diaconis (Stanford)

Friday, September 30th, Noon at Bren 1414

Title: Adding Numbers and Shuffling Cards

Abstract: When numbers are added in the usual way, 'carries' occur along the way. Carries make a mess and it is natural to ask, 'how do the carries go?' How many carries are typical, and if you just had a carry, is it more or less likely to have a carry in the next column? It turns out that carries form a Markov chain with an 'Amazing' transition matrix. Further, this same matrix comes up as a central player in analyzing the usual method of riffle shuffling cards. I will explain both sides, in particular the 'seven shuffles theorem' and their connection. The math has connections to all kinds of corners. The findings actually connect to hardware design (Knuth's favorite way to represent numbers is ``balanced ternary'--these have the fewest carries). I will try to explain all of this to a general audience 'in English'.

Bio: Diaconis left home at 14 to travel with sleight-of-hand legend Dai Vernon. To do so, he dropped out of high school, promising himself that he would return one day so that he could learn all of the math necessary to read William Feller's famous two-volume treatise on probability theory, An Introduction to Probability Theory and Its Applications. He returned to school (City College of New York for his undergraduate work, graduating in 1971 and then a Ph.D. in Mathematical Statistics from Harvard University in 1974), learned to read Feller, and became a mathematical probabilist. He is the Mary V. Sunseri Professor of Statistics and Mathematics at Stanford University.