Reference. Finite discovery and support [ftip-00I4]
✍️source

For finite discovery probabilities, rollout budgets, and support-preserving changes of law, see § [ftip-0076].

Related

Finite discovery and support [ftip-0076]

A successful continuation can have positive probability and still be difficult to observe within a finite rollout budget. This subsection separates the probability of observing a success from support, coverage, and capability acquisition.

Convention. Repeated attempts and the discovery event [ftip-0077]

Fix a task instance, evaluator, success threshold, and a joint law for \(B\geq 1\) attempts. Let \(E_i\) be the event that attempt \(i\) succeeds. The discovery event by attempt \(B\) is

\[ D_B=\bigcup _{i=1}^{B}E_i. \]

Write \(p_i=\Pr (E_i)\). Independence is an additional property of the declared joint law; it is not implied by repeated decoding, a shared model, or a common environment. In the independent and identically distributed case, write \(p_i=p\). When the attempt law is the one fixed in Definition [ftip-005U], this \(p\) is the corresponding successful-support probability.

Theorem. Discovery under independent attempts [ftip-0078]

Assume the events \(E_1,\ldots ,E_B\) of Convention [ftip-0077] are independent. Then

\[ \Pr (D_B)=1-\prod _{i=1}^{B}(1-p_i). \]

In particular, independent attempts with a common success probability \(p\) satisfy

\[ \Pr (D_B)=1-(1-p)^B. \]

Proof.

The complement of discovery is \(D_B^{\mathsf c}=\bigcap _{i=1}^{B}E_i^{\mathsf c}\). Independence gives \(\Pr (D_B^{\mathsf c})=\prod _i\Pr (E_i^{\mathsf c}) =\prod _i(1-p_i)\). Taking complements proves the first identity; substituting \(p_i=p\) proves the specialization.

This finite statement follows from the displayed hypotheses. The calculation in Example [ftip-0067] is its ten-attempt numerical preview.

Corollary. A rollout budget for target discovery probability [ftip-0079]

This is a finite corollary of Theorem [ftip-0078], obtained from its displayed hypotheses.

Let \(0<\delta <1\). Under the independent and identically distributed setup of Theorem [ftip-0078], suppose first that \(0<p<1\). The least positive integer budget whose discovery failure probability is at most \(\delta \) is

\[ B_{\min } =\left \lceil \frac {\log \delta }{\log (1-p)}\right \rceil . \]

If \(p=0\), no finite positive budget reaches failure probability below one. If \(p=1\), one attempt suffices.

Proof.

For \(0<p<1\), Theorem [ftip-0078] gives failure probability \((1-p)^B\). The inequality \((1-p)^B\leq \delta \) is equivalent to \(B\geq \frac {\log \delta }{\log (1-p)}\) because both logarithms are negative. The least integer solution is the displayed ceiling. The two boundary cases follow directly from \((1-p)^B\).

Lemma. Discovery bounds from conditional success rates [ftip-007A]

Put \(D_0=\varnothing \). Whenever \(\Pr (D_{i-1}^{\mathsf c})>0\), define the surviving conditional success rate

\[ q_i=\Pr (E_i\mid D_{i-1}^{\mathsf c}). \]

If these rates are defined through step \(B\), then

\[ \Pr (D_B^{\mathsf c})=\prod _{i=1}^{B}(1-q_i). \]

Consequently, if \(0\leq \underline q\leq q_i\leq \overline q\leq 1\) for every surviving step, then

\[ 1-(1-\underline q)^B \leq \Pr (D_B) \leq 1-(1-\overline q)^B. \]

Proof.

The chain rule gives \(\Pr (D_i^{\mathsf c})=\Pr (D_{i-1}^{\mathsf c})(1-q_i)\). Iteration proves the product identity, and the coordinatewise bounds on \(1-q_i\) give the two discovery bounds.

No independence assumption is used. The conditional rates may change with the earlier failures, an adaptive decoder, or a changing environment state.

This finite statement follows from the displayed hypotheses.

Remark. Discovery is neither acquisition nor coverage [ftip-007B]

The discovery event concerns whether a declared sampling procedure observes at least one success. Increasing its probability can be an elicitation effect in the sense of Definition [ftip-0005]: more attempts expose behaviour that already had positive probability. It is not by itself the independent before--after comparison required by Definition [ftip-0007].

Successful-support coverage in Definition [ftip-005V] integrates an instance-level threshold over a task law. A large discovery probability on one instance therefore does not establish broad coverage or the uniform task-family witness of Definition [ftip-005X].

Theorem. Finite exponential tilting preserves support [ftip-007C]

Fix a prompt \(x\), a finite response set \(\mathcal Y\), a reference policy \(\pi _{\mathrm {ref}}\), a finite real reward \(r(x,y)\), and \(\beta >0\). Let \(\pi _r\) be the normalized exponential tilt of Definition [ftip-003O]. Then, for every \(y\in \mathcal Y\),

\[ \pi _r(y\mid x)>0 \quad \Longleftrightarrow \quad \pi _{\mathrm {ref}}(y\mid x)>0. \]

Proof.

The multiplier \(\exp (r(x,y)/\beta )\) is finite and strictly positive. The finite normalizer \(Z_r(x)\) is also strictly positive. Multiplication by the first quantity and division by the second therefore preserve whether the reference mass is zero or positive.

The source policy form appears as equation (4) in [rafailov2023direct, Section 4]; the displayed result is the finite corollary derived here. Infinite rewards, non-normalizable response spaces, approximate optimization, and changes to the generation mechanism lie outside the statement.

Remark. Formal support and operational discoverability [ftip-007D]

Support preservation is a statement about exact positive probability. A response can remain in mathematical support while its mass becomes too small to observe within the available rollout budget. The identities in Theorem [ftip-0078] and Corollary [ftip-0079] quantify this distinction for declared independent attempts.

Top-\(k\) truncation, nucleus sampling, finite numerical precision, context limits, and parser constraints can also remove an operational route even when the underlying softmax law assigns it positive mass. Claims about elicitation must therefore name both the policy law and the executable inference procedure.

Example. Counterexample: Equal one-shot success, unequal successful coverage [ftip-007E]

Let the evaluation law be uniform on two instances \(x_1,x_2\). Consider protocols \(P\) and \(P'\) with successful-support probabilities

\[ \bigl (p_P(x_1),p_P(x_2)\bigr ) =\left (\frac 12,\frac 12\right ), \qquad \bigl (p_{P'}(x_1),p_{P'}(x_2)\bigr ) =(1,0). \]

Both protocols have mean one-shot success \(1/2\). At threshold \(\alpha =1/2\), however, Definition [ftip-005V] gives

\[ \operatorname {Cov}_{1/2}(P)=1, \qquad \operatorname {Cov}_{1/2}(P')=\frac 12. \]

Thus average success does not determine successful-support coverage. The example is finite and uses the same task law and threshold for both protocols; it does not compare their training costs or establish acquisition.