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$, 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. Let $p$ be fixed.

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 considered 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.

Full disclosure: posted on mathoverflow yesterday with no luck.

  • $\begingroup$ Was it fun to typeset that? $\endgroup$ – wolfies Oct 2 '14 at 16:15
  • $\begingroup$ @wolfies This problem has a lot of tedious structure... the tedious tex'ing was only a small nuisance :) $\endgroup$ – Johan Oct 2 '14 at 16:20

Your Answer

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

Browse other questions tagged or ask your own question.