4
$\begingroup$

Let $(X_1, X_2)$ be uniform over the unit Sierpinski triangle (represented in Cartesian coordinates). What is its covariance matrix?

This is a question I saw in a jobs ad. I would love some leads on solving it.

$\endgroup$
  • $\begingroup$ Certainly, the covariance must be zero, due to the relationship between covariance and correlation and the symmetry of the standard Sierpinski triangle. $\endgroup$ – Mark McClure May 9 '18 at 15:25
  • $\begingroup$ @MarkMcClure any idea how one could show this "the long way around"? I'm very interested in probabilistic reasoning over fractal distributions! $\endgroup$ – Carl Patenaude Poulin May 9 '18 at 16:03
  • $\begingroup$ Yeah - numerical estimations are easy but theoretical computations involve a bit more work. Are you sure the question asks for the full covariance matrix? That essentially means you need to compute the $X$ and $Y$ variances. That can be done, but is not totally easy. $\endgroup$ – Mark McClure May 9 '18 at 16:10
  • 1
    $\begingroup$ You know how to express the variances as integrals with respect to the uniform distribution? If so, then an approach similar to the one I outline in my answer to this question should work. I believe that both variances are $1/18$. $\endgroup$ – Mark McClure May 9 '18 at 18:31
  • 1
    $\begingroup$ Is this triangle bounded by the triangle with vertices $(0, 0), (1, 0), (0, 1)$? It's unclear to me. $\endgroup$ – Brian Tung May 9 '18 at 20:51
2
$\begingroup$

For this answer, I will interpret the "unit Sierpinski triangle $S$" as being the one with vertices $(0,0)$, $(1,0)$, $(0,1)$. If you want to use the triangle with vertices $(0,0)$, $(1,0)$, $(\frac{1}{2}, \frac{\sqrt{3}}{2})$ instead (i.e. beginning with an equilateral triangle) then a very similar method should work.

I will also interpret the "uniformity" condition on the probability measure $\mu$ on $S$ as meaning that the contraction of $S$ to each of its subtriangles of level 1, $S_{00}$, $S_{01}$, and $S_{10}$, respects measure except that it multiplies it by $\frac{1}{3}$.

Now, this will imply that for any measurable and $L^1$ function $f : S \to \mathbb{R}$, we have $$ \int_{S_{00}} f(x,y) d\mu = \frac{1}{3} \int_S f \left(\frac{1}{2}x, \frac{1}{2}y \right) d\mu; \\ \int_{S_{01}} f(x,y) d\mu = \frac{1}{3} \int_S f \left(\frac{1}{2} x, \frac{1}{2}y + \frac{1}{2} \right); \\ \int_{S_{10}} f(x,y) d\mu = \frac{1}{3} \int_S f \left(\frac{1}{2} x + \frac{1}{2}, \frac{1}{2} y \right).$$ The reason: it must hold for any characteristic function of a set by the uniformity condition; then, by linearity it must hold for simple functions; then, the definitions of Lebesgue integrals for nonnegative functions and for $L^1$ functions will extend the equations to all $L^1$ functions.

We can also show that the function $x : S \to \mathbb{R}$ must be measurable: for any dyadic rational $q$, $x^{-1}([q, \infty)) = \{ (x, y) \in S \mid x \ge q \}$ is a finite union of subtriangles of $S$ and therefore measurable. However, the intervals $[q, \infty)$ with $q$ a dyadic rational generate the Borel $\sigma$-algebra on $\mathbb{R}$. Similarly, the function $y : S \to \mathbb{R}$ must be measurable. And then, since both $x$ and $y$ are bounded functions on $S$ and $\mu$ is a finite measure, it follows that they are also in $L^1(\mu)$.

Using this, we can now calculate: $$E(x) = \int_S x\,d\mu = \int_{S_{00}} x\,d\mu + \int_{S_{01}} x\,d\mu + \int_{S_{10}} x\,d\mu = \\ \frac{1}{3} \int_S \frac{1}{2}x\,d\mu + \frac{1}{3} \int_S \frac{1}{2}x\,du + \frac{1}{3} \int_S \left( \frac{1}{2}x + \frac{1}{2} \right) d\mu = \\ \frac{1}{2} \int_S x\,d\mu + \frac{1}{6} = \frac{1}{2} E(x) + \frac{1}{6}.$$ It follows that $E(x) = \frac{1}{3}$. Very similarly, $E(y) = \frac{1}{3}$.

The calculation of $E(x^2), E(xy), E(y^2)$ will be very similar (using the previous results for $E(x)$ and $E(y)$ in intermediate steps).

$\endgroup$
  • 1
    $\begingroup$ I concur with this and get$$\left(\begin{array}{cc} 2/27 & -1/27 \\ -1/27 & 2/27 \\ \end{array}\right)$$ for the final covariance matrix. The original ad did use an equilateral triangle however. $\endgroup$ – Mark McClure Nov 9 '18 at 0:05
1
$\begingroup$

As mentioned by @MarkMcClure in the comments (and the wonderful linked answer), both the numerical and exact answer of points sampled from the Sierpinski triangle seems to be $(1/18) \mathbf{I}_2$ when you consider the points as N-dimensional samples $X=(x_1, x_2, \ldots, x_N)^T$. If however, you consider the transpose of that $Y = X^T$ you get the answer below. While not correct, it was fun to work through and I'll leave it up as long as people still think it has some value.

Original Answer

Not directly an answer, but there are simple direct insights you can make into the problem by sampling. First, sample a few thousand points using the chaos game. enter image description here

Compute the covariance matrix $C = \textrm{Cov}(X_1,X_2)$ and then the eigenvectors, $Cv = \lambda v$. You'll quickly find that the largest eigenvalue dominates all of the rest. In this sample $\lambda_1 / \lambda_2 \approx 10^{15}$. Sort $C$ by this eigenvector $v_1$ and you get a beautiful and smooth matrix:

enter image description here

For the final visual, color the points by this $v_1$

enter image description here

All of this suggests that the answer to the original question has a nice closed form.

$\endgroup$
  • $\begingroup$ Hmm... shouldn't the covariance matrix be 2 by 2? $\endgroup$ – Mark McClure May 10 '18 at 20:24
  • $\begingroup$ @MarkMcClure it's possible that there is a nomenclature error on my part here. I'm using this definition docs.scipy.org/doc/numpy-1.14.0/reference/generated/… where N points in d dimensions gives me an NxN matrix. Was the question about the transpose giving a dxd matrix? $\endgroup$ – Hooked May 10 '18 at 20:43
  • 1
    $\begingroup$ @MarkMcClure taking the 2x2 matrix gives ~ $0.05 * \mathbf{I}$ $\endgroup$ – Hooked May 10 '18 at 20:45
  • $\begingroup$ That sounds right - I computed it to be $I/18$ using the techniques on the comments. If you modifiy, I'll upvote. :) $\endgroup$ – Mark McClure May 10 '18 at 21:05
  • 1
    $\begingroup$ @MarkMcClure turns out, I totally misread the problem as stated in the prior comment. I like the pictures for the other problem I worked on so I thought I'd leave it up. I've brought attention to your comment/answer at the top and thanks for showing me the Strichartz paper (it's really interesting!). $\endgroup$ – Hooked May 11 '18 at 13:47

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.