Multiplication of random sparse matrices

Question

I am given 2 unstructured (i.e. do not posses any special sparsity pattern like banded/triangular/etc.) sparse matrices $A$ and $B$ of dimension ($n$ x $n$) and density $d$ each (thus each matrix contains $n^2 d$ non zero elements).
In terms of probability, for any element $A(i,j)$,
$p (A[i,j] \neq 0) = d$ and independent of all other elements of $A$.
Similar probability distribution occurs for $B$.
I wanted to know if it is possible to calculate the expected density of $C = AB$ in terms of $n$ and $d$ i.e. the distribution $p( C[i,j] \neq 0 )$?

Answer 1

I took a go at this and hopefully I am able to write this properly to articulate the logic. In this logic, I am assuming summation of terms from $A$ and $B$ used to compute a term in $C$ can't cancel out to equal $0$ and that instead $C$ only has zero terms based on the sparseness of $A$ and $B$. Please let me know if you spot any errors.

$$ \begin{align} p\left( \left\{C(i,j) \neq 0\right\} \right) &= p\left( \bigcup_{k=1}^{n} \left\{ A(i,k)B(k,j) \neq 0 \right\} \right)\\ &= 1 - p\left( \bigcap_{k=1}^{n} \left\{ A(i,k)B(k,j) \neq 0 \right\}^c \right)\\ &= 1 - \prod_{k=1}^n p\left( \left\{ A(i,k)B(k,j) \neq 0 \right\}^c \right)\\ &= 1 - \prod_{k=1}^n \left( 1 - p\left( \left\{ A(i,k)B(k,j) \neq 0 \right\} \right) \right)\\ &= 1 - \prod_{k=1}^n \left( 1 - p\left( \left\{ \left\{A(i,k) \neq 0 \right\} \bigcap \left\{ B(k,j) \neq 0 \right\} \right\} \right) \right)\\ &= 1 - \prod_{k=1}^n \left( 1 - p\left( \left\{A(i,k) \neq 0 \right\} \right) p\left(\left\{ B(k,j) \neq 0 \right\} \right) \right)\\ &= 1 - \prod_{k=1}^n \left( 1 - d^2 \right)\\ &= 1 - \left( 1 - d^2 \right)^n\\ &\approx nd^2\;\;\;\;\; \forall d^2 \ll 1 \end{align} $$