1
$\begingroup$

Consider a collection of increasing positive integers $\{a_i\}_{i=1}^m$.

Consider distribution $p_i=\frac{a_i}{\sum_{i=1}^ma_i}$. Given $\{a_i\}_{i=1}^m$, let $\mathcal{P}_{a,m}$ be distribution at every $m$.

$$\mbox{Case }(1)\mbox{: }a_{i+1}=a_i+\theta(\log^ka_i)$$ $$\mbox{Case }(2)\mbox{: }a_{i+1}=a_i+\theta(a_i^{\frac{1}{k}})$$ where $k$ is a positive constant.

$\mathsf{\underline{Conjecture}}$: I think at a fixed $k>0$, there will be constants $c_k>0, m(a,c_k)\in\Bbb N$ such that: $$\mbox{Case }1\mbox{: }\forall m>m(a,c_k)\mbox{, }H(\mathcal{P}_{a,m})>c_k$$ $$\mbox{Case }2\mbox{: }\forall m>0\mbox {, }H(\mathcal{P}_{a,m})<c_k.$$

Follow from relevant link Entropy difference dominance of sequences

Generalization is in here Limiting Entropy of deterministic sequences - 2

Improve this question
$\endgroup$
5
  • $\begingroup$ Added mathoverflow.net/questions/191683/… $\endgroup$
    – Turbo
    Commented Dec 29, 2014 at 4:32
  • 1
    $\begingroup$ I don't quite understand your setup. What do you mean by the limiting distribution $\mathcal P_a$? Since your sequence $a_i$ is increasing, for any fixed $i$ the limit of $a_i/\sum_{i=1}^m a_i$ is $0$ for $m\to\infty$. However later on you are asking whether $H(\mathcal P_a)\to\infty$ apparently presuming that $\mathcal P_a$ depends on something else. $\endgroup$
    – R W
    Commented Jan 2, 2015 at 12:24
  • $\begingroup$ @RW Idea is at each $m$, sequence $\{a\}^m_{i=1}$ has entropy $H(a,m)$. I am questioning about growth of $H(a,m)$ as a function of $m$ (is there a path to make it more precise here?) $\endgroup$
    – Turbo
    Commented Jan 2, 2015 at 19:35
  • $\begingroup$ @RW Does update make more sense? $\endgroup$
    – Turbo
    Commented Jan 3, 2015 at 1:57
  • 1
    $\begingroup$ Yes - now it's clear what you are asking about $\endgroup$
    – R W
    Commented Jan 3, 2015 at 2:53

1 Answer 1

Reset to default
1
$\begingroup$

Regarding (2), the answer seems to be no by the reasoning at Entropy difference dominance of sequences That is, the limiting entropy can be that of the geometric distribution, which is finite.

The boundary between finite and infinite entropy may be close to a distribution like $p_1,\dots,p_m$ where $p_k$ is on the order of $$ \frac1{k(\log k)^a},\quad a\in\{2,3\}. $$ Because then the entropy will be $$ \sum_k \frac{-1}{k(\log k)^a}\cdot\log\left(\frac{1}{k(\log k)^a}\right)$$ $$ =\sum_k \frac{\log k+a\log\log k}{k(\log k)^a}\approx \sum_k \frac{1}{k(\log k)^{a-1}} $$ which goes to infinity as $m\rightarrow\infty$ if $a=2$, but not if $a=3$.

Improve this answer
$\endgroup$
7
  • $\begingroup$ $a=2$ case corresponds to $a_{i+1}=a_i + \theta(\log^c a_i)$ correct for all fixed $c\geq2$ correct? What does $a=3$ case correspond to in terms of $|a_{i+1}-a_i|$? $\endgroup$
    – Turbo
    Commented Jan 1, 2015 at 9:02
  • 1
    $\begingroup$ I didn't check how it covers the case (1) exactly, so maybe you can try to work it out and report back $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Jan 1, 2015 at 9:09
  • $\begingroup$ I checked a while back. Case $1$ seems related to $a\leq2$ and case $2$ seems related to $a>2$(possibly $a$ takes value such as $3$ that makes your summation converge). $\endgroup$
    – Turbo
    Commented Jan 2, 2015 at 2:14
  • $\begingroup$ @BjornKjosHanssen What is interpretation of entropy here? Does it mean we should be able to compress $a_i$ in finite number of bits or impossible to do in finite number of bits in total? $\endgroup$
    – Turbo
    Commented Jan 2, 2015 at 5:28
  • $\begingroup$ @Turbo sounds like another interesting question :) $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Jan 2, 2015 at 6:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .