Natural theorems proven only "to high probability"? There are plenty of situations where a randomized "proof" is much easier than a deterministic proof, the canonical example being polynomial identity testing.  

Question: Are there any natural mathematical "theorems" where a randomized proof is known but a deterministic proof is not?

By a "randomized proof" of a statement $P$ I mean that


There is a randomized algorithm that takes an input $n &gt; 0$ and if $P$ is false produces a deterministic proof of $\neg P$ with probability at least $1-2^{-n}$.
Someone has run the algorithm for, say, $n = 100$, and not disproved the theorem.


It's easy to generate non-natural statements that fit: just pick a large instance of any problem where only an efficient randomized algorithm is known.  However, although there a lot of mathematical theorems with "lots of numerical evidence", such as the Riemann hypothesis, I don't know of any with rigorous randomized evidence of the above form.
$
\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\maj}{maj}
$
This is not an example of what you are asking for, but it suggests how such an example can come about. Some combinatorial identities can be encoded as identities about polynomials of bounded degree $d$. If the polynomials are univariate, to prove the identity it is enough to verify it on $d+1$ points. However, if the polynomials are multivariate, and the degree is at least moderately large, the Scwartz-Zippel lemma may be the only practical way to verify the identity.

For an example of the univariate case, check this article by Zeilberger, resolving a question of Knuth. He proves a statement about statistics of permutations. For a permutation $\pi \in S_n$, let $\inv(\pi)$ be the number $|\{(i, j): i &lt; j, \pi(i) &gt; \pi(j)\}|$ of inversions of $\pi$, and let the major index $\maj(\pi)$ of $\pi$  be the sum of all integers in the set $\{i: \pi(i+1) &lt; \pi(i)\}$ . Zeilberger proves that, for all $n$, the covariance of the two statistics is

$$
\mathbb{E}[(\inv(\pi) - \mathbb{E}[\inv(\pi)])\cdot(\maj(\pi) - \mathbb{E}[\maj(\pi)])] = \frac{1}{4}{n \choose 2},
$$
where all expectations are over a uniformly random $\pi$ in $S_n$. Zeilberger's proof is just a computer verification for $n \in \{1, 2, 3, 4, 5\}$, and an observation that the statement is equivalent to an identity between polynomials in $n$ of degree at most $4$.