1
$\begingroup$

For a stochastic matrix $P$ of size $n$, we define

$$\|P\|_1 := \max_{j \in [n]} \sum_{i \in [n]}|P(i,j)|$$

i.e., the maximum column sum, which is based on the $\|\cdot\|_1$ matrix norm. Now, although $\|P\|_\infty$ for all stochastic matrices (defined as the maximum row sum) is equal to one by definition, $\|P\|_1$ can grow as large as $n$. To see this, take the matrix where the first column is all ones and the rest are zeros.

  1. Is it possible to relate $\|P\|_1$ to other properties of the $n$ state Markov chain represented by this stochastic matrix? It seems like it quantifies how much the chain is attracted to a particular state.

  2. Is it true that $\frac{\|P^k\|_1}{k} \leq \|P\|_1$ for all $k$ ?

  3. Is it true that $\frac{\|P^k\|_1}{k^2} \leq \|P\|_1$ for all $k$ ?

  4. Has $\|P\|_1$ be considered in any way in the literature ?


So far:

  • I don't think it can be related to its mixing time as I can seem to be able to generate arbitrary slow mixing chains with the same value for $\|P\|_1$.
  • It makes sense that it stabilizes at some point when $k$ increases because in the long run the rows of $P^k$ are all $\pi$ (stationary distribution), so that I am expecting $\|P^k\|_1 \rightarrow n \cdot \max_i \pi_i$. I actually have been able to plot both oscillating and non-oscillating cases around that value for $k$ increasing.
  • Question 2 has been disproven by @dEmigOd.
  • I have a program running for trying to find counter examples for question 3, which has been unsuccessful so far (generating random rows from a Dirichlet distribution)
$\endgroup$
3
  • $\begingroup$ Please provide some context for your questions, calculations you have made, or any other information you have. Just throwing questions around will probably get them closed with no answers. $\endgroup$ Aug 13, 2018 at 8:25
  • $\begingroup$ @uniquesolution Added more information as per requested. $\endgroup$ Aug 13, 2018 at 11:26
  • $\begingroup$ Can you please limit yourself to just one question per post? $\endgroup$
    – Xander Henderson
    Aug 14, 2018 at 0:08

1 Answer 1

1
$\begingroup$
  1. This is not true. Let $$ P = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ \end{pmatrix} $$ Then, $$ P^2 = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix}$$

essentially every state will end in state $1$ in two steps.

We have, $\lVert P \rVert_1 = 3$, but $\lVert P^2 \rVert_1 = 7 > 2 \cdot \lVert P \rVert_1$.

  1. I suppose, it is not that difficult to imagine a chain with $\lVert P \rVert_1 = \sqrt{n}$, while $\lVert P^2 \rVert_1 = n$. Was it attracted to some state more than another chain, with $\lVert P \rVert_1 = \frac{n}{2}$ and $\lVert P^2 \rVert_1 = n$?

Update: As per new question regarding $\frac{\lVert P^k \rVert_1}{k^2} \leq \lVert P \rVert_1$.

Proceed in the same spirit, Now a $25 \times 25$ matrix will work. Send states $1-5$ to state $1$, states $6 - 10$ to state $2$, etc. In $2$ steps every state end up in state $1$. $\lVert P \rVert_1 = 5$, but $\lVert P^2 \rVert_1 = 25$. As I previously mentioned you can play with this until $\sqrt{n}$.

Could it be $\frac{\lVert P^{\sqrt{n} + 1} \rVert_1}{\sqrt{n} + 1} \geq \lVert P \rVert_1$?

$\endgroup$
2
  • $\begingroup$ About 2. I agree. Although somewhat rare, it can happen as confirmed by numerical simulation. I have not been able to generate any example when dividing by $k^2$ yet. $\endgroup$ Aug 13, 2018 at 11:28
  • $\begingroup$ New question 3 was actually answered for 1. part! $\endgroup$
    – dEmigOd
    Aug 13, 2018 at 12:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .