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 \vec{\gamma}\log \vec{\gamma}+\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.)?

  • $\begingroup$ $n$ is the length of the sequence by the way. $\endgroup$ – user13503 Jan 29 '13 at 11:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.