# Probability of having a path of a given length in a random graph

Suppose $G=\langle V,E \rangle$ is a directed graph consisting of $n\in \mathbb{N}$ vertices. Vertex $v_i \in V$ has an edge to vertex $v_j \in V$ with a probability of $P(i, j) = f(|i-j|)$ where $f$ is a descending "good enough" function.

What is probability to have a path of length $k$?

Update 1. Let us consider a simplified problem. Suppose the probability of having an edge between any two arbitrary vertices is fixed and equals $p$. Thus, the adjacency matrix $\bf A$ consists of elements $a_{ij} = \delta(p)$ equal $1$ with a probability of $p$.

It's well known that $({\bf A}^k)_{ij}$ gives the number of $k$-paths from $v_i$ to $v_j$. Can we employ that?

• It is not exactly clear how arcs are distributed. Is it for a $fixed$ acyclic digraph $G$, each arc of $G$ is deleted with probability $1-P(i,j)$? Or do you not mean to include the term acyclic? – D Poole Oct 30 '13 at 14:07
• @DPoole OK, let's remove the acyclicity requirement as irrelevant. – Yury Bayda Oct 30 '13 at 19:14
• A few more questions. Do you want to know the probability that the digraph has a path of length $k$ or for some generic $v_i$ and $v_j$, the probability that there is a path of length $k$ between $v_i$ and $v_j$? Also are you looking for the exact probability or are asymptotic bounds for this probability sufficient? If asymptotic bounds are good, what range of $k$ and $p$ are you looking at? – D Poole Nov 1 '13 at 18:37
• @DPoole 1) the probability that the digraph has a path of length $k$. 2) exact probability (nevertheless, an example of asymptotic estimation will be useful) – Yury Bayda Nov 1 '13 at 21:24
• In the limit for large graphs, the result you are looking for is Theorem 2.1 of arxiv.org/pdf/1005.4104v1.pdf – ckoe Nov 25 '15 at 15:31