4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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.) $\endgroup$ – usul Nov 1 '16 at 14:32
  • 2
    $\begingroup$ 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. $\endgroup$ – user83457 Nov 1 '16 at 15:07
  • $\begingroup$ I think: if $A_0$ and $A_1$ are invertible, then (1) $\ge$ (2). $\endgroup$ – Nawaf Bou-Rabee Nov 2 '16 at 2:49
  • 1
    $\begingroup$ @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). $\endgroup$ – Matt F. Nov 2 '16 at 2:56
  • $\begingroup$ @MattF. Good point. $\endgroup$ – Nawaf Bou-Rabee Nov 2 '16 at 3:30
5
$\begingroup$

This seems to be false.

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.

$\endgroup$
  • $\begingroup$ Thanks! This wasn't what I expected and I'll have to think some more. $\endgroup$ – Tom Kempton Nov 2 '16 at 9:29
  • $\begingroup$ 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! $\endgroup$ – Tom Kempton Nov 2 '16 at 9:36
  • $\begingroup$ @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. $\endgroup$ – Matt F. Nov 2 '16 at 13:55
  • 1
    $\begingroup$ Ah yes, I see. If we add epsilon to each entry of each matrix then what I said should become true, but there's no mixing in the system at present. Thanks again for the example, I don't think it completely kills my application, but it certainly stops me stating the lemma I want as simply as I had hoped... $\endgroup$ – Tom Kempton Nov 2 '16 at 15:24

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.