1
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – joriki
    Commented Feb 14, 2023 at 11:09
  • $\begingroup$ 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. $\endgroup$
    – Duber
    Commented Feb 14, 2023 at 13:10
  • $\begingroup$ 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. $\endgroup$ Commented Feb 14, 2023 at 15:31
  • $\begingroup$ Thank you Misha, could you be a bit specifier about the special case that is solvable? $\endgroup$
    – Duber
    Commented Feb 14, 2023 at 15:41
  • $\begingroup$ 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. $\endgroup$ Commented Feb 14, 2023 at 16:39

0

You must log in to answer this question.

Browse other questions tagged .