# functions over dependent random variables

Say we have a set of identically distributed integer-valued random variables: $\{ A_i \}_{i=1}^n$, such that they are not independent. Say we have another set of identically distributed integer-valued random variables $\{ B_i \}_{i=1}^n$, such that they are not independent (different dependence than that of the $A_i$'s).

If we have $A_i \sim B_i$, this is, $\lim A_i / B_i = 1$, what can we say about a function of the random variables such as:

$f(A_1, \dots, A_n) = \max_i A_i$ and $f(B_1, \dots, B_n) = \max_i B_i$

Does it follow that $f(A_1, \dots, A_n) \sim f(B_1, \dots, B_n)$?

Thanks!

-
What do you mean by $\lim A_i/B_i$? Is it large $n$ limit, or some other limit? – Sasha Jul 17 '12 at 19:11
I'm sorry, I forgot to say that the limit is taken as $n$ goes to $\infty$. For example, consider $A_i$ to be degree of a certain vertex $v_i$ in a random graph $G(n,p)$. They all have the same distribution, but they are not independent. The $B_i$'s could be the degree of another family of random graphs. In both cases, $f$ is the maximum degree of the graph. – Joanne Jul 17 '12 at 19:21
Are the $A_i$ and $B_i$ for one $n$ independent of those for other $n$'s? Is the limit supposed to be almost sure? And in particular $P(B_i = 0) \to 0$? – Robert Israel Jul 17 '12 at 19:43
For fixed $n$, each $A_i$ depends only on $\{ A_j : j \le n, j \neq i \}$. Yes, $P(A_i = 0) \rightarrow 0$ and $P(B_i = 0) \rightarrow 0$ in $n$. – Joanne Jul 17 '12 at 20:11
Yes, the $A_i$ and $B_i$ for one value of $n$ are independent of those for other values of $n$. – Joanne Jul 17 '12 at 20:15

The limit, $\lim \frac{A_{i}}{B_{i}} = 1$ is ill defined, but seems to mean that $A_{i}$ and $B_{i}$ are essentially the same till the first degree in the exponent.

I am assuming the limit $\displaystyle\lim_{n \to\infty} \frac{A_{i}}{B_{i}} = 1$ holds $\forall i = 1, \dots, n$, and that the random variable $A_{i}$ and $B_{i}$ depend on $n$.

The question breaks down to the following:

Is $\mathbb{P}\left(f(A_1, \dots, A_n) = f(B_1, \dots, B_n)\right) = 1$? (almost sure convergence)

For the given functions, $f(A_1, \dots, A_n) = \max_i A_i$ and $f(B_1, \dots, B_n) = \max_i B_i$, we have:

Is $\mathbb{P}\left(\max_i A_i = \max_i B_i\right) = 1$?

Intuitively, yes. Let me try to give a (semi)-rigorous proof.

Proof:

Let us explicitly represent $A_i$'s as a function of $n$, i.e. $A_i(n)$. Also, without loss of generality, let us take these random variables to be positive.

Let $\max_i A_i(n) = A_j(n)$ for some $j \in \{1, \dots n\}$. Then, by the relationship between $A_j(n)$ and $B_j(n)$ in the form of the above limit, for every $\epsilon > 0$, there exists a large enough $n_0$, such that $n \geq n_0$ and

$$A_j(n)/\left(1 - \epsilon\right) \geq B_j(n) \geq A_j(n)/\left(1 + \epsilon\right)\hspace{20 mm}(1)$$

Hence, if $A_j(n)$ is the maximum, as assumed above, then it stands to reason that $B_j(n)$ is the maximum among $B_i(n)$'s. Let me prove this rigorously.

Assume that $B_j(n)$ is not the maximum among $B_i(n)$'s. Let us also assume that there is only one $A_j(n)$ satisfying $\max_i A_i(n) = A_j(n)$. Consider $\max_i B_i(n) = B_k(n)$ for some $k \in \{1, \dots n\} \neq j.$ Then, for every $\epsilon > 0$, there exists some $n_1$ such that $n > n_1$ and:

$$A_k(n)/\left(1 - \epsilon\right) \geq B_k(n) \geq A_k(n)/\left(1 + \epsilon\right) \hspace{20 mm} (2)$$

This implies that $B_k(n)$ is arbitrarily close to $A_k(n)$ as $n \to \infty$. Similarly, eq. (1) tells us that $B_j(n)$ is arbitrarily close to $A_j(n)$ as $n \to \infty$. However, $max_i A_i(n) = A_j(n)$ and hence $A_j(n) \geq A_k(n)$. We, however, assumed that there exists only one $j$ that satisfies $max_i A_i(n) = A_j(n)$. Hence, clearly, $B_j(n) > B_k(n)$ for sufficiently large $n > \max(n_0, n_1)$. Clearly, we have a contradiction and therefore, $B_j(n)$ is indeed the maximum among $B_i(n)$ in the limit.

The case, where $A_j(n) = A_k(n)$ (for sufficiently large $n > \max(n_0, n_1)$) is trivially taken care of, since in this case $B_j(n) = B_k(n)$ and hence, in either case the limit,

$$\lim_{n \to\infty} \frac{\max_i A_{i}}{\max_i B_{i}} = \lim_{n \to\infty} \frac{A_{j}}{B_{j}} = 1 \hspace{20 mm} (3)$$

where $j$ is as defined above.

To finish it off, note that the limits mentioned in eq. (3) are the definition of almost sure convergence, and hence:

$\displaystyle \mathbb{P}\left(A_i = B_i\right) = 1$, $\forall i$.

Therefore, $\displaystyle \mathbb{P}\left(\max_i A_i = \max_i B_i\right) = 1$, where $j$ is such that $\max_i A_i = A_j$ and $\max_i B_i = B_j$.

Q.E.D.

By the way, not quite sure if the same reasoning can lead to a similar outcome for any general functions, $f(A_1, \dots, A_n)$ and $f(B_1, \dots, B_n)$.

-
Consider the random graph example: Let $G_1 = G(n,p_1(n))$ and $G_2 = G(n, p_2(n))$ be two different r.g.s Then, we define the random variables $A_i$ to be the degree of $v_i$ in $G_1$, for each $i \in \{1, \dots, n\}$. Similarly, we define $B_i$ to be the degree of $v_i$ in $G_2$. Then, for fixed $n$, we have that all the $A_i$'s are identically distributed (but they are not independent). Also, the $B_i$'s are identically distributed but they are not independent. If we have that $lim_{n \rightarrow \infty} A_i/B_i = 1$, can we conclude $lim_{n \rightarrow \infty} max_i A_i / max_i B_i = 1$? – Joanne Jul 17 '12 at 21:57
Well, based on my reasoning above, it seems to be the case. I'll try and verify my reasoning once again and make it totally rigorous. Anyway, is there something in my explanation that you don't understand? – lite-whowantstoknow Jul 18 '12 at 6:07
Joanne, I added more reasoning into my Proof. Hope this helps. – lite-whowantstoknow Jul 18 '12 at 20:27