Skip to main content
3 of 4
added 73 characters in body
Dustin G. Mixon
  • 7.6k
  • 2
  • 31
  • 56

How fast is discrete-time diffusion on a continuous set?

This question is inspired by Joseph O'Rourke's beautiful answer to my previous question.

Let $\mathbb{S}^{d\times n}$ denote the set of real $d\times n$ matrices whose columns have unit norm and sum to the zero vector. I want to approximate the uniform distribution on this set by running a diffusion process. Specifically, consider the following random transition: Given a member of $\mathbb{S}^{d\times n}$, select some columns at random (say, each column is independently active with probability $1/2$), and then apply a random rotation to these columns that fixes their sum. This transition can be expressed in terms of a conditional density on $\mathbb{S}^{d\times n}$, namely $f(x^{(i+1)}|x^{(i)})$. Next, define the operator $A:L^1(\mathbb{S}^{d\times n})\rightarrow L^1(\mathbb{S}^{d\times n})$ that uses this transition rule to update the distribution on $\mathbb{S}^{d\times n}$: $$ g^{(i+1)}(x) =(Ag^{(i)})(x) :=\int_{\mathbb{S}^{d\times n}}f(x|y)g^{(i)}(y)dy. $$ My questions concern this operator:

(1) Since $f(x|y)=f(y|x)$ for almost every $x$ and $y$, it is straightforward to see that $A$ sends the uniform distribution to itself. But is this stationary distribution also the limiting distribution?

(2) Assuming this is the limiting distribution, how fast is the convergence? I assume there is an analog to expander walk sampling (i.e., the rate of convergence should be expressed in terms of the spectrum of $A$), but I would like a reference for the continuous-state case. Yoav Kallus commented on Joseph O'Rourke's answer to my previous question that polymer people might use the phrase "Rouse relaxation time" to describe this, but these keywords haven't helped me find the theorem I want.

(3) Assuming the rate of convergence is completely expressible in terms of the spectrum of $A$, how do I actually calculate the spectrum? Do the symmetries in the transition rule naturally lead to a Fourier-type eigenbasis?

Dustin G. Mixon
  • 7.6k
  • 2
  • 31
  • 56