Minimax Optimal Universal Codeword Sets
In an interactive multi-user data-processing system a user knows the probabilities of his messages and must encode them into a fixed system-wide variable-length codeword set. He needs to receive the answer to his last message before selecting the next, so his encoding is one-shot. To minimize averag...
| Autor principal: | |
|---|---|
| Publicado: |
2023
|
| Acceso en línea: | https://hdl.handle.net/1721.1/149023 |
| _version_ | 1826214669816168448 |
|---|---|
| author | Elias, Peter |
| author_facet | Elias, Peter |
| author_sort | Elias, Peter |
| collection | MIT |
| description | In an interactive multi-user data-processing system a user knows the probabilities of his messages and must encode them into a fixed system-wide variable-length codeword set. He needs to receive the answer to his last message before selecting the next, so his encoding is one-shot. To minimize average codeword length he encodes his messages in order of decreasing probability into codewords in order of increasing length. I give an algorithm which, for each of several measures of performance, finds the codeword set best by that measure for the worst user, and some of the minimax optimal codeword sets the algorithm has found. Some of the results hold for all user distributions: others require e.g. that all users send exactly or at most m distinct messages, and/or that there is an integer k such that no user has a message of probability greater than 1/k. |
| first_indexed | 2024-09-23T16:09:09Z |
| id | mit-1721.1/149023 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T16:09:09Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1490232023-03-30T03:07:08Z Minimax Optimal Universal Codeword Sets Elias, Peter In an interactive multi-user data-processing system a user knows the probabilities of his messages and must encode them into a fixed system-wide variable-length codeword set. He needs to receive the answer to his last message before selecting the next, so his encoding is one-shot. To minimize average codeword length he encodes his messages in order of decreasing probability into codewords in order of increasing length. I give an algorithm which, for each of several measures of performance, finds the codeword set best by that measure for the worst user, and some of the minimax optimal codeword sets the algorithm has found. Some of the results hold for all user distributions: others require e.g. that all users send exactly or at most m distinct messages, and/or that there is an integer k such that no user has a message of probability greater than 1/k. 2023-03-29T14:20:27Z 2023-03-29T14:20:27Z 1982-01 https://hdl.handle.net/1721.1/149023 9220072 MIT-LCS-TM-212 application/pdf |
| spellingShingle | Elias, Peter Minimax Optimal Universal Codeword Sets |
| title | Minimax Optimal Universal Codeword Sets |
| title_full | Minimax Optimal Universal Codeword Sets |
| title_fullStr | Minimax Optimal Universal Codeword Sets |
| title_full_unstemmed | Minimax Optimal Universal Codeword Sets |
| title_short | Minimax Optimal Universal Codeword Sets |
| title_sort | minimax optimal universal codeword sets |
| url | https://hdl.handle.net/1721.1/149023 |
| work_keys_str_mv | AT eliaspeter minimaxoptimaluniversalcodewordsets |