# Expectation and Dependence

Probably a very simple question, I think I'm looking for a general statement that says 'if one decreases the independence between two processes then the expected value of the maximum of these two processes decreases'.

More precisely, let $A_0, A_1$ be two non-negative $2\times 2$ matrices. Let $n\geq 6$ and $p\in(0,1)$. I want to compare

(1) $\mathbb E (\max\{||A_{i_1}\cdots A_{i_n}||, ||A_{j_1}\cdots A_{j_n}||\}:$ each $i_k, j_k\in\{0,1\}$ is picked independently with probability $(p,1-p))$

(2) $\mathbb E (\max\{||A_{i_1}\cdots A_{i_n}||, ||A_{j_1}\cdots A_{j_n}||\}:$ each $i_k, j_k\in\{0,1\}$ is picked independently with probability $(p,1-p)$ apart from $j_5$, which is fixed at $j_5=i_3)$.

The $i_3=j_5$ condition is just meant to be some kind of dependence condition that isn't easy to factor out (I don't want to be able to write $A_{i_1}\cdots A_{i_n}$ and $A_{j_1}\cdots A_{j_n}$ as a product of 'the dependent bit' and 'the independent bit').

I would like to say that the value of (1) is greater than or equal to the value of (2), and that this follows from some general principle in probability theory that introducing any kind of dependence between two random processes decreases the expected value of the maximum of these two processes. Unfortunately I don't know my way around the probability literature, so any tips would be very welcome.

I'm trying to solve some problems in dynamical systems that rely on this kind of estimate. Apologies if this is trivial.

• Just a quick comment: "decreasing independence" is not enough, you are also relying on "increasing correlation". (e.g. if $X,Y$ are uniform random {0,1}s, then the condition $X\neq Y$ increases the expected maximum over the independent case, but the condition $X=Y$ decreases it.) – usul Nov 1 '16 at 14:32
• If you were getting your matrices by taking i.i.d. entries I think it would be an easy consequence of the FKG inequality & that the matrix norm is increasing as a function of each entry for positive matrices. – user83457 Nov 1 '16 at 15:07
• I think: if $A_0$ and $A_1$ are invertible, then (1) $\ge$ (2). – Nawaf Bou-Rabee Nov 2 '16 at 2:49
• @NawafBou-Rabee, that also fails: take the matrices in my answer and add epsilon to all the diagonal entries. This will make them invertible, but for sufficiently small epsilon we will still have (2)>(1). – Matt F. Nov 2 '16 at 2:56
• @MattF. Good point. – Nawaf Bou-Rabee Nov 2 '16 at 3:30

Let $n=6$, $\ p=1/2$, $$A_0 = \left( \begin{matrix} 0 & 1 \\ 0 & 1 \\ \end{matrix} \right), \ \ A_1 = \left( \begin{matrix} 1 & 0 \\ 0 & 0 \\ \end{matrix} \right).$$
So the norm of the product is either $\sqrt{2}$, 1 or 0. (If the norms or matrices seem artificial, they can be adjusted by $\epsilon$ without affecting the result.)
The two expectations are $(720+127\sqrt{2})/4096 = .2196$ for the uncorrelated case and $(724+126\sqrt{2})/4096 = .2203$ for the correlated case.
• I suspect that for large $n$, and replacing our dependency condition with $i_{100}=j_{200}$, this counterexample would break down, as one starts to get some probability distribution on the relative sizes of entries in a long random product of matrices. But i'm still really surprised by this answer! – Tom Kempton Nov 2 '16 at 9:36
• @TomKempton, I think this example works even with $i_{100}=j_{200}$, at least for n<400. The issue is that when k<n/2, you get higher expected norm with i_k=0, and when k>n/2, you get higher expected norm with i_k=1. There are only n+1 ways to get a non-zero product, so you could actually calculate this exactly. – Matt F. Nov 2 '16 at 13:55