[math-fun] Asimov's correlation problem
The optimal solution was unit vectors that are the N+1 vertices of a regular simplex in N-dimensional space centered at the origin. (N=3 for Asimov's problem, regular tetrahedron.) These are anticorrelated somewhat, dot product of any two is -1/N minimizing correlation by making it maximally negative. My solution with 4 mutually orthogonal 8-vectors was optimal if we want zero correlation, which minimizes correlation if you meant the absolute value of the correlation...
Yup. Maybe there is an easier way to see what the cosine of the angle between any two vectors from the center to a vertex of a regular n-simplex is, but the way I know is this: __________________________________________________________________________________ The n+1 standard basis vectors in R^(n+1) form the vertices of a regular n-simplex whose center lies at c = (1/(n+1), ..., 1/(n+1)) in R^(n+1). So, two vectors in R^(n+1) forming the angle in question are v = e_1 - c = (1-1/(n+1), -1/(n+1), -1/(n+1),..., -1/(n+1)) and w = e_2 - c = (-1/(n+1), 1-1/(n+1), -1/(n+1),..., -1/(n+1)) and so <v, w> / (||v|| ||w||) = (-1/(n+1)) / ((1-1/(n+1))^2 + n/(n+1)^2) = -1/n. __________________________________________________________________________________ Question: --------- Is there a more immediate way to see that this number is -1/n ??? —Dan
On Nov 5, 2015, at 12:10 PM, Warren D Smith <warren.wds@gmail.com> wrote:
The optimal solution was unit vectors that are the N+1 vertices of a regular simplex in N-dimensional space centered at the origin. (N=3 for Asimov's problem, regular tetrahedron.)
These are anticorrelated somewhat, dot product of any two is -1/N minimizing correlation by making it maximally negative. My solution with 4 mutually orthogonal 8-vectors was optimal if we want zero correlation, which minimizes correlation if you meant the absolute value of the correlation...
On 05/11/2015 20:46, Dan Asimov wrote:
Yup. Maybe there is an easier way to see what the cosine of the angle between any two vectors from the center to a vertex of a regular n-simplex is, but the way I know is this:
__________________________________________________________________________________ The n+1 standard basis vectors in R^(n+1) form the vertices of a regular n-simplex whose center lies at
c = (1/(n+1), ..., 1/(n+1))
in R^(n+1). [...] Is there a more immediate way to see that this number is -1/n ???
Dunno whether it's much easier -- it's obviously more or less equivalent -- but if you start by putting n+1 vertices at n,-1,-1,...,-1 -1,n,-1,...,-1 -1,-1,n,...,-1 ... -1,-1,...,-1,n then their centroid is obviously at 0, their norms are all sqrt(n^2+n), and their inner products are all -2n+(n-1) [at this point it's obvious, if it wasn't already, that they are the vertices of a regular n-simplex], so cos theta = (-n-1)/[n(n+1)] = -1/n. -- g
On Thu, Nov 5, 2015 at 1:52 PM, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
n,-1,-1,...,-1 -1,n,-1,...,-1 -1,-1,n,...,-1 ... -1,-1,...,-1,n
This looks a lot like the matrix in Grover's algorithm, but that one has (n/2)-1 instead of n (and a normalization factor). -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
Let e0, … , en be n+1 unit vectors giving the vertices of the regular simplex centered on the origin of R^n. e0+ … +en = 0 (1) Take the inner product of each side of (1) with itself: (n+1)1 + (n+1)n c = 0 (2) where c is the cosine of the angle formed by any two distinct vectors. Solve (2) for c: c = -1/n. -Veit
On Nov 5, 2015, at 3:46 PM, Dan Asimov <asimov@msri.org> wrote:
Question: ---------
Is there a more immediate way to see that this number is -1/n ???
—Dan
participants (5)
-
Dan Asimov -
Gareth McCaughan -
Mike Stay -
Veit Elser -
Warren D Smith