# Approximating high-dimensional integrals by low-dimensional ones

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}$.]

-
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

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$.
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