CounterexampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck pass

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.

The uncorrected Monte Carlo permutation fraction can be zero and invalid

Statement refuted

For every invariant finite-group null and every $B \geq 1$ , the uncorrected fraction ${\tilde{p}}_{B} : = \frac{1}{B} \sum_{b = 1}^{B} 1 {T (g_{b} \cdot X) \geq T (X)},$ with IID uniform $g_{b} \in G$ independent of $X$ , is a valid p-value.

Facts & Assumptions

Given: A finite invariant group model, one IID uniform simulated transformation, and the uncorrected fraction above. Show that it can have positive probability of being zero; compare the identity-corrected value.

[F1]

Measurable finite-group permutation setups: the test premise is invariance of the null law under every group element.

[F2]

Identity-corrected random-permutation Monte Carlo p-value: the corrected with-replacement procedure adds the distinguished identity count and divides by $B + 1$ .

[F3]

Validity of identity-corrected random-permutation Monte Carlo p-values: under the invariant null and with-replacement design, the identity-corrected value is superuniform.

[F4]

Valid p-values: validity requires $P (p (X) \leq u) \leq u$ at every $u \in [0, 1]$ , including $u = 0$ .

[F5]

Finite probability spaces, outcome weights, events, and event probabilities: event probabilities on a finite sample space are sums of the outcome weights.

[F6]

The uniform probability space on a nonempty finite set: a uniform law on the two-element group gives probability $1 / 2$ to each transformation.

[F7]

Independent random elements: the simulated transformation is independent of the observed data.

Counterexample

Take $Ω = {0, 1}$ , let $G = {e, s}$ with $s$ swapping the two points, let $P (X = 0) = P (X = 1) = 1 / 2$ , and set $T (x) = x$ . This law is invariant. Take $B = 1$ and draw $g_{1}$ uniformly from $G$ , independently of $X$ .

Given: The finite model, the group action and score, and the independent uniform draw $g_{1}$ above.

1.1F1F5F6F7givenalgebra

If $X = 0$ , both transformations have score at least $T (X) = 0$ , so ${\tilde{p}}_{1} = 1$ . If $X = 1$ , the identity gives an indicator of $1$ and the swap gives an indicator of $0$ . Therefore ${\tilde{p}}_{1} = 0$ exactly on ${X = 1, g_{1} = s}$ . By [F5], [F6], and independence [F7], this event has probability $(1 / 2) (1 / 2) = 1 / 4$ .

2.1F4step 1.1algebra

Consequently $P ({\tilde{p}}_{1} \leq 0) = 1 / 4 > 0$ , contradicting the necessary superuniform bound [F4]. Thus the uncorrected fraction can equal zero and is anti-conservative at cutoff $0$ .

3.1F2F3step 1.1algebra∎

In the same witness the corrected value is $p_{+} = (1 + 1 {T (g_{1} \cdot X) \geq T (X)}) / 2$ , so it equals $1 / 2$ with probability $1 / 4$ and $1$ with probability $3 / 4$ . Its CDF is $0$ below $1 / 2$ , $1 / 4 \leq u$ for $1 / 2 \leq u < 1$ , and $1$ at $u = 1$ , consistent with the general identity-corrected result [F3].

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

30 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

Jesse Hemerik and Jelle Goeman, Exact Testing with Random Permutations, §3.2 (standard reference, not scraped)
Eugene Katsevich, STAT 9610 Lecture Notes, §3.2.4.2, equations (3.19)–(3.20) (standard reference, not scraped)