Probabilistic analysis of arithmetic coding showing its robustness
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916617329311744 |
|---|---|
| author | Mahmoud, Hosam M. Rivertz, Hans J. |
| author_facet | Mahmoud, Hosam M. Rivertz, Hans J. |
| contents | We probabilistically analyze the performance of the arithmetic coding algorithm under a probability model for binary data in which a message is received by a coder from a source emitting independent equally distributed bits, with 1 occurring with probability $p\in(0,1)$ and 0 occurring with probability $1-p$.
We establish a functional equation for the bivariate moment generating function for the two ends of the final interval delivered by the algorithm. Via the method of moments, we show that the transmitted message converges in distribution to the standard continuous uniform random variable on the interval [0,1]. It is remarkable that the limiting distribution is the same for all $p$, indicating robustness in the performance of arithmetic coding across an entire family of bit distributions. The nuance with $p$ appears only in the rate of convergence. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_10935 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Probabilistic analysis of arithmetic coding showing its robustness Mahmoud, Hosam M. Rivertz, Hans J. Data Structures and Algorithms We probabilistically analyze the performance of the arithmetic coding algorithm under a probability model for binary data in which a message is received by a coder from a source emitting independent equally distributed bits, with 1 occurring with probability $p\in(0,1)$ and 0 occurring with probability $1-p$. We establish a functional equation for the bivariate moment generating function for the two ends of the final interval delivered by the algorithm. Via the method of moments, we show that the transmitted message converges in distribution to the standard continuous uniform random variable on the interval [0,1]. It is remarkable that the limiting distribution is the same for all $p$, indicating robustness in the performance of arithmetic coding across an entire family of bit distributions. The nuance with $p$ appears only in the rate of convergence. |
| title | Probabilistic analysis of arithmetic coding showing its robustness |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.10935 |