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

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 $$$$P(a_{i_0,j_0}^{(m)}=l)$$$$ 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 $$$$a_{i_0,j_0}^{(m)}=\Sigma_{k_1,...,k_{m-1}\in\{1,...,n\}}a_{i_0k_1}...a_{k_{m-1}j}$$$$ then it suffices to calculate $$$$P(\Sigma_{k_1,...,k_{m-1}\in\{1,...,n\}}a_{i_0k_1}...a_{k_{m-1}j}=l)$$$$ But it seems not easy to calculate this, could someone help me with that? I appreciate it so much!

• There's not enough information to calculate this probability. I suspect that you forgot to add the assumption that the existences of the edges are mutually independent. If so, I doubt that there's a closed form for this probability. Commented Feb 14, 2023 at 11:09
• Thank you Joriki for commenting, yes I forgot to make clear that the existence of edges are mutually independent, but I still can not figure this out, could someone help with their ideas? The problem I think lies in how to treat the summation, we can not just simply pick $l$ of them and let them be 1 and others 0, because if you let some item be 1, there should be other items MUST also be 1, which makes me hard to calculate. Commented Feb 14, 2023 at 13:10
• I don't expect there to be a closed-form solution to this problem. If you're looking for a general solution, it might be hopeless. If you're looking for a special case, or if you want to solve a different problem by solving this one, then there may be hope. Commented Feb 14, 2023 at 15:31
• Thank you Misha, could you be a bit specifier about the special case that is solvable? Commented Feb 14, 2023 at 15:41
• I'm not saying I know of any particular special case that is solvable. I'm saying that if you have a particular special case that you want to solve, then it might still be possible. Commented Feb 14, 2023 at 16:39