5
$\begingroup$

Given $y_{n}(x)=\left(\sum_{k=0}^{n-1} x^{2^k}\right)^{n}$. An example ($n=5$) may look like $$ y_5(x)={x^{80}}+5 x^{72}+5 x^{68}+5 x^{66}+5 x^{65}+10 x^{64}+20 x^{60}+20 x^{58}+20 x^{57}+20 x^{56}+20 x^{54}+20 x^{53}+40 x^{52}+20 x^{51}+40 x^{50}+30 x^{49}+35 x^{48}+60 x^{46}+60 x^{45}+60 x^{44}+60 x^{43}+80 x^{42}+50 x^{41}+61 x^{40}+60 x^{39}+100 x^{38}+90 x^{37}+85 x^{36}+70 x^{35}+95 x^{34}+65 x^{33}+75 x^{32}+{120 x^{31}}+120 x^{30}+100 x^{29}+110 x^{28}+100 x^{27}+90 x^{26}+90 x^{25}+100 x^{24}+100 x^{23}+90 x^{22}+70 x^{21}+66 x^{20}+70 x^{19}+55 x^{18}+65 x^{17}+75 x^{16}+60 x^{15}+50 x^{14}+50 x^{13}+40 x^{12}+30 x^{11}+31 x^{10}+25 x^{9}+15 x^{8}+10 x^{7}+5 x^{6}+x^{5} $$ If you plot exponents of addends of $y_n$ against prefactors, this looks (for $n=7$) like

$\hskip1.7in$enter image description here

Can this be described by a kind of Poisson distribution for general $n$?

$\endgroup$
  • $\begingroup$ Very nice question. Were you able to find out more about this problem? $\endgroup$ – Yuriy S Mar 10 '16 at 21:43
  • 1
    $\begingroup$ I'd consider instead $f(x)^n = \left(\sum_{k=0}^\infty x^{2^k-1}\right)^n = \sum_{m=0}^\infty a_m(n) x^m$ for $|x| < 1$ ? the central limit theorem should tell us that the coefficients $\frac{a_m(n)}{n}$ will tend to the normal distribution $\endgroup$ – reuns Mar 11 '16 at 6:33
  • 1
    $\begingroup$ Are you sure your plot is for $n=7$ and not $n=8$? The average degree should be $2^n-1$ which is only $127$ for $n=7$ and $255$ for $n=8$ matching the plot. $\endgroup$ – A.S. Mar 11 '16 at 6:41
  • 1
    $\begingroup$ Probabilistically speaking, you have a multinomial $M\sim MN(n,\frac 1 n,\dots,\frac 1 n)$ dotted with $V=(2^0,\dots, 2^{n-1})$: $S_M=M\cdot V$. You get $\mu_M=2^n-1$ and can compute variance exactly. Approximate $S_M$ by $S_B=\sum_{i=0}^{n-1} 2^{i}B(n,\frac 1 n)$ or go even further to get $S_P=\sum_{i=0}^{n-1} 2^{i}Pois(1)$. All cumulants of a Poisson are $1$, hence cumulants of $S_P$ are $$\kappa_k=\frac {2^{kn}-1}{2^k-1}$$ yielding variance $\kappa_2\approx \frac{4^n}3$ and $\kappa_{3}\approx\frac {8^n}7$. Quality of approximation of $S_M$ by $S_P$ deteriorate for higher cumulants. $\endgroup$ – A.S. Mar 11 '16 at 7:46
  • 1
    $\begingroup$ The above yields asymptotic skew of $\frac {3^{3/2}}{7}\approx 0.74$ $\endgroup$ – A.S. Mar 11 '16 at 7:51
3
+50
$\begingroup$

This is not a Poisson distribution, but is related. It is a rather interesting distribution, but let me not disclose it at the moment.

First note that, up to the multiple $n^n$, this is the probability generating function for the sum of $n$ iid random variables, which are uniformly distributed on the set $\{1,2,\dots,2^{n-1}\}$.

Dividing by $2^{n-1}$, we get the sum of $n$ iid random variables $\xi_{1,n},\dots,\xi_{n,n}$, uniformly distributed on the set $\{1,2^{-1},2^{-2}\dots,2^{1-n}\}$. Then the characteristic function of the sum $S_n = \xi_{1,n}+\dots+\xi_{n,n}$ is $$ \varphi_{S_n}(t) = \varphi_{\xi_{1,n}}(t)^n = \left(\frac1n \sum_{k=0}^{n-1}e^{it2^{-k}}\right)^n = \left(1+ \frac1n \sum_{k=0}^{n-1}\big(e^{it2^{-k}}-1\big)\right)^n\\ \to \exp\left\{\sum_{k=0}^{\infty}\big(e^{it2^{-k}}-1\big)\right\} = \prod_{k=0}^{\infty}\exp\left\{e^{it2^{-k}}-1\right\},\quad n\to\infty. $$ Therefore, $$S_n\overset{w}{\longrightarrow} S = \sum_{k=0}^\infty \frac{\zeta_k}{2^k},\quad n\to\infty,$$ where $\zeta_k$ are iid with Poisson(1) distribution.


Let us study the limit disribution $S$. As @A.S. wrote, its cumulants are $(1-2^{-k})^{-1}$.

Further, let $0.\alpha_1\alpha_2\alpha_3\dots$ be the binary form of fractional part of $S$. Then the sequence $\{\alpha_n,n\ge 1\}$ of digits is stationary (in fact, this is the case for any random variable of the form $\sum_{k=0}^\infty \zeta_k 2^{-k}$ with iid integer-valued variables $\zeta_k$). It is possible to "identify" the marginal distribution of digits, that is, the probability $p = P(\alpha_1 = 1)$. Define for $k\ge 0$ $$ E_k = 1 - 2e^{-1}\sum_{n=0}^\infty \frac{1}{(2^k (2n+1))!}. $$ Then $$ p = \frac12\left(1-\prod_{k=0}^\infty E_k\right). $$ If $p\neq 1/2$, which seems to be the case, then the distribution of $S$ is singular. (In the unlikely case that $p=1/2$, it is still singular since the digits $\alpha_n$ are dependent.) It is also continuous, but at the moment I don't see a simple way to prove this.

$\endgroup$
  • $\begingroup$ Didn't think of rescaling by $2^{n-1}$. What else can you say about the limiting distribution $\zeta$ apart from its characteristic function and cumulants $\kappa_k=(1-2^{-k})^{-1}$? $\endgroup$ – A.S. Mar 12 '16 at 15:03
  • $\begingroup$ @A.S., I tried to scale by variance too, but quickly found that there is no limit with such scaling. Concerning the distribution, I believe it is continuous and singular, but didn't try to prove this yet. $\endgroup$ – zhoraster Mar 12 '16 at 15:43
  • $\begingroup$ I got some !simulation pictures $\endgroup$ – A.S. Mar 12 '16 at 15:55
  • $\begingroup$ @A.S., the sequence of binary digits of the fractional part is stationary. I have some problems computing even the marginal distribution of digits (probably I'm just a bit tired), but it is almost obvious that the digits are dependent. So the singularity should be quite easy to prove. $\endgroup$ – zhoraster Mar 12 '16 at 20:43
  • $\begingroup$ +1 Whoa, I admit that this is not my branch of math, I deal with regularly. I might need more than 3 days to judge all this. Could you point towards a good online reference to provide my the basics I need? $\endgroup$ – draks ... Mar 14 '16 at 19:35
1
$\begingroup$

This is not an answer, but a series of thoughts about the problem.

As a start, the coefficient of $x^k$ in $y_n(x)$ seems to be the number of ways that $k$ can be written as the sum of $n$ powers of $2$ not exceeding $2^{n-1}$.

Another approach might be to use the fact that the coefficient of $x^m$ in $f(x)$ is $\frac{f^{m}(0)}{m!}$, and evaluate $y^{m}(0) $.

Another thought is that having $n$ as both the exponent and limit of the sum seems odd. It might be profitable to consider $y_{n, m}(x) = \left(\sum_{i=0}^n x^{2^i}\right)^m $.

That's all I can think of for now.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.