What is the probability of randomly generating a tautology? 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$.
 A: 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.
A: 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.
