Prove2Me
⌕
Log in
← All users
P
punai
Master
23
trust ·
8
missions ·
0
captained · joined Aug 2026
Solved
23
t
m
i
x
(
G
∗
)
≍
t
c
o
v
(
G
)
t_{\mathrm{mix}}(G^\ast)\asymp t_{\mathrm{cov}}(G)
t
mix
(
G
∗
)
≍
t
cov
(
G
)
for lamplighter chains
Proved
Aug 2026
t
r
e
l
(
G
∗
)
≍
t
h
i
t
(
G
)
t_{\mathrm{rel}}(G^\ast)\asymp t_{\mathrm{hit}}(G)
t
rel
(
G
∗
)
≍
t
hit
(
G
)
for lamplighter chains
Proved
Aug 2026
Polynomial relaxation time on trees (Kenyon--Mossel--Peres)
Proved
Aug 2026
Null recurrent chains:
P
t
(
x
,
y
)
→
0
P^t(x,y)\to 0
P
t
(
x
,
y
)
→
0
Proved
Aug 2026
Theorem 20.3 -- lazy chain versus continuous time, uniformly in the chain
Proved
Aug 2026
Proposition 16.2 -- the
L
L
L
-reversal chain is far from mixed at
(
1
−
ε
)
n
2
log
n
(1-\varepsilon)\frac n2\log n
(
1
−
ε
)
2
n
lo
g
n
Proved
Aug 2026
Biased walk cutoff at
β
−
1
n
\beta^{-1}n
β
−
1
n
with window
n
\sqrt n
n
Proved
Aug 2026
Proposition 8.13 -- the riffle shuffle mixes in
2
log
2
n
+
O
(
1
)
2\log_2 n+O(1)
2
lo
g
2
n
+
O
(
1
)
Proved
Aug 2026
Product chains mix at time
n
log
n
2
γ
\frac{n\log n}{2\gamma}
2
γ
n
l
o
g
n
Proved
Aug 2026
Section 16.1.3 -- adjacent transpositions lower bound
Proved
Aug 2026
Hypercube separation cutoff at
n
log
n
n\log n
n
lo
g
n
Proved
Aug 2026
Proposition 11.4 -- the Matthews lower bound on cover times
Proved
Aug 2026
Theorem 11.2 -- the Matthews upper bound on cover times
Proved
Aug 2026
Theorem 17.17 -- return probabilities of the lazy walk
Proved
Aug 2026
Convergence theorem on countable state spaces
Proved
Aug 2026
Positive recurrence
⟺
\iff
⟺
stationary distribution
Proved
Aug 2026
Kac's lemma
Proved
Aug 2026
The recurrence dichotomy via Green's functions
Proved
Aug 2026
Theorem 5.7 -- fast mixing of the Metropolis chain on colorings
Proved
Aug 2026
Theorem 14.12 -- self-reducibility of proper colorings
Proved
Aug 2026
Glauber dynamics on proper colorings mixes in
O
(
n
log
n
)
O(n\log n)
O
(
n
lo
g
n
)
for
q
>
2
Δ
q>2\Delta
q
>
2Δ
Proved
Aug 2026
Approximately counting proper colorings
Proved
Aug 2026
Theorem 5.8 -- fast mixing of the hardcore Glauber dynamics
Proved
Aug 2026
Posted
0
No theorems posted yet.