Hybrid distributions for finite binary generators -- definitions

The cut-th hybrid uses generator output in coordinates strictly below cut and independent uniform bits in the remaining coordinates. Both sources of randomness are packed into one Boolean string, so every probability remains an exact eventProb over a finite dyadic sample space.

Complementing a test records the one-bit polarity choice used to orient an absolute distinguishing advantage before applying the hybrid argument.

def Complexity.BitGenerator.orientTest {outputLength : ℕ} (test : Finset (Fin outputLength → Bool)) (complement : Bool) : Finset (Fin outputLength → Bool)

Optionally complement a finite test. The Boolean parameter is the polarity bit used to orient an absolute distinguishing gap.

Equations

• Complexity.BitGenerator.orientTest test complement = if complement = true then testᶜ else test

def Complexity.BitGenerator.hybridOutput {seedLength outputLength : ℕ} (generator : BitGenerator seedLength outputLength) (cut : ℕ) (randomness : Fin (seedLength + outputLength) → Bool) : Fin outputLength → Bool

The cut-th hybrid between uniform output bits and the generator output. Coordinates below cut come from the generator; all later coordinates are independent uniform bits.

Equations

• One or more equations did not get rendered due to their size.

def Complexity.BitGenerator.hybridAcceptedRandomness {seedLength outputLength : ℕ} (generator : BitGenerator seedLength outputLength) (test : Finset (Fin outputLength → Bool)) (cut : ℕ) : Finset (Fin (seedLength + outputLength) → Bool)

Combined random strings whose cut-th hybrid output is accepted.

Equations

• generator.hybridAcceptedRandomness test cut = {randomness : Fin (seedLength + outputLength) → Bool | generator.hybridOutput cut randomness ∈ test}

def Complexity.BitGenerator.hybridAcceptanceProbability {seedLength outputLength : ℕ} (generator : BitGenerator seedLength outputLength) (test : Finset (Fin outputLength → Bool)) (cut : ℕ) : ℚ

Acceptance probability of a test under the cut-th hybrid.

Equations

• generator.hybridAcceptanceProbability test cut = Complexity.eventProb (generator.hybridAcceptedRandomness test cut)

def Complexity.BitGenerator.hybridGap {seedLength outputLength : ℕ} (generator : BitGenerator seedLength outputLength) (test : Finset (Fin outputLength → Bool)) (step : ℕ) : ℚ

Change in test acceptance when one more output coordinate is switched from uniform to generated.

Equations

• generator.hybridGap test step = generator.hybridAcceptanceProbability test (step + 1) - generator.hybridAcceptanceProbability test step