6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I suppose you mean e.g. $\mathbb P(A^k[i,j]\geqslant 1)$? $\endgroup$ – Math1000 May 9 '18 at 6:27
  • $\begingroup$ Loops are the problem, I think. For me it is non trivial, for example in the case of a $3*3$ matrix, with $k=2$ we have $P(A^{k}[i,j]=1)=p^2(1-p^2)(3-2p)$ where $p$ is the probability of having $1$. It is simple to generalise to any $n$ , but it is more difficult to generalise to any $k$ $\endgroup$ – Alex May 9 '18 at 11:19
  • 1
    $\begingroup$ @Math1000 yes! good catch! $\endgroup$ – Daniel May 9 '18 at 14:01
  • $\begingroup$ @Alex Would it be easier if we assume that there are no cycles? There seem to be algorithms that achieve this, while preserving approximate edge/node generation equal-probability and independence: arxiv.org/abs/0907.4346 $\endgroup$ – Daniel May 9 '18 at 14:18
  • $\begingroup$ @Daniel Maybe, later I will read the article...Meanwhile, take a look at the simulation I quickly made $\endgroup$ – Alex May 9 '18 at 14:39
2
$\begingroup$

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

enter image description here

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,
enter image description here enter image description here

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)$

$\endgroup$
  • $\begingroup$ Ah sorry. I think what I had in mind was "the existence of any path", not exactly one path. My apologies. $\endgroup$ – Daniel May 9 '18 at 15:06
  • 1
    $\begingroup$ And I realized this only after @Math1000 pointed it out. $\endgroup$ – Daniel May 9 '18 at 15:07
  • $\begingroup$ @Daniel So, we need to calculate the probability that $P_{k,n}(A_{ij}=0)$. I think it is slightly easier to find a recurrence relationship in this case. I made a new simulation.... $\endgroup$ – Alex May 9 '18 at 15:33
  • $\begingroup$ Thanks. This makes more sense to me. Looks like for big enough $n$ the probability get to one, even for small values of $k$. $\endgroup$ – Daniel May 9 '18 at 15:41
  • 1
    $\begingroup$ @Daniel Yes it is...But for $k=2$ is simple to calculate the probability for any $n$, i.e. for $n=3$ we have $P_{k=2,n=3}[A_{i,j}^{k}\geq1]=p^2(p^3-2p^2-p+3)$ where $p$ is the probability of having 1 in the matrix $A_{i,j}$. The generalisation is not difficult $\endgroup$ – Alex May 9 '18 at 19:27
0
$\begingroup$

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 $$

$\endgroup$
  • $\begingroup$ What makes the problem really tricky for directed graphs? Is it the cycle? $\endgroup$ – Daniel May 9 '18 at 14:11
  • $\begingroup$ Actually I think the solution will work for digraphs too. I will edit. $\endgroup$ – Patrick Hew May 9 '18 at 14:17
  • $\begingroup$ This is the probability that a greedy algorithm finds a path of length $k$: it goes from $i$ to the first node there's a connection to, then from there again to the first new node it finds, and so on, and finally goes from the last node it finds to $k$. It is far from the probability that there's any path of length $k$. $\endgroup$ – Misha Lavrov May 9 '18 at 14:24
  • $\begingroup$ Yes I think @Misha Lavrov is right. The problem here is to correctly conceptualise the probability space. I will build a better answer. $\endgroup$ – Patrick Hew May 9 '18 at 14:50
0
$\begingroup$

(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.

Calculation for the special case of $n=3$, $k=2$, $i=1$, $j=3$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.