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

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)
• 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. Aug 13, 2018 at 8:25
• @uniquesolution Added more information as per requested. Aug 13, 2018 at 11:26
• Can you please limit yourself to just one question per post? Aug 14, 2018 at 0:08

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

• 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. Aug 13, 2018 at 11:28
• New question 3 was actually answered for 1. part! Aug 13, 2018 at 12:01