2
$\begingroup$

Question: What's a standard name/framework for the following, or some variant?

Stated briefly for a probabilistic algorithm: define $p_n$ as the conditional probability of success of a fork of the algorithm after it consumed $n$ bits of randomness, knowing the other fork succeeded.

Claim: $p_n$ is non-decreasing.


Stated more in detail for a fixed deterministic sequential algorithm which input is a bitstring, that it consumes bit by bit, at most one bit at each execution step. Each run of the algorithm has the same fixed limit $t$ on the number of steps (yielding a time limit for constant step frequency), and the algorithm is aborted if it did not succeed within this limit. The outcome of any run is success or abort. Assume the algorithm aborts if it's input is shorter than what the algorithm requests.

If the algorithm succeeds for bitstring $b$, then it succeeds for $b\mathbin\|0$ and for $b\mathbin\|1$ (and won't read the extra $0$ or $1$ bit). If the algorithm aborts for bitstring $b$ with length $\lvert b\rvert\ge s$, then it aborts for $b\mathbin\|0$ and for $b\mathbin\|1$ (and won't read the extra $0$ or $1$ bit).

Assume there exists a bitstring such that the algorithm succeeds.

For an integer $n$, define $p_n$ as the probability the algorithm succeeds in the second part of this experiment:

  • we repeatedly run the algorithm, with as many uniformly random independent input bits as it requests, until we find one input bitstring $b$ such that the algorithm succeeds;
  • we once more run the algorithm, with input the first $n$ bits of $b$, then as many uniformly random independent input bits as the algorithm requests.

In this experiment, the algorithm never aborts because it's input is shorter than what the algorithm requests. When $n$ is larger than $\lvert b\rvert$, the last run succeeds after all the bits of $b$ have been input, since the previous run did, and the algorithm is deterministic. It follows: $n\ge t\implies p_n=1$.

Claim: $p_n$ is non-decreasing. That follows from this simpler proposition, applied to the set of $t$-bit bitstrings that make the algorithm succeed.


I find this theorem useful in some proofs of cryptographic security, usually made with a more complex argument. See the motivating context.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.