- #1
barbutzo
- 8
- 0
Homework Statement
Let us define the following random walk:
Start with a randomly chosen (with uniform probability) unit vector (with respect to the usual Euclidean norm) in [tex]\mathbb{R}^n[/tex] and call it [tex]x^{(0)}[/tex]. Now, [tex]x^{(t+1)}[/tex] is generated from [tex]x^{(t)}[/tex] in the following manner - randomly and uniformly choose two coordinates [tex]i<j[/tex], and an angle [tex]\theta \in [0,2\pi)[/tex] and rotate [tex]((x^{(t)})_i,(x^{(t)})_j)[/tex] by the angle [tex]\theta[/tex]. That is, replace [tex]((x^{(t)})_i,(x^{(t)})_j)[/tex] with [tex]((x^{(t)})_i*\cos(\theta)+(x^{(t)})_j*\sin(\theta),-(x^{(t)})_i*\sin(\theta)+(x^{(t)})_j*\cos(\theta))[/tex]. Now we want to calculate (up to constants) the value of [tex]\lim_{t\rightarrow\infty}\mathbb{E}[\Vert x^{(t)} \Vert_4^4][/tex].
Homework Equations
I'm not really sure what to write here - as this is from an advanced algorithms class, so I guess it does not assume any more than undergrad probability.
The Attempt at a Solution
Well, I don't have much more that intuition here - it seems that after a while the [tex]x[/tex] vector should resemble [tex](\frac{1}{\sqrt(n)},\frac{1}{\sqrt(n)},\ldots,\frac{1}{\sqrt(n)})[/tex] but I have no idea how to formalize it. I mean - suppose one entry (or a set of entries) is too big - than with probability 1 it will end up getting rotated, but how will the rotation affect its value? It might get rotated with a huge coordinate!
Last edited: