New answers tagged

1

The inequality you are citing should have a power 2 on the Cheeger constant (a.k.a the bottleneck ratio), so the inequality should read: $$t_{\rm mix} \le C\log\left(\min_{v\in V}\dfrac{1}{\pi(v)}\right)\Phi(L)^{-2} \,.$$ This need not hold on a simple graph without loops; e.g. it fails if the graph is bipartite, where the mixing time is infinite. The ...


6

Let $\{b_n\}_{n \ge 1}$ be a sequence of independent random variables taking the values $\pm 1$ with probability $1/2$ each. Define $\{a_n\}_{n \ge 1}$ by $a_n=b_{n-1} b_{n-2}$ if $\; n \equiv 0 \mod 3$ and $a_n=b_n$ otherwise. Then the variables $a_n$ are pairwise independent. For example, if $\epsilon, \sigma \in {\pm1 }$ then $P(a_2=\epsilon,a_3=\sigma)...


9

I think you could make such an example by choosing any normal sequence $S$ on the alphabet $\{0,1,2,3\}$, and then applying the letter-to-word substitution $\tau$ defined by $0 \mapsto +++$, $1 \mapsto +--$, $2 \mapsto -+-$, $3 \mapsto --+$. (I'm abbreviating $1$ by $+$ and $-1$ by $-$.) The twofold independence comes from normality of $S$; you basically ...


8

$\def\ZZ{\mathbb{Z}}\def\RR{\mathbb{R}}$Here is a suggestion, with some details missing. Let $\theta$ be an irrational number and set $r_n = \{ \theta n^2 \}$, where $\{ \alpha \}$ is the fractional part of $\alpha$. Then I claim that the pairs $(r_n, r_{n+j})$ are equidistributed in $(\RR/\ZZ)^2$, but $(r_n, r_{n+1}, r_{n+2})$ is not equidistributed in $(\...


Top 50 recent answers are included