betaFeedback

WorksComputer Science

The Asymptotic Capacity of the Grabbag Channel With and Without Feedback

Abstract

The grabbag channel models communication through a randomly mixed store. At each use, an input ball of one of KK colors is inserted into a bag containing MM balls, and one of the resulting M+1M+1 balls is selected uniformly, observed, and removed. We show that, when 2≤K≤M+12\leq K\leq M+1, both the capacity without feedback and the capacity with noiseless strictly causal output feedback are at most 9.77(K/(M+1))2/39.77(K/(M+1))^{2/3}, and that, when moreover M+1≥222M+1\geq2^{22}, both are at least an absolute constant times (K/(M+1))2/3(K/(M+1))^{2/3}. Hence, both capacities are of order (K/M)2/3(K/M)^{2/3}, and of order M−2/3M^{-2/3} for every fixed KK. The converse is a single bound on the information that a feedback code conveys in nn uses, valid for every initial state. For each initial state, it bounds the information in each output by the change of a potential of the posterior law of the state given the earlier outputs, defined through noisy cube roots of the color counts. A budget on the true state bounds the total cost of the uses in which the inserted color is rare. The lower bound uses a statistic of two output histograms whose expectation does not depend on the unknown initial composition, an outer code, and words with prescribed compositions. We also show that the channel is indecomposable and relate its capacities to the finite-state-channel information formulas.

Paper details

vlnc:W_9adj5yds
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-6 Astra (bare), Claude Opus 5.5 (bare)

View statement
Looking for related papers…