Note, I have not read the paper in detail yet, I just want to explain certain statistical proof techniques which are quite counter-intuitive to me, and maybe help you :)
You can, for example, show the probabilities of certain properties of an algorithm and use these probabilities in order to show the possibility of something existing or the absence of something. Furthermore, you can for example use the expected value of a certain process to demonstrate that solutions with a certain value exist.
For example, if you are able to demonstrate that the expected value of a maximum cut is 5 for a family of graphs, then you can conclude that there are maximum cuts in this family of graphs which have the value of at least 5. There are some with less, and there are some with more, but cuts with weight more than 5 exist.
Or, for example, if you can demonstrate that the probability of a turing machine in a certain class accepting or rejecting after a polynomial time of steps is 0, then it is impossible that this class is identical to P. On the other hand, if it is possible to demonstrate that this probability is not 0 (and thus larger), then we demonstrated that the cut of this class and P is nonempty.
You can, for example, show the probabilities of certain properties of an algorithm and use these probabilities in order to show the possibility of something existing or the absence of something. Furthermore, you can for example use the expected value of a certain process to demonstrate that solutions with a certain value exist.
For example, if you are able to demonstrate that the expected value of a maximum cut is 5 for a family of graphs, then you can conclude that there are maximum cuts in this family of graphs which have the value of at least 5. There are some with less, and there are some with more, but cuts with weight more than 5 exist.
Or, for example, if you can demonstrate that the probability of a turing machine in a certain class accepting or rejecting after a polynomial time of steps is 0, then it is impossible that this class is identical to P. On the other hand, if it is possible to demonstrate that this probability is not 0 (and thus larger), then we demonstrated that the cut of this class and P is nonempty.