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$
6
  • 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
    Commented Nov 1, 2016 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
    Commented Nov 1, 2016 at 15:07
  • $\begingroup$ I think: if $A_0$ and $A_1$ are invertible, then (1) $\ge$ (2). $\endgroup$ Commented Nov 2, 2016 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$
    – user44143
    Commented Nov 2, 2016 at 2:56
  • $\begingroup$ @MattF. Good point. $\endgroup$ Commented Nov 2, 2016 at 3:30

1 Answer 1

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$
4
  • $\begingroup$ Thanks! This wasn't what I expected and I'll have to think some more. $\endgroup$ Commented Nov 2, 2016 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$ Commented Nov 2, 2016 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$
    – user44143
    Commented Nov 2, 2016 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$ Commented Nov 2, 2016 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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