AI & ML
The Asymptotic Capacity of the Grabbag Channel With and Without Feedback
arXiv math.IT0 views
arXiv:2611.24700v1 Announce Type: new Abstract: The grabbag channel models communication through a randomly mixed store. At each use, an input ball of one of $K$ colors is inserted into a bag containing $M$ balls, and one of the resulting $M+1$ balls is selected uniformly, observed, and removed. We show that, when $2\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/3}$, and that, when moreover $M+1\geq2^{22}$, both are at least an absolute constant times $(K/(M+1))^{2/3}$. Hence, both capacities are of order $(K/M)^{2/3}$, and of order $M^{-2/3}$ for every fixed $K$. The converse is a single bound on the information that a feedback code conveys in $n$ 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.
Source:https://arxiv.org/abs/2611.24700PreviousRelative Entropy under Ordered Chi-Squared Constraints: Exact Bounds and ExtremizersNextOn cyclic codes generated by cyclotomic polynomials
Related posts
![Physical AI Engineering — Ch.01: Foundations of Physical AI [EN]](https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2Fwmesn5i4hcar0szww4nk.png)
Physical AI Engineering — Ch.01: Foundations of Physical AI [EN]
0dev.to
587 of OpenAI's 840 Ashby Jobs Report isRemote: true. Twenty-Two Are Remote
0dev.to

Meta now sells 3D movies on Quest VR headsets
0The Verge
![Physical AI Engineering — Ch.10: Medical and Human Centric Physical AI [EN]](https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2Fvy8fkq2vnw6ud8c0kvic.png)
Physical AI Engineering — Ch.10: Medical and Human Centric Physical AI [EN]
0dev.to
![Physical AI Engineering — Ch.09: Industrial Physical AI [EN]](https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2F2ulspenbbtgxps8mti74.png)
Physical AI Engineering — Ch.09: Industrial Physical AI [EN]
0dev.to
![Physical AI Engineering — Ch.08: Autonomous Vehicles and Mobility [EN]](https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2Fudcokq8k14p8ppu1mdnf.png)
Physical AI Engineering — Ch.08: Autonomous Vehicles and Mobility [EN]
0dev.to