Para receber por e-mail novas publicações de Seminário de Colóquio dos Alunos, Clique Aqui!

Seminários do IMPA

Colóquio dos Alunos

Título
The cutoff of the lazy random walk on the hypercube $\{1, -1\}^n$
Expositor
Shangjie Yang

IMPA
Data
Sexta-feira, 19 de outubro de 2018, 15:30
Local
Sala 236
Resumo

In this talk, we are interested in how does the lazy random walk on the hypercube relax to equilibrium.

The n-dimensional hypercube $\{1, -1\}^n$ is a graph whose vertices are the the binary sequences $(x_1, x_2, ..., x_n)$, where $x_i \in \{-1, 1\}$ for all $j \leq n$. Two vertices are connected by an edge if they differ at exactly one coordinate. The lazy random walk on the hypercube moves from the current vertex $(x_1, ..., x_n)$ to another vertex in the following manner: every time it chooses a coordinate $j\in \{1, 2, 3, ... n\}$ uniformly at random and chooses $u \in \{1, -1\}$ uniformly at random, and moves to the vertex $(x_1, ..., ux_j, ..., x_n)$. We show that around time $\frac{1}{2} n \log n$, the total variation distance to equilibrium of the lazy random walk on the hypercube $\{-1, 1\}^n$ drops abruptly from $1$ to $0$.