# Forking Lemma - Statement of The Lemma

Statement of The Lemma

The generalized version of the lemma is stated as follows. Let A be a probabilistic algorithm, with inputs (x, h1, ..., hq; r) that outputs a pair (J, y), where r refers to the random tape of A (that is, the random choices A will make). Suppose further that IG is a probability distribution from which x is drawn, and that H is a set of size h from which each of the hi values are drawn according to the uniform distribution. Let acc be the probability that on inputs distributed as described, the J output by A is greater than or equal to 1.

We can then define a "forking algorithm" FA that proceeds as follows, on input x:

1. Pick a random tape r for A.
2. Pick h1, ..., hq uniformly from H.
3. Run A on input (x, h1, ..., hq; r) to produce (J, y).
4. If J = 0, then return (0, 0, 0).
5. Pick h'J, ..., h'q uniformly from H.
6. Run A on input (x, h1, ..., hJ−1, h'J, ..., h'q; r) to produce (J', y').
7. If J' = J and hJh'J then return (1, y, y'), otherwise, return (0, 0, 0).

Let frk be the probability that FA outputs a triple starting with 1, given an input x chosen randomly from IG. Then