Vtyjkyuk

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 $fracP^kk leq |P|_1$ for all $k$ ?




3. Is it true that $fracP^kk^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)

2. This is not true.
   Let
   $$
   P =
   beginpmatrix
   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 \
   endpmatrix
   $$
   Then,
   $$
   P^2 =
   beginpmatrix
   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 \
   endpmatrix$$

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 = sqrtn$, while $lVert P^2 rVert_1 = n$. Was it attracted to some state more than another chain, with $lVert P rVert_1 = fracn2$ and $lVert P^2 rVert_1 = n$?

Update:
As per new question regarding $fraclVert P^k rVert_1k^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 $sqrtn$.

Could it be $fraclVert P^sqrtn + 1 rVert_1sqrtn + 1 geq lVert P rVert_1$?