User david moews - MathOverflow

Answer by David Moews for Does the set of happy numbers have a limiting density?

2011-11-10T22:55:56Z

I started working on this question after it was posted to MathOverflow and found bounds similar to those found by Justin Gilmer: upper asymptotic density of the happy numbers 0.1962 or greater, lower asymptotic density no more than 0.1217. However, I was also able to prove that the upper asymptotic density of the happy numbers was no more than 0.38; Gilmer mentioned in his paper that the question of whether the upper asymptotic density was less than 1 was still open.

A writeup of the result is at http://djm.cc/dmoews/happy.zip. The method used to find an upper bound on the upper asymptotic density was to start with a random number with decimal expansion $??\dots{}??\hbox{#}\hbox{#}\dots{}\hbox{#}\hbox{#}$, where the digits # are independent and uniformly distributed, and the digits ? are arbitrarily distributed and may depend on each other, but are independent of the #s. Then if there are $n$ #s, asymptotic normality implies that after applying $s$, we get a mixture of translates of a distribution which is approximately normal, with mean $28.5n$ and standard deviation proportional to $\sqrt{n}$. If $10^{n'}/\sqrt{n}$ is sufficiently small, each translate of this normal distribution will have its last $n'$ digits approximately uniformly distributed, so we get a random number which can be approximated by the same form of decimal expansion we started with, $??\dots{}??\hbox{#}\hbox{#}\dots{}\hbox{#}\hbox{#}$, where now there are $n'$ digits #. Repeating this eventually brings us to numbers small enough to fit on a computer.

The method used to find the bounds similar to Gilmer's was to start with a random number of the form $dd\dots{}dd??\dots{}??\hbox{#}\hbox{#}\dots{}\hbox{#}\hbox{#}$, where the ?s and #s are as before, the $d$s are fixed digits, and there are the same number of $d$s and #s, but very few ?s. Then if the parameters are appropriately chosen, we can show that after applying $s$, we again get a random number which can be approximated by the same form of decimal expansion, $dd\dots{}dd??\dots{}??\hbox{#}\hbox{#}\dots{}\hbox{#}\hbox{#}$, and repeat this step until the number is small.

Answer by David Moews for A bound involving Stirling numbers of the second kind and the asymptotics

2011-09-14T05:18:07Z

($A_{n,r}$ has a combinatorial interpretation: the denominator is the number of ways of partitioning the numbers ${1,\ldots,n+r}$ into $r$ blocks, where the list of blocks is ordered but the numbers within each block are unordered, and the numerator is the same count, except that the numbers within each block are now also ordered. $A_{n,r}$ is therefore the expected number of ways to order the numbers within each block, given a random partition of ${1,\ldots,n+r}$ into $r$ unordered blocks.)

Here is a proof of $A_{n,r}\ge A_{n,r+1}$: Algebraic manipulation simplifies this inequality into $$S_{n+r+1,r+1} r(r+1)\ge S_{n+r,r} (n+r)(n+r+1),$$ or, setting $m:=n+r$, $$S_{m+1,r+1} r(r+1)\ge S_{m,r} m(m+1).$$ If we multiply by $x^m/(m+1)!$ and sum over $m$, we see that it will do to prove $$r(r+1) \sum_m S_{m+1,r+1} \frac{x^{m}}{(m+1)!}\succ \sum_m S_{m,r} \frac{x^m}{(m-1)!},$$ where $\succ$ means that the inequality holds on the coefficients of each power of $x$. This can be rewritten as $$x^{-1} r(r+1) \sum_m S_{m+1,r+1} \frac{x^{m+1}}{(m+1)!}\succ x \partial_x \sum_m S_{m,r} \frac{x^m}{m!}.$$ The egf for $S_{m,r}$ in the first variable is $$\sum_m S_{m,r} \frac{x^m}{m!}=\frac{(e^x-1)^r}{r!},$$ so this becomes $$x^{-1} \frac{(e^x-1)^{r+1}}{(r-1)!}\succ x e^x \frac{(e^x-1)^{r-1}}{(r-1)!},$$ which will follow if $$(e^x-1)^2 \succ x^2 e^x.$$ This last coefficientwise inequality is true because the coefficient of $x^n$ ($n\ge 2$) is $(2^n-2)/n!$ on the left-hand side and $1/(n-2)!=n(n-1)/n!$ on the right-hand side, and $2^n-2\ge n(n-1)$ for $n\ge 2$.

Answer by David Moews for exchangeable normal r.v.s

2011-09-09T21:50:26Z

De Finetti's theorem has already been mentioned, but it seems to me that it answers the original question. In this case, it says that any exchangeable infinite sequence $X_1, X_2, X_3, \ldots$ of real-valued random variables comes from some probability measure $\Phi$ on the set of measures on $\Bbb R$. The sequence is generated by picking $\mu\sim\Phi$ and then taking i.i.d. $X_1, X_2, X_3, \ldots \sim\mu$. So, the third bullet point is automatically satisfied, and the "population distribution" is $\mu$. To get marginal normality you only need that ${\bf E}[\mu]=N(0,1)$, so there is a wide choice for $\Phi$.

Answer by David Moews for What conditions on a probability distribution defined by long-time averaging do I need to satisfy a central limit theorem?

2011-09-09T22:36:24Z

In your example, algebraic manipulation gives $$ 2^{-M} \sum_{n=0}^{2^M-1} X_n^{(M)} = \prod_{j=0}^{M-1} \cos t h_j. $$ If the $h_j$'s are linearly independent over $\Bbb Q$, then, as you point out, the random variables $\cos t h_j$ approach independence as $t$ is chosen over larger and larger intervals. Therefore, in the limit, $$ Y = Z_1 ... Z_M, \qquad Z_i = \cos W_i, \qquad W_1,...,W_M {\rm\ \ i.i.d.\ uniform\ on\ } [0,2\pi). $$ By symmetry, ${\bf E}[Y]=0$, and since ${\bf E}[Z_i^2]=1/2$ for each $i$, we have ${\bf Var}[Y]=2^{-M}$. This may explain the result of your numerical experiments. However, $Y$ does not approach normal after rescaling: if $Y$ is rescaled to unit variance by setting $Y'_M:=2^{M/2} Y$, then $\log |Y'_M|=\log(\sqrt{2} |Z_1|)+...+\log(\sqrt{2} |Z_M|)$, so, since ${\bf E}[\log(\sqrt{2} |Z_i|)]<0$ and ${\bf Var}[\log(\sqrt{2} |Z_i|)]<\infty$, we can apply the CLT to $\log |Y'_M|$ to show that, as $M\to\infty$, $\log |Y'_M|$ will converge weakly to normal after rescaling, but $Y'_M$ converges weakly to 0.

Comment by David Moews

2011-11-16T23:14:49Z

Given the recurrence for $v(t)$ above, you can also use the renewal theorem to prove that $\lim_{t\to\infty} v(t)$ exists and compute its value.

Comment by David Moews

2011-11-16T01:30:43Z

I think some factors of $t$, etc., may be missing from the working shown here. When I apply the method given above I find $c=5/\log 6=2.79055$, which is in good agreement with an experimental value of $2.79 \pm 0.01$.

Comment by David Moews

2011-09-20T00:20:45Z

\begin{eqnarray*} &\ &\sum_{n\ge 0} \frac{t^n}{(n+r)!} \sum_{k_1+\cdots+k_r=n} \frac{1}{r!} \binom{n+r}{k_1+1 \cdots k_r+1} \prod_{i=1}^r (k_i+1)! x_i^{k_i+1}\\ &= &\frac{1}{r!} \frac{x_1}{1-x_1t}\cdots \frac{x_r}{1-x_rt}. \end{eqnarray*}

Comment by David Moews

2011-09-20T00:17:43Z

From a combinatorial view, this function is a little odd because it mixes $r$-partitions of $\{1,\ldots,n\}$ with $r$-partitions of $\{1,\ldots,n+r\}$. I don't think it will come out to be anything simple. If you changed $S_{n,r}$ to $S_{n+r,r}$, split it up, and pushed it forward through the second sum, you would get something simple:

Comment by David Moews

2011-09-20T00:12:57Z

Substituting $\alpha$ for $y$, this shows that the function is a probability density. The density of the marginals can now be found by multiplying $2\phi(x) f(\alpha x)$ by the density of $\alpha$, $\phi(\alpha)$, and integrating over $\alpha$. Substituting $x$ for $y$ in the equation above shows that $\int 2 f(\alpha x) \phi(\alpha) d\alpha=1$, so the overall integral reduces to $\phi(x)$, giving marginal normality, as desired.

Comment by David Moews

2011-09-20T00:12:32Z

I think, that the example is correct as stated. There is nothing special about the function $\Phi$; you could use any nonnegative function $f$ satisfying $f(x)+f(-x)=1$, and let each $X_i$ have density $2\phi(x) f(\alpha x)$. Since $\phi$ is even, you then get $\int 2\phi(z) f(yz) dz=2 \int_{z\ge 0} (f(yz) + f(-yz))\phi(z) dz=1$ for any $y$.

Comment by David Moews

2011-09-13T01:58:50Z

Setting $Y_M:=Y$, there is no way to pick scaling constants $a_M$ such that $a_M Y_M$ converges to something nontrivial. $|Y_M|^{1/\sqrt{M}}$ will converge if rescaled appropriately.

Comment by David Moews

2011-09-13T01:07:50Z

To compute the variance of $Y$, observe that $Y^2$ is the product of $M$ independent random variables, each distributed as $\cos^2 W$, where $W$ is uniform. Since $\cos^2$ has average value $\frac{1}{2}$, and the r.v.s are independent, ${\bf E}[Y^2]$ is the product of $M$ copies of $\frac{1}{2}$, which is $2^{-M}$.

Comment by David Moews

2011-09-12T08:13:51Z

True, Lauritzen's example is multivariate normal. OK, here's another example: pick $\alpha\sim N(0,1)$, and then let $X_i$ be i.i.d., each with density $2\phi(x) \Phi(\alpha x)$, where $\phi$ and $\Phi$ are the density and cdf of $N(0,1)$. In this example the $X_i$'s have skewed distributions where $\alpha$, a measure of the skew, is itself normally distributed.

Comment by David Moews

2011-09-09T23:55:44Z

Another example, in which $\Phi$ is discrete, would be to draw the graph of the density function of $N(0,1)$, divide the region underneath the density function into countably many chunks, and pick $\mu$ by throwing a dart at the picture and looking at the chunk it lands in. To pick the $X_i$'s, we throw more darts at the picture, but condition them to land in the chunk we chose earlier.

Comment by David Moews

2011-09-09T23:52:19Z

Lauritzen gives a simple example in his lecture. He fixes some $\rho$ in $[0,1]$ and then takes $\mu=N(Y,1-\rho)$, where $Y\sim N(0,\rho)$. This interpolates between the i.i.d. case ($\rho=0$) and the case where $X_1$, $X_2$, ... is a constant sequence ($\rho=1$.)