4
$\begingroup$

Consider a Toeplitz matrix $T$, indexed by $\mathbb{N}_0 \times \mathbb{N}_0$. given by the sequence $t_k,k \in \mathbb{Z}$ where $t_k \geq 0,\sum_{k=-\infty}^\infty t_k=1$. By this I mean that $T_{i,i+k}=t_k$ for all $i \in \mathbb{N}_0$ and $k \in \{ -i,-(i-1),\dots,0,1,\dots \}$.

It is easy to see that $T$ defines a bounded operator on all the $\ell^p(\mathbb{N}_0)$ spaces. Suppose additionally that there are vectors $b,x^*$ with $Tx^*+b=x^*$.

I would like to understand under what assumptions the iteration $x^{(k+1)}= Tx^{(k)}+b$ will converge to $x^*$.

It is not hard to see that this will not happen if $\lim_{i \to \infty} x^{(0)}_i$ and $\lim_{i \to \infty} x^*_i$ both exist but are different. Thus $\ell^\infty$ perturbations will in general not decay. But it seems that this should be the only obstacle, i.e. $\ell^p$ perturbations should decay.

However, Szego's theorem tells us that the spectrum of $T$ accumulates around $1$, since it traces out the curve $\left \{ \sum_{k=-\infty}^\infty t_k e^{2 \pi i k \lambda} : \lambda \in [0,1] \right \}$. So it seems that there is no hope of using a simple Banach fixed point theorem argument. Is there some workaround? Perhaps some kind of Riemann-Lebesgue lemma type argument based on the idea that the eigenvectors whose eigenvalues are near $1$ cannot contribute too much to any fixed $x^{(0)}$? Or perhaps some kind of Perron-Frobenius type result?

Improve this question
$\endgroup$
2
  • $\begingroup$ So what exactly are you asking? Just whether $T^k x$ converges to $0$ in $\ell^p$ for every $x\in\ell^p$ (if we remove all the irrelevant stuff by an approptiate affine change of variable)? $\endgroup$
    – fedja
    Nov 18, 2017 at 0:01
  • $\begingroup$ @fedja An affirmative answer to that would answer the question, but a negative answer wouldn't (I'd like a hypothesis on $x^{(0)}$ that works even if it turns out to be restrictive). $\endgroup$
    – Ian
    Nov 18, 2017 at 4:18

1 Answer 1

Reset to default
1
$\begingroup$

OK. The case when one $t_k=1$ and the rest are $0$ is easy to figure out (left shifts are good, the rest are bad). Assume that all $t_k<1$. The $\ell_1$ problem is essentially equivalent to the question when the corresponding random walk on $\mathbb Z$ has positive chance to stay above $0$ forever (this is not obvious to me except in non-interesting cases like that of finite step variance, say, and the answer does depend on $t_k$). However, any other $\ell^p$ ($1<p<\infty$) is trivial again because it will suffice to show that the images of every $x$ consisting of a single $1$ and a bunch of zeroes tend to $0$ in the uniform norm since their $\ell^1$ norms are bounded by $1$, which is true even for the full convolution on $\mathbb Z$ (if $f(z)=\sum t_kz^k$, then all entries of $T^kx$ are bounded by $\int_{\mathbb T}|f(z)|^k\,dm(z)$ and the dominated convergence theorem finishes the story).

So, the question is now just this. Given a random walk on $\mathbb Z$, find a reasonable necessary and sufficient condition for its having a positive chance to stay above $0$ forever starting with some sufficiently positive point. I'm inclined to wait for real probabilists to say something about it because that has definitely been considered in the literature and I do not feel like it is an undergraduate level question.

Improve this answer
$\endgroup$
8
  • $\begingroup$ I think in the $\ell^1$ case you are referring to the fact that $T$ can be written as $S D^{-1}$ where $S$ is row stochastic and $D$ is diagonal with $D_{ii}=\sum_k T_{ik}$, so powers of $T$ are more or less controlled by powers of $S$. Is that right? I think I see the idea you are referring to in the $\ell^p$ case (there is some sort of "spreading" that leads to decay in $\ell^p$ even if not in $\ell^1$). $\endgroup$
    – Ian
    Nov 18, 2017 at 5:05
  • $\begingroup$ @Ian No, you do not need to rewrite anything. Just think a bit of which paths in the random walk correspond to the admissible products in $T^k$. In the $\ell^p$ ($p\in(1,\infty)$) case just note that an arbitrary vector is a sum of a vector with finite support (that is killed by the above argument) and an arbitrarily small tail vector (whose norm cannot grow). The whole point of my post was just to brush off the trivialities and highlight the core of the question. $\endgroup$
    – fedja
    Nov 18, 2017 at 5:35
  • 1
    $\begingroup$ Here is a classification for Fedja's last point: 1) If the mean $\sum k t_k$ exists and is positive, then the probability is positive. If it is negative, then it is zero. This follows from the strong law of large numbers. 2) In general there is a criterion for transience/recurrence: the walk is recurrent iff $Re[1/(1-\phi(\theta))]$ is not integrable in a neighborhood of 0 (here $\phi(\theta)$ is the characteristic function; this is Theorem in page 84 of Spitzer, principles of random walk, second edition). In case of recurrence, the probability you ask about is 0. $\endgroup$
    – ofer zeitouni
    Nov 24, 2017 at 9:15
  • 1
    $\begingroup$ 3) If the mean vanishes and the walk is transient, it must oscillate. Indeed, if $S_n\to \infty$ with positive probability then necessarily by Kesten's lemma, $\liminf S_n/n>0$, which is impossible due to the ergodic theorem. (H. Kesten, Sums of stationary sequences cannot grow slower than linearly, Proc. AMS 49 (1975) pp. 205–211.) 4) When the walk is transient and the mean does not exist, P5 in page 181 of Spitzer says that $1-E(z^T)=e^{-\sum \frac{z^k}{k} P(S_k<0)}$ where $|z|<1$ and $T=\inf \{n: S_n<0\}$. Thus, everything is determined by the limit as $|z|\to 1$ of the sum. $\endgroup$
    – ofer zeitouni
    Nov 24, 2017 at 9:16
  • 1
    $\begingroup$ @Ian This is just to attract your attention to Ofer's comments (MO doesn't automatically notify the poster of the question about comments to the answers as far as I know :-) $\endgroup$
    – fedja
    Nov 25, 2017 at 3:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.