Consider a random diagraph G = (V, A), where |V| = n and an arc (u, v) is present in A with probability p(n) independent of the existence of the other arcs. We discuss the expected number of vertices reachable from a vertex, the expected size of the transitive closure of G and their related topics based on the properties of reachability, where the reachability from a vertex s to t is defined as the probability that s is reachable to t. Let γn,p(n) denote the reachability s to t (≠ s) in the above random digraph G. (In case of s = t, it requires another definition.) We first present a method of computing the exact value of γn,p(n) for given n and p(n). Since the computation of γn,p(n) by this method requires O(n3) time, we then derive simple upper and lower bounds γUn,p(n) and γLn,p(n) on γn,p(n), respectively, and in addition, we give an upper bound γn,p(n) on γUn,p(n), which is easier to analyze but is still rather accurate. Then, we discuss the asymptotic behavior of γn,p(n) and show that, if p(n) = α/(n − 1), limn→∞ γn,p(n) converges to one of the solutions of the equation 1 − x − e−αx = 0. Furthermore, as for &Rmacr;(n) and &Tmacr;(n), which are upper bounds on the expected number of reachable vertices and the expected size of the transitive closure of G, respectively, it turns out that limn→∞ &Rmacr;(n) = α/(1 − α) if p(n) = α/(n − 1) for 0 < α < 1; otherwise either 0 or ∞, and limn→∞ &Tmacr;(n) = α if p(n) = α/(n − 1)2 for α ≥ 0; otherwise either 0 or ∞.
