What does it mean for a theorem to be "almost surely true", in a probabilistic sense? (Note: Not referring to "the probabilistic method")

First of all, the phrase "almost surely true" or its equivalent "true with probability 1" has a technical and well defined meaning for results with some probability aspect. It means that although there may be examples involving specification of an infinite set of items which violate the statement, the probability measure of the collection of such sets is zero. A good example is the statement that a balanced random walk in 1 dimension will return to the origin almost certainly -- you can of course construct sequences (e.g., all +1 steps) that do not, but with probability 1 a random sequence will return to 0.

Next, there are some statements in number theory, typically involving distributions of primes, which have been proven in a limit/probabilistic sense. These statements general sound like "there exists some sufficiently large $N$ that for all intervals of length greater than $N$ the occurence of is rarer than . Some authors then say that the proposition is "almost surely true."

The statement you have encountered is weaker yet. It says that given some known distribution properties (again, of the primes) and other small-number information, the author can prove that the probability of a violation of the conjecture is less than that tine $\epsilon$, *assuming the pseudo-random distribution of the primes is not correlated with the properties that would affect Goldbach's conjecture."

For example, if we were to substitute the "conjecture" that there are no nontrivial tuples such that $a^3 + b^3 + c^3$ we might be able to say, based on knowing the conjecture is true for numbers below a million, and assuming the cubes are distributed randomly with a density $1/3n^2$, that the probability of that conjecture being false is less than 0.1.

Obviously, the interesting thing about this author's work is the incredibly tiny heuristic probability.