{"id":"37d67f68-8123-461d-a247-144a21af7567","arxiv_id":"2502.07566","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For the binary energy harvesting channel, the authors provide convex optimization formulations of Q-graph lower and upper bounds that converge to the capacity with an O(1/N) gap, enabling capacity computations to 1e-6 precision.","lead":"This paper gives the first computable capacity bounds for the binary energy harvesting channel (BEHC), a noiseless channel with a unit battery and random energy arrivals, by expressing lower and upper bounds as convex optimization problems. The bounds tighten to the true capacity with a controlled gap, so capacity can be computed to any desired precision for any harvesting probability.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: inequality (62) in Theorem 6 is the least-secure step, but direct computation of the two Q-chain stationary distributions confirms it, so the convergence claim stands.","rationale":"The central claim is the computable capacity via converging convex lower and upper bounds. The only step that is both essential and compressed is (62). We verified it analytically: the stationary distribution of a birth-like chain with reset at N is \\pi_q = \\pi_0 \\prod_{j<q} r_j, and the upper bound's self-loop only increases \\pi_N and decreases all \\pi_q for q<N. The gap bound then follows. The concavity of the upper-bound objective is also valid because the auxiliary U is defined so that P(S|U,Q) equals the fixed conditional (20) at every time, not just in stationarity, though this pointwise justification is not stated explicitly. Both concerns are presentation-level, not correctness-level. The verdict should remain ACCEPT/UNCHANGED.","tokens_in":27197,"tokens_out":53527,"duration_ms":454011,"concrete_test":"Implement the two-state Q-chain recursions from Theorem 6 for arbitrary N and arbitrary transition probabilities r_q in [0,1] and p0 in [0,1]; compute the stationary distributions using the closed forms above and verify \\pi^U_q \\le \\pi^L_q for q<N and \\pi^U_N \\ge \\pi^L_N. Also run a random search over r_q,p0 for N up to 10 to confirm no violation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader flags inequality (62) in Theorem 6: for the optimal upper-bound Q-graph distribution \\bar P^* and the constructed lower-bound distribution \\tilde P, one needs \\bar P^*_Q(q) \\le \\tilde P_Q(q) for q<N, stated as \"as a result\" of the self-loop difference at node N. This is load-bearing for the O(1/N) gap and hence for the claimed 1e-6 precision. Independent verification: for q<N both Q-chains share the same transition probabilities r_q = P(X=0|q); the remaining upper-bound chain at N has self-loop probability p=1-p0 with p0=P(U^+=0|N), while the lower-bound chain resets to 0 with probability 1. Writing the stationary distribution in closed form gives \\pi_q = \\pi_0 \\prod_{j<q} r_j for q<N, \\pi_N^L = \\pi_0 D, \\pi_N^U = \\pi_0 D/(1-p), D=\\prod_{j<N} r_j. This yields \\pi_0^U \\le \\pi_0^L and hence (62). No counterexample found; the terse proof in the paper is correct but under-explained.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the noiseless binary energy harvesting channel (BEHC) with a unit-sized battery and i.i.d. Bernoulli(η) energy arrivals. Its main contribution is a computable characterization of the capacity: a lower bound obtained by specializing the Q-graph lower bound of [26] to an N+1-node Q-graph, and an upper bound obtained from a modified 'boosted' channel that charges the battery after N consecutive zeros. Both bounds are formulated as convex optimization problems (Eqs. (26) and (28)), and the paper proves that the two optimal values converge to the same limit, with a gap bounded by max_p H(p)/(Np+1). Numerical capacities for η ∈ {0.1,...,0.9} are reported to six decimal places in Table I, improving the bounds of [14]. The paper also uses an MDP/value-iteration approach to compute achievable rates for the noisy BEHC with feedback over a binary symmetric channel.","tokens_in":27417,"tokens_out":23950,"duration_ms":222305,"significance":"This is a substantial contribution: it converts the previously uncomputable multi-letter capacity expression for the BEHC into a genuinely computable convex optimization problem, and it supplies the first Q-graph upper bound for this channel, via the boosted-channel construction. The paper is transparent about building on the general Q-graph lower bound of [26], and it provides public MATLAB code for the numerical results. I specifically checked the step flagged in the stress-test note, inequality (62) in Theorem 6: writing the stationary distributions of the two Q-chains in closed form confirms that ̄P*_Q(q) ≤ ̃P_Q(q) for q<N, so the convergence proof's load-bearing inequality is sound. The main weaknesses are an incorrect asymptotic-order statement in the abstract/Remark 2 and a few local proof gaps that are readily fixable; they do not undermine the central claim.","major_comments":[{"comment":"The paper states that the gap between the bounds vanishes as O(N), and Remark 2 writes ψ(N)=O(N). This is inconsistent with Eq. (61), which gives b_N - a_N ≤ max_p H(p)/(Np+1) =: ψ(N). Since ψ(N) tends to 0 — in fact the current bound gives ψ(N)=O(log N / N), not O(N) — the advertised central claim of a vanishing gap is misstated in all three locations. Please correct the asymptotic notation uniformly.","section":"Abstract; Section III (p. 4); Remark 2, Eq. (64)"},{"comment":"The induction proving π(S=0|u,q) = ̅η^{u+1} does not explicitly cover the case q=N with u>0. This case is needed because the convex formulation (26) and the policy constraints (24) require π(·|u,N) for every u∈[0:N]. The missing case follows by the same predecessor argument, since (u,N) can only be reached from (u-1,N-1) with X=0, but as written the proof of Theorem 2 is incomplete at this point. Please add the missing induction step.","section":"Lemma 4, Section V-A"}],"minor_comments":[{"comment":"\"For the sequence of solutions to the convex optimization problems (28) for the lower bound\" should refer to problem (26), not (28), for the lower bound.","section":"Theorem 6, first paragraph"},{"comment":"The passage \"we set |̃U(Q=N)|=0\" followed immediately by \"we set ̃U(Q=N)=[0:N]\" is internally inconsistent. The final auxiliary sets (38) are clear, but the proof should explain that the variable ̃U_{i-1} is retained at Q=N only as a dummy for stationarity.","section":"Theorem 5, Step 3, Section V-B"},{"comment":"The Markov-chain step in Eq. (66)(b) is delegated to \"an identical derivation of [30, Lemma 21]\" without reproducing the argument. Since this chain is used in the upper-bound proof, please expand the derivation or state the referenced lemma explicitly.","section":"Appendix A, proof of Lemma 7"},{"comment":"The claim C_BEHC < ̅C_BEHC(N) should be relaxed to C_BEHC ≤ ̅C_BEHC(N), since equality can occur in degenerate cases such as η=1; the upper-bound argument only needs the non-strict inequality.","section":"Section V-B, before Lemma 5"},{"comment":"The notation ̄I_{̄P*} is used before being defined; please define it explicitly as the conditional mutual information evaluated under the distribution ̄P*.","section":"Eq. (61), Step (e)"}],"recommendation":"minor_revision","confidential_remarks":"No confidentiality concerns. The manuscript fits the journal's scope and the numerical claims are backed by public code. My recommendation of minor revision is driven by the asymptotic-order typo and the small proof gaps listed above, not by any doubt about the correctness of the central result."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline result is real: for the noiseless BEHC, the authors derive convex lower and upper bounds that provably converge to capacity, with the gap bounded by max_p H(p)/(Np+1). The earlier literature only had multi-letter expressions or non-tight numerics, so this is a genuine advance within information theory and energy harvesting. The table shows they beat the prior bounds for every eta and reach 1e-6 precision.\n\nThe paper does several things well. The lower bound inherits the Q-graph framework from their prior work, and the BCJR-invariance check in Lemma 3 is careful. The upper bound is the real novelty: a boosted channel that is not itself an FSC, but which they reformulate as one by adding a Q-state, then bound via the standard converse. The convex formulations are explicit enough to be reproducible, and they ship code. The convergence proof is the load-bearing part, and I checked the terse inequality (62): the stationary-distribution comparison between the two Q-chains is valid because the transition probabilities for q<N match and the only difference at node N is the self-loop, which makes the closed-form comparison go through. The stress-test note confirms this; the claim of a vanishing gap is correct, despite the abstract's sloppy \"O(N)\" phrasing.\n\nSoft spots are minor. The abstract says the gap \"vanishes as O(N)\", which is backwards and should be fixed to O(1/N). Lemma 4 omits a proof step (Step (d)) that is asserted rather than shown; it is believable but a referee will want the detail. The proof of Theorem 6 is dense, especially the construction in (55)-(57), and the monotonicity argument is compressed. None of this undermines the central result.\n\nThe main limitation, acknowledged by the authors, is that the upper-bound technique does not generalize to arbitrary EH models; it relies on the special structure of the BEHC. That is fine, since the paper's claim is about the BEHC. The noisy-channel section is explicitly preliminary: achievable rates from an MDP, no upper bounds, and the results are not deeply discussed.\n\nThis deserves a serious referee. It resolves an open problem, the math mostly holds, and the numerical claims are reproducible. The presentation issues are fixable. I would recommend acceptance after minor revision, and I would cite it.","headline":"This paper gives the first computable capacity bounds for the binary energy harvesting channel, and the convergence proof holds up under scrutiny; send it to review.","tokens_in":27946,"tokens_out":584,"would_cite":true,"duration_ms":8221,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","94A24","94A40","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"For the noiseless binary energy-harvesting channel, the paper proves that capacity can be computed to any desired precision by solving two convex optimization problems whose gap vanishes as $1/N$.","keywords":["binary energy harvesting channel","channel capacity","finite-state channel","convex optimization","Q-graphs","feedback capacity","directed information","energy harvesting"],"falsifier":"Run the convex programs (26) and (28) for $\\eta=0.05$ at $N=10{,}000$ and check whether the gap exceeds $\\max_p H(p)/(Np+1) \\approx 10^{-3}$; a violation, or a direct violation of the monotonicity inequality (62) for any $N$, would refute the claimed $O(1/N)$ convergence.","tokens_in":26987,"feed_emoji":"🔋","tokens_out":5058,"duration_ms":42942,"temperature":0.7,"pith_summary":"The paper claims that the capacity of the binary energy-harvesting channel—a unit-sized battery, binary inputs, random energy arrivals, noiseless output—can be pinned down to any specified precision, something no earlier capacity expression achieved in computable form. It constructs two sequences of single-letter bounds, a lower bound and an upper bound, each obtained by optimizing over an $N$-node auxiliary directed graph called a Q-graph. The two sequences squeeze the true capacity from below and above, and the gap between them is at most $\\max_p H(p)/(Np+1)$, which goes to zero as $N$ grows. This gives a practical recipe: pick $N$ to meet a target accuracy, run the convex programs, and read off the capacity. The paper demonstrates the recipe for every $\\eta \\in \\{0.1,\\dots,0.9\\}$, reporting $10^{-6}$ precision and tightening the best previously published bounds for all of them.","feed_headline":"Capacity of energy-harvesting channel pinned down to 1e-6","feed_subtitle":"A pair of convex bounds squeeze the true rate between them, with a gap that shrinks as 1/N for every harvesting probability.","key_machinery":"The load-bearing object is the Q-graph: a directed graph with $N+1$ nodes, node $q$ recording 'q consecutive zeros have been sent since the last 1'. Each node has outgoing edges labeled by the transmitted symbol $X=0$ or $X=1$, and the graph's transitions define the auxiliary variable $Q$ in the single-letter bounds. The lower bound uses the graph where the $X=0$ edge from node $N$ returns to node $0$; the upper bound uses the graph where that edge self-loops at node $N$, which makes the capacity of a modified 'boosted' channel that dominates the original. The auxiliary random variable $U(Q=q)=\\{0,\\dots,q\\}$ encodes the time since the encoder last attempted a $1$, and the strategy $f(U^+,S)=S\\cdot\\mathbf{1}\\{U^+=0\\}$ sends a $1$ only when the battery is full and the policy chooses $U^+=0$. The machinery turns the capacity problem into two finite-dimensional convex programs with $O(N^2)$ linear constraints, whose objectives are conditional mutual informations $I(U^+,U;X|Q)$.","core_discovery":"The central discovery is that the notoriously hard noiseless binary energy-harvesting channel admits a computable capacity expression in the form of a limit of convex programs. The encoder's battery state is a finite-state channel state known causally to the encoder; the difficulty is that the state process has unbounded memory because a run of zeros can be arbitrarily long. The paper's key move is to truncate that memory to the last $N$ inputs, encoded as a Q-graph with $N+1$ nodes whose transitions track the number of consecutive zeros since the most recent transmitted one. For the lower bound, the last node sends a zero back to node $0$; for the upper bound, that edge becomes a self-loop, which corresponds to a 'boosted' channel where $N$ consecutive zeros guarantee a charged battery and therefore a channel whose capacity is at least the true one. Both bounds are optimized over a finite auxiliary variable $U$ that records how many steps ago the encoder last attempted to send a $1$, and both optimizations are convex. The upper and lower sequences converge to the same limit because the only discrepancy between them is concentrated at the last node, and the stationary probability of that node is at most $1/(Np+1)$ under any optimal policy. Therefore the capacity equals the common limit, and the gap is bounded by $\\max_p H(p)/(Np+1) = O(1/N)$.","pith_inferences":["The same truncate-and-squeeze idea could extend to larger finite batteries and non-binary harvest amounts: the state is still a finite automaton whose memory is a run of zeros, so an $N$-node Q-graph with appropriately adjusted edges may give analogous convex bounds, though the cardinality bound on $U$ would need reworking.","A testable practical consequence is that the achieved precision for small $\\eta$ is limited mainly by the $O(N^2)$ constraint-construction cost, so a sparse or iterative solver could push the method to $N \\gg 10^4$ and sub-$10^{-6}$ precision cheaply.","The upper bound's 'boosted channel' construction—forcing a charge after $N$ consecutive zeros—is a general-purpose upper-bounding trick for any channel with a battery that is guaranteed to fill after enough idle slots; identifying such monotonicity in other state-dependent channels could yield computable upper bounds where none exist.","The equivalence between the auxiliary variable and 'time since last attempted 1' suggests a natural coding interpretation: near-optimal codes on the BEHC are renewal-like, attempting a 1 after a geometrically distributed number of zeros."],"forward_implications":["For any target accuracy $\\epsilon$ and any harvesting probability $\\eta$, choosing $N$ large enough (e.g. $N=10{,}000$ guarantees about $10^{-3}$ for all $\\eta$) yields computable lower and upper bounds enclosing $C_{\\mathrm{BEHC}}$ within $\\epsilon$, without needing a closed-form capacity expression.","The computed values for $\\eta \\in \\{0.1,\\dots,0.9\\}$ at $10^{-6}$ precision improve on the best previously reported bounds, with the largest gains at small $\\eta$.","The same Q-graph plus MDP machinery gives numerical achievable rates for noisy BEHCs with feedback; for $\\eta=1$ the achievable rate for a BSC($p$) equals the ordinary BSC capacity $1-H(p)$.","The convex formulations are explicit optimization problems (Eqs. 26 and 28) with $O(N^2)$ constraints, so the method is directly reproducible from the paper and the released code.","Because the gap bound is independent of $\\eta$, the method provides a uniform precision guarantee across all harvesting probabilities."],"supporting_citations":[{"why":"Supplies the finite-state channel feedback-capacity lower bound (Theorem 1), the converse bound in Eq. (40), and the MDP formulation that the BEHC bounds build on.","marker":"[26]"},{"why":"Defines the binary energy-harvesting channel with a unit-sized battery and provides the best-known numerical bounds that this paper improves upon.","marker":"[14]"},{"why":"Introduced the BEHC model as a simplified binary instance of the finite-battery energy-harvesting channel.","marker":"[12]"},{"why":"Establishes the general finite-battery EH capacity framework and justifies the empty-battery initial state assumption used throughout.","marker":"[11]"},{"why":"Provides the Q-graph method for single-letter bounds on feedback capacity, the technique adapted here to the BEHC.","marker":"[27]"},{"why":"Gives the argument for restricting the upper-bound maximization to policies with a unique stationary distribution, used in the proof of Theorem 4.","marker":"[29]"},{"why":"Provides a Markov-chain lemma used in the proofs of Lemma 6 and Lemma 7 for the boosted-BEHC auxiliary-variable reduction.","marker":"[30]"}],"fun_headline_variants":["Energy-harvesting channel capacity: now computable to 1e-6","Convex optimization pins down energy-harvesting channel capacity","Q-graph bounds compute energy-harvesting channel capacity","Capacity of binary energy-harvesting channel via convex programs","Energy-harvesting channel capacity pinned to 1e-6 precision"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes that in the optimal upper-bound coding distribution, the chance of being in any intermediate node of the tracking graph is never higher than in the matching lower-bound distribution; this monotonicity, justified by a short self-loop argument at the last node, is what makes the gap shrink as $1/N$.","fun_headline_variants_meta":{"raw":{"variants":["Energy-harvesting channel capacity: now computable to 1e-6","Convex optimization pins down energy-harvesting channel capacity","Q-graph bounds compute energy-harvesting channel capacity","Capacity of binary energy-harvesting channel via convex programs","Energy-harvesting channel capacity pinned to 1e-6 precision"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000746,"raw_usage":{"total_tokens":3386,"prompt_tokens":1068,"completion_tokens":2318,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":684,"completion_tokens_details":{"reasoning_tokens":2224}},"tokens_in":684,"tokens_out":2318,"duration_ms":15633,"temperature":1.0,"reasoning_tokens":2224,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T12:16:11.431182+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the convex programs (26) and (28) for $\\eta=0.05$ at $N=10{,}000$ and check whether the gap exceeds $\\max_p H(p)/(Np+1) \\approx 10^{-3}$; a violation, or a direct violation of the monotonicity inequality (62) for any $N$, would refute the claimed $O(1/N)$ convergence.","supporting_citations":[{"cited_title":"Finite-state channels with feedback and state known at the encoder,","cited_arxiv_id":null,"evidence_quote":"Supplies the finite-state channel feedback-capacity lower bound (Theorem 1), the converse bound in Eq. (40), and the MDP formulation that the BEHC bounds build on."},{"cited_title":"The binary energy harvesting channel with a unit-s ized battery,","cited_arxiv_id":null,"evidence_quote":"Defines the binary energy-harvesting channel with a unit-sized battery and provides the best-known numerical bounds that this paper improves upon."},{"cited_title":"Binar y energy harvesting channel with finite energy storage,","cited_arxiv_id":null,"evidence_quote":"Introduced the BEHC model as a simplified binary instance of the finite-battery energy-harvesting channel."},{"cited_title":"Capacity of the e nergy- harvesting channel with a finite battery,","cited_arxiv_id":null,"evidence_quote":"Establishes the general finite-battery EH capacity framework and justifies the empty-battery initial state assumption used throughout."},{"cited_title":"A single-let ter upper bound on the feedback capacity of unifilar finite-state channels,","cited_arxiv_id":null,"evidence_quote":"Provides the Q-graph method for single-letter bounds on feedback capacity, the technique adapted here to the BEHC."},{"cited_title":"The feedback c apacity of Noisy Output is the STate (NOST) channels,","cited_arxiv_id":null,"evidence_quote":"Gives the argument for restricting the upper-bound maximization to policies with a unique stationary distribution, used in the proof of Theorem 4."},{"cited_title":"Finit e state channels with time-invariant deterministic feedback,","cited_arxiv_id":null,"evidence_quote":"Provides a Markov-chain lemma used in the proofs of Lemma 6 and Lemma 7 for the boosted-BEHC auxiliary-variable reduction."}],"review_version":1}