BN06 General Forking Lemma

Fix an integer  and a set  of size  Let  be a randomized algorithm that on input returns a pair, the first element of which is an integer in the range  and the second element of which we refer to as a side output. Let IG be a randomized algorithm that we call the input generator. The accepting probability of , denoted , is defined as the probability that  in the experiment

The forking algorithm  associated to  is the randomized algorithm that takes input  proceeds as follows:

Let

Alternatively,

:

For any input  let  denote the probability that  in the experiment

Also let

For any input , with probabilities taken over the coin tosses of  we have

Let  denote the set from which  draws its coins at random. For each  let  be defined by setting  to

for all  and  Regard  as a random variable over the uniform distribution on its domain. Then

So we get 

Taking the square root of both sides, and using the fact that  for any real numbers we get

So we get