The investigator will study problems in discrete probability, most of which concern mixing times for Markov chains. The Thorp shuffle, which is a method of card shuffling based on "local swaps" has found applications to applied cryptography. It is the basis of a new algorithm to encipher small messages such as social security numbers. Recently, algorithms based on variants of the Thorp shuffle that use both local and global swaps have been proposed. It is planned to obtain good mixing time bounds for these shuffles. These shuffles appear to have a very strong mixing property that relates to the cryptographic notion of indifferentiability. It is planned to prove this rigorously. It is also planned to study a number of problems concerning random walks on graphs, including Aldous and Fill's conjecture that for coalescing random walks, the expected time for all particles to coalesce is at most a constant times the maximum expected hitting time of any vertex.
The primary goal of this project is to find improved methods to analyze Markov chains. Markov chains have been used widely in statistics, statistical physics, simulation and optimization. This project focuses on Markov chains used in "small space" encryption algorithms. With rising concerns about identity theft, methods to encrypt small messages such as social security numbers are of great practical interest.
The major goal of the project was to use the mathematics of card shuffling to find improved algorithms for format-preserving encryption, which has applications such as enciphering credit card numbers or social security numbers. Other goals included analysis of mixing times of Markov chains (e.g., the number of shuffles necessary to randomize a deck of cards), the cover time (the number of steps necessary for a random walk to visit every state), and random walks on fractals. In joint work with Phillip Rogaway, the PI used a card shuffle as the basis for a new enciphering scheme. This scheme can efficiently encipher credit card numbers and social security numbers in such a way that the encodings are of the same form as the original data. In a joint work with Anastasia Raymer, the PI analyzed the 15 puzzle. The question was how many moves are required to "mix up" the puzzle, with a goal of improving techniques for bounding mixing times of Markov chains. In a joint work with Itai Benjamini and Ori Gurel-Gurevich, the PI studied the cover time of a random walk, finding that it is extremely unlikely that a random walk will visit every possible state after a number of steps that is of the same order as the number of states. In a joint work with Steve Evans and Arnab Sen, the PI analyzed coalescing random walks on fractals, showing that after any amount of time has elapsed there must be only finitely many particles in the system.
