Polarization of Bounded Martingales

Madhu Sudan (Harvard)

A recent invention in information theory called Polar Coding (due to Arikan, 2008) has led to a remarkable construction of error-correcting codes and decoding algorithms, resolving one of the fundamental algorithmic challenges in the field of reliable transmission of information. 

The phenomenon underlying the success of Polar Codes is the ``polarization'' of a ``bounded'' martingale. A bounded martingale, X_0,...,X_t,...  is one where X_t in a bounded interval, say [0,1]. This martingale is said to polarize if lim_{t \to \infty} X_t \in {0,1} with probability one. The questions of interest to the results in coding are purely probabilistic ones: how close to the endpoints {0,1} does the martingale get to in t steps, and with what probability? While Arikan's construction explores these for specific martingales, studying polarization is general seems to be of natural interest.

In this talk I will introduce the concept of polarization. I will explain how this phenomenon was used by Arikan to construct Polar Codes, and explain how to analyze polarization in some fairly general settings.

Based on joint work with Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, and Atri Rudra.