into account: the second proof only adds information if the first one is absent. As they share edge $cd$, this means that edge $ac$ has to be missing, leading to $P_2(path(a,d))=P((ac\wedge cd) \vee (\neg ac \wedge ab\wedge bc
\wedge cd))=0\ldotp72+(1-0\ldotp8)\cdot 0\ldotp378=0\ldotp7956$. Similarly, we obtain $P_3(path(a,d))=0\ldotp8276$ and $P_k(path(a,d))=0\ldotp83096$ for $k\geq 4$.

### Monte Carlo {#sec:mc_method}

As an alternative approximation technique, we propose a Monte Carlo method, where we proceed as follows.

Execute until convergence:

1.  Sample a logic program from the ProbLog program

2.  Check for the existence of some proof of the query of interest

3.  Estimate the query probability $P$ as the fraction of samples where the query is provable

We estimate convergence by computing the 95% confidence interval at each $m$ samples. Given a large number $N$ of samples, we can use the standard normal approximation interval to the binomial distribution:

$$\delta \approx 2\times\sqrt{\frac{P.(P-1)}{N}}$$

Notice that confidence intervals do not directly correspond to the exact bounds used in our previous approximation algorithm. Still, we employ the same stopping criterion, that is, we run the Monte Carlo simulation until the width of the confidence interval is at most $\delta_p$.

A similar algorithm (without the use of confidence intervals) was 