ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Median queries identify a finite threshold by binary search

Example

Fix $n \geq 1$ and ordered distinct points $X = {x_{1} < \dots < x_{n}}$ with sigma-algebra $2^{X}$ . Let $D_{X}$ be any probability measure on $(X, 2^{X})$ , let $H = {h_{k} : 0 \leq k \leq n}$ with $h_{k} (x_{j}) = 1$ exactly when $j > k$ , take the pool $U = (x_{1}, \dots, x_{n})$ , target $h_{k^{*}}$ for some $k^{*} \in {0, \dots, n}$ , and exact oracle $O (x_{j}) = h_{k^{*}} (x_{j})$ . Consider the adaptive median selector that maintains the candidate interval $[a, b] \subseteq {0, \dots, n}$ , initially $[0, n]$ ; while $a < b$ , it sets $s = b - a + 1$ , queries $x_{j}$ with $j = a + ⌊ s / 2 ⌋$ , and retains the threshold indices matching the returned label. It stops when one candidate remains. This selector identifies $k^{*}$ in at most the least integer $q \geq 0$ such that $2^{q} \geq n + 1$ queries. It is a separate median-query rule; the A-page procedure scans the fixed pool in ascending order.

Example references

Finite pool-based realizable active-learning instance: supplies the finite-class, ordered-pool, target, and exact-oracle conventions used here.

Daniel Joseph Hsu, Algorithms for Active Learning, Chapter 1 §1.2

Illustration

For $n = 7$ , each internal node is the queried pool point, each edge is its exact binary label, and each terminal label is the remaining threshold-index interval. Thus $x_{4}$ splits $[0, 7]$ evenly; the next median queries $x_{2}$ or $x_{6}$ . The figure records only these first two levels; the proof below establishes the general branch sizes and query bound without relying on the diagram.

diagram failed to render:
\begin{tikzpicture}[
  level distance=15mm,
  sibling distance=43mm,
  every node/.style={draw, rounded corners, align=center, font=\small},
  edge from parent/.style={draw, -latex}
]
\node {query $x_4$\\ $[0,7]$}
  child { node {query $x_2$\\ $[0,3]$}
    child { node {$[0,1]$} edge from parent node[left,draw=none] {$1$} }
    child { node {$[2,3]$} edge from parent node[right,draw=none] {$0$} }
    edge from parent node[left,draw=none] {$1$}
  }
  child { node {query $x_6$\\ $[4,7]$}
    child { node {$[4,5]$} edge from parent node[left,draw=none] {$1$} }
    child { node {$[6,7]$} edge from parent node[right,draw=none] {$0$} }
    edge from parent node[right,draw=none] {$0$}
  };
\end{tikzpicture}

Facts & Assumptions

Given: The finite threshold instance and adaptive median selector stated in the Example.

[F1]

Finite pool-based realizable active-learning instance: the pool is a finite ordered list, the target belongs to the finite classifier class, and each oracle response equals the target label at the queried point.

Verification

1.1givenF1algebra

Suppose the current candidate interval is $[a, b]$ with $s = b - a + 1 \geq 2$ . Then $j = a + ⌊ s / 2 ⌋$ satisfies $a < j \leq b$ . Among candidate indices, the label at $x_{j}$ is $1$ exactly for $k < j$ , namely $k \in [a, j - 1]$ , and is $0$ exactly for $k \geq j$ , namely $k \in [j, b]$ . These branches have sizes $⌊ s / 2 ⌋$ and $⌈ s / 2 ⌉$ . By [F1], the exact oracle retains the branch containing $k^{*}$ , so the target remains in the updated interval and the new size is at most $⌈ s / 2 ⌉$ .

2.1givenstep 1.1algebra∎

Starting from $s_{0} = n + 1$ , repeated ceiling-halving gives $s_{r} \leq ⌈ (n + 1) / 2^{r} ⌉$ : if this holds at $r$ , then $s_{r + 1} \leq ⌈ s_{r} / 2 ⌉ \leq ⌈ (n + 1) / 2^{r + 1} ⌉$ . For the least $q$ with $2^{q} \geq n + 1$ , this bound is at most $1$ . Since the target remains in the interval by step 1.1, the selector stops with the singleton ${k^{*}}$ after at most $q$ queries.

Depends on

Finite pool-based realizable active-learning instance

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

3 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Daniel Joseph Hsu, Algorithms for Active Learning, Chapter 1 §1.2 (standard reference, not scraped)