5
$\begingroup$

Consider the following $n \times n$ symmetric matrix of i.i.d. Bernoulli random variables, $X_{ij}$. For $i=1,...,n$ and $i<j\le n$. Let $X_{ij} \sim \text{Bernoulli}(p)$ when $i \ne j$ ($p$ fixed), and let $X_{ji} = X_{ij}$ (symmetry). For $i=j$, let $X_{ii} =0$ deterministically. This random matrix corresponds to a $G(n,p)$ random graph.

I am interested in the expectation of a complex quantity that reduces to the following expression: $$ Y_n = \frac{ \sum_{i,j,a,b,c,d} X_{ij} X_{ia} X_{bj} X_{cd} - \sum_{i,j,k,a,b,c} X_{ij} X_{ik} X_{ab} X_{ac} }{ \sum_{i,j,a,b,c,d} X_{ij} X_{ia} X_{ib} X_{cd} - \sum_{i,j,k,a,b,c} X_{ij} X_{ik} X_{ab} X_{ac} } := \frac{A_n}{B_n}, $$

where all sums are from $1$ to $n$. $A_n$ and $B_n$ are shorthand for the numerator and denominator.

This quantity is undefined (0/0) with positive probability for all $n$, so technically the expectation is undefined. However, under the following decomposition:

$$\mathbb E[Y_n] = \Pr[B_n = 0] \mathbb E[Y_n | B_n =0] + \Pr[B_n \ne 0] \mathbb E[Y_n | B_n \ne 0]$$

we have that $\mathbb E[Y_n | B_n =0]$ is undefined but $\mathbb E[Y_n | B_n \ne 0]$ is defined. It's possible to show that $\Pr[B_n = 0] \rightarrow 0$ as $n \rightarrow \infty$, so I'm interested in $\mathbb E[Y_n | B_n \ne 0]$, which is conditioning on a high probability event.

I have derived the following expectations:

\begin{eqnarray} \mathbb E [ \sum_{i,j,a,b,c,d} X_{ij} X_{ia} X_{bj} X_{cd}] &=& (n^6 -6n^5+7n^4)p^4 + (2n^5-2n^4)p^3 + n^4p^2 + O(n^3) \\ \mathbb E [ \sum_{i,j,a,b,c,d} X_{ij} X_{ia} X_{ib} X_{cd}] &=& (n^6 -7n^5+11n^4)p^4 + (3n^5-6n^4)p^3 + n^4p^2 + O(n^3) \\ \mathbb E [ \sum_{i,j,k,a,b,c} X_{ij} X_{ik} X_{ab} X_{ac}] &=& (n^6 -6n^5+5n^4)p^4 + (2n^5)p^3 + n^4p^2 + O(n^3) \end{eqnarray}

The resulting expectations of $A_n$ and $B_n$ are then:

\begin{eqnarray*} \mathbb E [A_n ] &=& (n^6 -6n^5+7n^4)p^4 + (2n^5-2n^4)p^3 + n^4p^2 - (n^6 -6n^5+5n^4)p^4 \\ && - (2n^5)p^3 - n^4p^2 + O(n^3) \\ &=& -2(p^3-p^4)n^4 + O(n^3), \end{eqnarray*} \begin{eqnarray*} \mathbb E [ B_n] &=& (n^6 -7n^5+11n^4)p^4 + (3n^5-6n^4)p^3 + n^4p^2 - (n^6 -6n^5+5n^4)p^4 \\ && - (2n^5)p^3 - n^4p^2 + O(n^3) \\ &=& (p^3-p^4)n^5 - 6(p^3 -p^4)n^4 + O(n^3). \end{eqnarray*}

I am wondering, what are ways of establishing that $\mathbb E[A_n /B_n | B_n \ne 0] = \mathbb E[A_n] / \mathbb E[B_n] + o(1)$ for such quantities?

The two approaches I have tried are:

  • Multivariate delta method: this requires establishing a CLT that $(A_n,B_n)$ is a joint normal distribution. This is going to require a CLT for the dependent variables that constitute the sums in question, but they are not $m$-dependent for any fixed $m$. I've also looked into CLTs for quadratic forms, but I haven't seen an answer there either.

  • Taylor expansion: in order to prove that the remainder is bounded, I need to establish a concentration inequality on both the numerator and denominator that is nearly the same as establishing a CLT, but perhaps a little easier. For more on this strategy, see here.

Suggestions for how to make one of these approaches work, or another approach, would be very much appreciated.

$\endgroup$

1 Answer 1

1
$\begingroup$

One possibility is to write $$ \mathbb{E} \frac{A}{B} = \mathbb{E} \frac{A}{1 + (B - 1)} = \sum_{k \ge 0} (-1)^k \mathbb{E} [A (B-1)^k]. $$ If you can show that $\mathbb E[A(B-1)^k] = (1+o(1)) \mathbb{E}[A] \mathbb{E}[(B-1)^k]$ for every $k$ (where $1+o(1)$ is uniform in $k$) then you have $\mathbb{E}[A/B] = (1 + o(1)) \mathbb{E}[A] \mathbb{E}[1/B]$.

In order to have $\mathbb{E}[1/B] = (1 + o(1)) 1/\mathbb{E}[B]$, you need to know that $B$ has almost no lower tail. For example, if $B > 0$ then you have $$ \begin{align*} \mathbb{E}[1/B] &= \int_0^\infty \Pr(1/B \ge t)\, dt \\ &= \int_0^\infty \Pr(B \le 1/t)\, dt \\ &\le \frac{1}{(1-\epsilon)\mathbb{E} [B]} + \int_{0}^{(1-\epsilon)\mathbb{E}[B]} \Pr(B \le s) \frac{ds}{s^2}, \end{align*} $$ and so it is enough to have upper bounds on $\Pr(B \le s)$ when $s$ is noticeably smaller than $\mathbb{E}[B]$

I'm not sure that this is the best/easiest approach to the problem, but somehow you need to do something like this. You can only reasonably expect $\mathbb{E}[A/B] \approx \mathbb{E}[A] / \mathbb{E}[B]$ if

  • $A$ and $B$ are more-or-less independent
  • $B$ is strongly concentrated, particularly in its lower tail.

The two things you would need to check (namely, $\mathbb E[A(B-1)^k] = (1+o(1)) \mathbb{E}[A] \mathbb{E}[(B-1)^k]$ and upper bounds on $\Pr(B \le s)$) are somehow versions of these.

$\endgroup$
1
  • $\begingroup$ Thank you very much Joe for proposing this approach, and your clear explanation. I will explore it and get back to this thread if/when I have any further questions. $\endgroup$ Oct 2, 2014 at 23:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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