Probably of $A^k[i, j] \geq 1$ for a random matrix

Question

Suppose there is a square matrix $A$, with random elements (say $A[i, j] \geq 1$ with probability $p$). This can be thought of as the adjacency matrix of a (directed) graph and $A^k[i, j]$ as the number of path from $i$ to $j$ with length $k$.

Two question:

• What is the probability that Prob($A^k[i, j] \geq 1$). I.e. what is the probability that there is a path of length $k$ between two given nodes, in a random graph.

• How would the above probability change, if I tell you:

  • (a) $A^l[i, j]\geq 1, \text{for some }l, l > k$
  • (b) $A^l[i, j]\geq 1, \text{for some }l, l < k$.

I am not sure how hard are these questions. I did a little bit of thinking, didn't get anywhere. I hope I am not asking trivial questions.

Answer 1

This answer is wrong. It is retained here as the reason it is wrong may be of interest

Suppose that the graph has $n$ nodes. A $k$-length path from $i$ to $j$ consists of $i$ as node 0, followed by nodes 1, 2, ... , $k$ where $j$ is the $k$-th node. We have $n$ choices for node 1, $n-1$ choices for node 2 ... down to to $n-k+2$ choices for the ($k-1$)-th node, and then one choice for the $k$-th node.

Hence if the nodes have probability $p$ of being adjacent (and the probabilities are independent) then the probability of there being at least one $k$ length path from $i$ to $j$ is $$ \Pr(\text{At least one path of length $k$ from $i$ to $j$}) = \left( \Pi_{s=1}^{k-1} \left( 1 - (1-p)^{n-s+1} \right) \right)\cdot p $$

Answer 2

Simulation of $P_{n}[A^{k}_{ij}\geq1]$ for various n and k

For $k=2$ and arbitrary $n$ is simple to calculate the probability of having $A^{2}_{ij}\geq1$. In general: $$ P_{n}(A^{2}_{ij}\geq1)=1-(p^3-2p^2+1)(1-p^2)^{n-2} $$ and so the probability goes to one for big $n$, even for $k=2$.

P.S. From the simulation it seems that for $k\geq5$ the matrices become quite independent and the probability tends to a limit cycle...

Derivation of the formula for the case $k=2$

Consider first $n=3$.

We obviously have $P(A_{ij}^2\geq1)=1-P(A_{ij}^2=0)$. A generic element of the matrix $A$ is equal to one with probability $p$ and so is equal to zero with probability $1-p$. The number $N$ of paths that connect $i$ to $j$ is equal to: $$ N=\sum_{s=1}^{3} A_{is}A_{sj} $$ So we need to calculate the probability that this quantity sum to $0$.

First of all we notice that the element $A_{ij}$ appears twice in the sum and so we have two elements of the sum that are dependent and one that is independent and we need to take account this to avoid double counting. Now the only way that the this sum is zero is that all its elements are equal to zero.

For the independent term this happens with probability $(1-p^2)$. For the dependent terms we have zero with probability $(1-p) + p(1-p)^2$ (the first term is the probability that $A_{ij}=0$ and having this the other term is automatically null). And so we have: $$ P(A_{ij,n=3}^2=0) = (1-p+p(1-p)^2)(1-p^2) = 1 - p^2(p^3-2p^2-p+3) $$ and thus $$ P(A_{ij,n=3}^2\geq1)=p^2(p^3-2p^2-p+3) $$ The generalisation for arbitrary $n$ is now immediate, because the only link that appears two time in the counting is $A_{ij}$ and so we have for arbitrary $n$ $$ P(A_{ij}^2=0) = (1-p+p(1-p)^2)(1-p^2)^{n-2} = (p^3-2p^2+1)(1-p^2)^{n-2} $$ and thus $$ P(A_{ij}^2\geq1)=1-(p^3-2p^2+1)(1-p^2)^{n-2} $$

--------------------------------------------------------OLD--------------------------------------------------

Simulation of $P_{n}[A^{k}_{ij}=1]$ for various n and k I made a very quicky simulation,

I think it is quite interesting. The blu line is the probability of having a 1 in a 3x3 random matrix after $k$-power. Also the are the probabilities for $n=4,5,6,8$. The problem is the correlation, but it seems that this correlation quickly goes to zero...

I think that for the special case $n=3$, $k=2$ the true probability is: $$ P(A_{k}[i,j]=1)=p^2(1−p^2)(3−2p) $$ where $p$ is the probability of having a one in the original random matrix.

P.S. Did you change the question? This simulation is only for $P(A_{k}[i,j]=1)$

Answer 3

(A partial/placeholder answer only to show why my previous answer was wrong.)

The key is to conceptualise the probability space. The probability space for this question consists of the set of all (directed) graphs on $n$ vertices. The probability that you're seeking comes from looking at the graphs that have $k$ steps from node $i$ to node $j$. We want to accumulate the probabilities of realising each of those graphs given that edges have probability $p$ of existing.

The following procedure will calculate the desired probability:

• Write down the possible matrices $A$. There are $\ell = n^2$ possible edges, representing the directed graphs on $n$ nodes with self-loops allowed.

• Note that the probability of realising a given matrix $A$ is $p^s(1-p)^{\ell-s}$ where $s$ is the number of adjacent vertices in the graph represented by $A$. (Assuming independence in realising edges - not trivial.)

• Given $i$, $j$, and $k$, select all matrices $A$ such that $A^k[i,j] = 1$.

• Add up the probabilities for the selected matrices.

The following picture calculates the probability in the special case of $n=3$, $k=2$, $i=1$, $j=3$. The probability in this case is $p^2 + (1-p^2)p(1 - (1-p)^2)$. A little bit of algebra verifies that this is equal to $p^2(3 - p - 2p^2 + p^3)$ as obtained by @Alex.

.