Type-II Error Exponents in Distributed Hypothesis Testing

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

Distributed binary hypothesis testing distinguishes two specified joint data laws, $P$ under $H_0$ and $Q$ under $H_1$, from length-$n$ observations split among terminals. Communication is over noiseless links with a prescribed rate budget. Type-I error is $\alpha_n=\Pr_P[\text{decide }H_1]$ and type-II error is $\beta_n=\Pr_Q[\text{decide }H_0]$. At a fixed admissible type-I error level, the type-II exponent is $\liminf_{n\to\infty}-n^{-1}\log\beta_n$. The one-sensor model sends a message to a decision center; interactive two-sensor protocols permit messages depending on previous messages.

Statement recorded in the supplied source.

Determine the optimal type-II error exponent for rate-limited distributed hypothesis testing and for its interactive two-sensor variant. [S2]

Scope qualification.

Resource constraints, including expected versus maximum communication length, follow the cited testing model. General joint laws are requested; special testing-against-independence results are not asserted to settle them.

Source status.

The supplied catalogue labels this record open. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-22.

Short English statement

Find the best exponential decay of false acceptance of the null hypothesis when observations are distributed and communication is limited.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30005061 (OWR-9790365-011). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 New Mathematical Techniques in Information Theory $2023$, Oberwolfach Reports, DOI 10.4171/owr/2022/14, pp. 683--707 https://doi.org/10.4171/owr/2022/14.
• S3 Salehkalaibar--Wigger, variable-length distributed testing https://arxiv.org/abs/2005.08610. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Preparation and review.

Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30005061 and source code OWR-9790365-011 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Literature and context check

The primary report, p. 698, explicitly distinguishes known testing-against-independence cases from its general-law and interactive questions. It also distinguishes maximum from expected communication resources. The following elementary example works through both distinctions; it is not a solution for general joint laws.

Research attempt: An exact independence example and the expected-length distinction

Under $H_0$, let $X^n=Y^n$ be a uniform binary string; under $H_1$, let $X^n,Y^n$ be independent uniform binary strings. A deterministic sensor partitions the $2^n$ strings into at most $M$ cells $C_j$, sending the cell index. The detector sees that index and $Y^n$. Allow a randomized decision, with probability $a_j(y)\in[0,1]$ of accepting $H_0$. Put $t_j=\sum_{y\in C_j}a_j(y)$. If type-I error is at most $\epsilon<1$, then \[ \sum_jt_j\geq(1-\epsilon)2^n. \] Under independence, \[ \beta={1\over4^n}\sum_j |C_j|\sum_y a_j(y) \geq {1\over4^n}\sum_j |C_j|t_j \geq {1\over4^n}\sum_jt_j^2 \geq{(1-\epsilon)^2\over M}. \tag{2} \] The middle step uses $t_j\leq|C_j|$; the last is Cauchy--Schwarz. Empty cells cause no problem. Thus for $0\leq R\leq1$ and $M\leq2^{nR}$, the type-II exponent is at most $R\log2$. Sending the first $\lfloor nR\rfloor$ bits and accepting precisely when they match the corresponding bits of $Y^n$ gives $\alpha=0$, $\beta=2^{-\lfloor nR\rfloor}$, and exponent $R\log2$. This proves the optimum in this explicitly deterministic one-way fixed-length model. With no communication, the identical marginal law of $Y^n$ also directly gives $\beta=1-\alpha\geq1-\epsilon$.

Now permit expected length at most $nR$, and private randomness at the sensor. Fix $0<\epsilon<1$ and $0<R<1-\epsilon$. With probability $\epsilon$ send a one-bit flag directing immediate rejection of $H_0$. Otherwise send the other flag followed by \[ \ell_n=\min\{n,\lfloor(nR-1)/(1-\epsilon)\rfloor\} \] initial bits of $X^n$; for sufficiently large $n$ this is nonnegative. The detector compares these bits to its own string. The messages form a prefix-free family: one branch is a single bit, and all messages in the other branch have the same length $1+\ell_n$. The expected length is exactly $1+(1-\epsilon)\ell_n\leq nR$. Its errors are \[ \alpha=\epsilon,\qquad \beta=(1-\epsilon)2^{-\ell_n}, \] so its exponent is $R\log2/(1-\epsilon)$, strictly greater than $R\log2$. The one-bit flag is included in the resource accounting. Thus importing $2$ as a converse for expected-length messages would be a concrete error: $2$ uses a bound on the total number of possible messages, which an expected-length constraint does not supply.

Verification and adversarial audit

For $R=0$ the fixed-length formula agrees with the marginal indistinguishability argument. For $R=1$ sending the entire string gives exponent $\log2$. The expected-length comparison restricts $0<R<1-\epsilon$ so that its claimed strict improvement does not exceed the full-observation exponent. Equation $2$ is proved for deterministic encoders; no unproved extension to randomized or interactive encoders is needed for the stated auxiliary theorem.

Audit corrections.

Maximum message count and expected length are not interchanged. A private random choice and its transmitted flag are explicitly costed; the known independence special case is identified as such.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

Neither the fixed-length independence calculation nor the explicit variable-length construction characterizes general $P,Q$, the general expected-resource optimum, or interactive two-sensor testing. The original target remains unresolved in this attempt.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://ems.press/content/serial-article-files/46950 (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration and repository-format review; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved as a new research contribution. This is a concrete route investigation, not a claim of new complete resolution or a current-status certification. A known answer reproduced for context does not become a new contribution. The catalogue's source-status label is preserved; this attempt status does not assert that a source-labelled solved question is open.