Take the 2-minute tour ×
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.

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|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.