Probability of number of $m$-walks in graph to be $l$

44 Views Asked by At

I'm considering this question: if a directed graph with adjacency matrix A satisfy that $P(a_{i,j}=1)=P(a_{i,j}=0)=0.5$ and $a_{i,i}=0$ for any i, j in ${1,...,n}$, where $n$ is the number of the nodes of graph. And $a_{i,j}$s are mutually independent. Then the question is , how to calculate \begin{equation} P(a_{i_0,j_0}^{(m)}=l) \end{equation} where $a_{i_0,j_0}^{(m)}$ means for node $i_0$, $j_0$, the number of $m$-walks that links the certain two nodes. I try to expand the $a_{i_0,j_0}$ as \begin{equation} a_{i_0,j_0}^{(m)}=\Sigma_{k_1,...,k_{m-1}\in\{1,...,n\}}a_{i_0k_1}...a_{k_{m-1}j} \end{equation} then it suffices to calculate \begin{equation} P(\Sigma_{k_1,...,k_{m-1}\in\{1,...,n\}}a_{i_0k_1}...a_{k_{m-1}j}=l) \end{equation} But it seems not easy to calculate this, could someone help me with that? I appreciate it so much!