Maximum column sum of stochastic matrix 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.


*

*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. 

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

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

*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)

 A: 

*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$.


*

*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$?
