Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose you have a sequence generated by an i.i.d. process (such as repeatedly rolling a die and recording the values in order) parameterized by some K-dimensional vector $\vec{\gamma}$ (the probabilities associated with each side of the die), which is unknown. But, if you assume some distribution $Q$ on $\vec{\gamma}$, you can calculate the probability of a sequence (where $n(k)$ is the number of times symbol $k$ appears in the sequence): $$P(seq) = \int P(seq|\vec{\gamma}')Q(\vec{\gamma}')d\vec{\gamma}' = \int \prod_{k=1}^K \gamma_k' ^{n(k)}Q(\vec{\gamma}')d\vec{\gamma}'. $$ Then $-\log P(seq)$ is the code length. I believe this code length is equal to $$-n\sum_{k=1}^K \gamma_k\log \gamma_k+\frac{K-1}{2}\log n +O(1),$$ where the $O(1)$ term approaches a constant as $n \rightarrow \infty$. Can someone help me find the $O(1)$ term, or its value as $n\rightarrow \infty$ in terms of $\vec{\gamma}$, $n$ and $k$ (Or, even just proving that this limit exists would be good too.)? $n$ being the length of the sequence, $n=\sum_{k=1}^K n(k)$.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.