Maximum column sum of stochastic matrix

Question

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)

Answer 1

2. 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$?