What is the probability of randomly generating a tautology?

Question

Suppose we randomly generate a classical Hilbert propositional calculus formula $F$ with $n$ variables, using the following method:

$F = x_i$ for each of $i \leq n$ with probability $\frac{1}{n+2}$.

$F = \neg F_1$, where $F_1$ is generated independently using the same method.

$F = F_1 \to F_2$, where $F_1$ and $F_2$ are generated independently using the same method.

It follows from the extinction criterion for the Galton-Watson branching processes, that the process of generation will terminate with probability $1$ and thus our random formula is well defined.

My question is:

What is the probability that $F$ is a tautology?

It is clearly less, than $\frac{2}{n+2}$. However, it is clearly greater, than $\frac{n}{(n + 2)^3}$ which is the probability of generating a formula of the form $x_i \to x_i$.

Answer 1

Nice question! I doubt that you'll find a closed form for arbitrary $n$, but I'll solve it for $n=1$, and higher values of $n$ could be treated analogously with more effort.

Classify the formulas according to which valuations satisfy them. For $n=1$, that makes $2^{2^1}=4$ different types of formulas: Those that are equivalent to $x_1$, those that are equivalent to $\neg x_1$, the tautologies and the contradictions. Denote the probabilities of generating one of these by $a$, $b$, $c$ and $d$, respectively. Then the recursive generation process implies the following equations:

\begin{eqnarray*} a&=&\frac13(1+b+ca+ba+bd)\;,\\ b&=&\frac13(0+a+cb+ab+ad)\;,\\ c&=&\frac13(0+d+aa+bb+cc+ac+bc+da+db+dc+dd)\;,\\ d&=&\frac13(0+c+cd)\;. \end{eqnarray*}

According to Wolfram|Alpha, this system of equations has a solution

$$ a\approx0.485694\;,\\ b\approx0.226917\;,\\ c\approx0.211531\;,\\ d\approx0.075859\;. $$

Thus, for $n=1$, the probability of generating a tautology is approximately $0.211531$.

Obviously, this will get pretty complicated pretty quickly with increasing $n$, as there are $2^{2^n}$ different classes of formulas to consider. This can be slightly reduced by a factor of about $n!$ by taking into account the symmetry under permutation of the variables, but even just for $n=2$ that leaves $12$ variables.

Answer 2

The probability that a formula generated that way is a tautology is

$$\frac{1}{n^2} + O(\frac{1}{n^3})$$

for large $n$.

To demonstrate this, let's call the probability that our formula is always true as $x$ and that our formula is always false as $y$.

Notice the following facts:

$x_i$ is sometimes true and sometimes false.

$\neg A$ is always true iff $A$ is always false.

$\neg A$ is always false iff $A$ is always true.

$x_i \to A$ is always true iff either $A = x_i$ or $A$ is always true.

$x_i \to A$ is true when $x_i$ is false (which sometimes happens)

$A \to x_i$ is always true iff either $A = x_i$ or $A$ is always false.

$A \to x_i$ is true when $x_i$ is true (which sometimes happens)

THe probability of generating any formula of type different from above mentioned ones is $O(\frac{1}{n^3})$

From this we can derive the following system of equations:

$$x = \frac{y}{n+2} + \frac{n}{n+2}(\frac{n}{(n+2)^2} + x + y) + O(\frac{1}{n^3})$$

$$y = \frac{x}{n+2} + O(\frac{1}{n^3})$$

When solving this system of equations we get $x = \frac{1}{n^2} + O(\frac{1}{n^3})$, Q.E.D.