Probability of randomly finding a loop in a (directed) Bernoulli random graph

Question

This problem is inspired by an activity at work, where each person was tasked with introducing another person in the onboarding class, sequentially.

Problem Statement

• Given $N$ people. For each pair of people $(i, j)$, we have that $i$ knows $j$ with probability $p$.
• The people introduce each other in the following way:
  • A uniformly random person starts the loop as the introducer.
    • This initial person cannot be introduced until the very last step.
  • At each step, the introducer picks another person whom they know, and has not yet been introduced, and is not the initial person, uniformly at random, and introduces them.
  • The introduced person then continues the loop.
    • The last person introduces the initial person (if they know them) to close the loop.

What is the probability, $q(N,p)$, that this loop terminates?

My try

I simulated some scenarios, summarised by the below heatmap.

It is easy to see that $q(N,p) \le p^2$ because the penultimate introduce only has one possible candidate to introduce (i.e. the remaining person that is not the initial person), and the last introducer also only has one possible candidate to introduce (i.e. the initial person). In fact, for large $p$, this bound seems very tight and $q$ doesn't really depend on $N$, because it is unlikely to fail the loop before the last two steps. However, for small $p$ (also more interesting and realistic), this bound is loose, and dependency on $N$ kicks in.

Related question (Just for interest -- no need to answer it)

Consider the following modification of our "introduction" algorithm: if someone has no valid person to introduce (i.e. they know none of the other non-introduced, non-initial people), then they will randomly pick another (non-introduced, non-initial) person to continue the loop, and we increment the failure counter by $1$.

It is interesting to find the expected number of failures, $e(N,p)$, in this algorithm.

My question to the community

Is there some nice (even if not closed-form) way to compute $q(N,p)$ in a non-Monte Carlo way? Are there nice bounds? Is there literature on this? Thank you!

Answer 1

For $i=1,\dots, N$, define $p_i$ so that if we have successfully reached the $i$-th person of the loop, then we can continue from the $i$-th person to the $i+1$-th person with probability $p_i$. We have that $p_N =p$, and $p_i = 1-(1-p)^{N-i}$ for $i=1,\dots,N-1$.

Consequently, writing $q=1-p$, your desired probability is $\prod_{i=1}^N p_i = p\prod_{i=1}^{N-1}(1-(1-p)^{N-i}) = p\prod_{i=1}^{N-1}(1-q^i)$. I'll leave you to work out the asymptotics.