Brownian Motion to Bits (and back)

Alon Kipnis
Graduate Student, Stanford University
Date: Oct. 21st, 2016


What is the minimal mean squared error in recovering a path of a one-dimensional Brownian motion from any finite bit per time lag encoded version of it? Is it possible to attain a bounded mean squared error in this case?

Berger's PhD thesis answers these two question by providing a coding theorem for the Brownian motion, showing that its optimal distortion-rate performance are described by Shannon's distortion-rate function. That is, Berger's result implies that for any positive bitrate, there exists a coding scheme that allows recovering of the Brownian path with mean squared error equals to Shannon's distortion-rate function.

Berger's result, however, does not take into account practical considerations in encoding analog process. Indeed, hardware and other implementation constraints restrict access only to samples of the continuous-time path, taken at a finite time resolution. The question that we ask in this talk is what is the minimal mean squared error in recovering the original Brownian path from a code that is only a function of these samples. This question is answered by deriving the distortion-rate function as a function of the sampling rate. It can be shown that the ratio between this function and the distortion-rate function of Berger is only a function of the number of bits per sample. For example, our result implies that using 1 bits per sample, one can attain distortion which is no more than 1.12 times the distortion-rate function.

Another interesting question arises in the following case: assume that the source encoder receives the discrete-time samples but is unaware of their underlying continuous-time origin. As a result, the encoder applies an optimal source code with respect to the empirical distribution of these samples, namely with respect to a discrete-time Brownian motion. We show that the maximal loss in this case, compared to an encoder that considers the continuous-time origin, does not exceed 1/6 times the intensity of the process.


Alon Kipnis is a fifth year PhD candidate in the Department of Electrical Engineering at Stanford. Previously he completed his M.Sc. in mathematics from Ben-Gurion University. His research interests included information theory, signal processing and stochastic analysis.