Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This question is motivated by the following naive one: suppose we have a nice subset $X$ of some Euclidean space, say a polyhedron, and a nice $\mathbb{R}$-valued function $f$ on this subset, say a polynomial. Is it possible to deduce the value of the integral of $f$ along $X$ with respect to the Lebesgue measure from the integrals of $f$ along sets of arbitrarily small Hausdorff dimension? One way to make this precise is as follows.

Let $A_t,0< t\leq 1$ be the subset of $[0,1]$ obtained from $[0,1]$ by first removing the middle $1-t$ part, then removing the middle $1-t$ parts of the resulting two segments, then removing the middle $1-t$ parts of the resulting four segments and so on. (The middle $1-t$ part of a segment $[a,b]$ is the open interval of length $(1-t)(b-a)$ with center $\frac{b-a}{2}$.) Here are some remarks:

  1. If $t=\frac{2}{3}$, then $A_t$ is the Cantor middle third set.

  2. The Hausdorff dimension of $A_t$ is $\frac{\ln 2}{\ln 2-\ln t}$.

Now let $f:[0,1]\to\mathbb{R}$ be some ``nice'' function. Set $g(t)$ to be the average of $f$ over $A_t$. Recall that if $A$ is a compact metric space and $f:A\to\mathbb{R}$ is continuous, then the average of $f$ over $A$ is the limit as $i\to \infty$ of the averages of $f$ over $B_i$ where $(B_i)$ is a sequence of finite sets that converges to $A$ in the Hausdorff metric; recall also that the Hausdorff distance between two closed nonempty $A',A''\subset A$ is $$max(min_{a\in A'}dist (a,A''),min_{a\in A''}dist (a,A')).$$

Is it possible to explicitly compute $g(t)$, say when $f(x)=x^n$ with $n$ a non-negative integer? If not, what can one say about this function? Is it analytic in $t$? If so, does it extend analytically to $\mathbb{C}\setminus (-\infty,0]$?

[upd: I would also be happy with answers to the same questions for $f(x)=e^{nx}$ or $e^{inx}, n\in\mathbb{Z}$.]

share|improve this question
As you undoubtedly know, Monte Carlo/Las Vegas integration speaks to the randomized version of this problem. –  Steve Huntsman Sep 13 '11 at 17:27
Steve -- the way I understand it, Monte Carlo integration computes the integral straight away, as the limit of a sequence of expectations. I was interested to know how one can express, in a simple example, a 1-dimensional integral in terms of lower dimensional integrals. –  algori Sep 13 '11 at 18:21
Perhaps the following AMS Notices article will be helpful? ams.org/notices/200511/fea-sloan.pdf –  j.c. Sep 13 '11 at 19:19
The uniform measure on $A_t$ is a countable convolution of distributions with 2-point support, so it's easy to integrate exponentials if you're willing to accept answers like $\prod_{n=1}^\infty \bigl((\exp(2s/3^n)+1)/2 \bigr)$ for the integral of $\exp sx$ on the Cantor set. In particular you can get such product formulas for Fourier components. You can also integrate $x^k$ by differentiating $k$ times and taking $s=0$, though the resulting formulas do get complicated as $k$ grows. –  Noam D. Elkies Sep 14 '11 at 15:48
@algori: For the generalized Cantor set where at the $n$-th stage you keep only $2^n$ intervals of length $r^n$ (for some positive $r \leq 1/2$), the $n$-th factor in the product is $\left(\exp((r^{n-1}-r^n)s)+1\right)/2$. [Cantor is $r=1/3$; the full interval is $r=1/2$ — check that the product then gives $(e^s-1)/s$ as it should.] It looks like your $t$ is $2r$, so you can take $r=t/2$ in the resulting product. –  Noam D. Elkies Sep 14 '11 at 17:41
show 5 more comments

1 Answer

up vote 5 down vote accepted

Here's how to average $e^{sx}$ over $A_t$. Let $r = t/2$, so at the $N$-th step of the construction of $A_t$ we have the disjoint union $A_t^{(N)}$ of $2^N$ intervals of length $r^N$ whose left endpoints are $\sum_{n=1}^N (r^{n-1}-r^n) \phantom. \epsilon_n$ with each $\epsilon_n \in \lbrace0,1\rbrace$. Thus to choose uniformly at random from $A_t^{(N)}$ we choose for each $n=1,2,\ldots,N$ either $0$ or $r^{n-1}-r^n$ with probability $1/2$, sum these $n$ terms, and add a real number chosen uniformly at random from $[0,r^N]$. This is a convolution of $N$ discrete measures and a single continuous one, so the average of $e^{sx}$ over $A_t^{(N)}$ is the product of $N$ finite sums and one integral: $$ \prod_{n=1}^N \frac{1+\exp((r^{n-1}-r^n)s)}{2} \cdot \frac1{r^N} \int_0^{r^N} e^{sx} dx \phantom. . $$ letting $N \rightarrow \infty$ we find that the average of $e^{sx}$ over $A_t$ is $$ I_s(r) = \prod_{n=1}^\infty \frac{1+\exp((r^{n-1}-r^n)s)}{2} \phantom. . $$ (Check: for $r=0$ this is just $(1+e^{s})/2$ because $A_0 = \lbrace 0,1 \rbrace$; and for $r=1/2$ it's $(e^{sx}-1)/s$ because $A_1$ is the interval $[0,1$].)

To average polynomials over $A_t$, it is enough to average $x^k$ for $k=0,1,2,\ldots$. To compute these averages we expand $I_s(r)$ in a power series about $s=0$. It's easier to do this with the logarithm: $$ \log I_s(r) = \sum_{n=1}^\infty \phantom. \log\frac{1+\exp((r^{n-1}-r^n)s)}{2} = \sum_{n=1}^\infty \phantom. \lambda((r^{n-1}-r^n)s), $$ where $$ \lambda(z) := \log \frac{1+e^z}{2} = \frac{z}{2} + \frac{z^2}{8} - \frac{z^4} {192} + \frac{z^6}{2880} - \frac{17z^8} {645120} + - \cdots. $$ Thus the $s$ coefficient of $\log I_s(r)$ is $\frac12 \sum_{n=1}^\infty (r^{n-1} - r^n) = 1/2$; the $s^2$ coefficient is $\frac18 \sum_{n=1}^\infty (r^{n-1} - r^n)^2 = \frac18 (1-r)/(1+r)$; the $s^4$ coefficient is $-\frac1{192} (1-r)^3 / (1+r+r^2+r^3)$; and the $s^3$, $s^5$, $s^7$, ... coefficients vanish. So $$ I_s(r) = \exp\left( \frac{s}{2} \phantom. + \phantom. \frac{1-r}{1+r} \frac{s^2}{8} \phantom. - \phantom.\frac{(1-r)^3}{1+r+r^2+r^3} \frac{s^4}{192} \phantom.+\phantom. O(s^6) \right). $$ From this we may recover the average of $x^k$ over $A_t$ by extracting the $s^k$ coefficient and multiplying by $k!$. If I did this right, the average comes to $1/2$ for $k=1$ (of course), then $1/(2+t)$ for $k=2$, and $$ \frac{4-t}{8+4t}, \phantom{\infty} \frac{8+2t^2-t^3}{(2+t)^2(4+t^2)},\phantom{\infty} \frac{(4-t)(4+2t^2-t^3)}{(2+t)^2(4+t^2)} $$ for $k=3,4,5$. I did at least check that for $t=1$ we recover $1/2,1/3,1/4,1/5,1/6$, and for $t=0$ each average is $1/2$.

share|improve this answer
Dear Noam -- thanks a lot for transforming your comments into an answer. So it turns out that the averages of polynomials are in fact rational functions in $t$. That's quite a surprise. –  algori Sep 14 '11 at 22:25
add comment

Your Answer


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

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