1
$\begingroup$

Is there any example of such a function $f$, preferably one defined on all $V^n$ and all positive integers $n$ where $V$ is some vector space? It must satisfy the following:

  1. $f(T) = f(\sigma(T))$ for any $T \in V^n$ and permutation $\sigma$
  2. $f((X,t,t)) = f((X,t))$ for any (possibly empty) sequence $X$ and $t \in V$
  3. $f(a+T) = a+f(T)$ for any $T \in V^n$ and $a \in V$ where $a+(t,...,u) = (a+t,...,a+u)$
  4. $f(B*T) = B*f(T)$ for any $T \in V^n$ and diagonal matrix $B$ where $B*(t,...,u) = (B*t,...,B*u)$
  5. $f$ is continuous on $V^n$ for each positive integer $n$

If there is no closed form, an algorithm to approximate it will be good enough.

The reason I am looking for such a function is that I want to find a way to determine the most probable original vector given a set of samples where some samples could be dependent on others. In another field it is called textual criticism but the criteria used there are extremely subjective, whereas I believe this model uses objective criteria and the results are reproducible, if this function exists in the first place. Permutation invariance and duplicate invariance are necessary to exclude identical copies (like those of internet-myths). Translation and stretch invariance seem to be logical requirements as well. If $f$ does not exist, can a proof be shown? Thanks a lot!

  • 0
    @Patrick: Not quite; I simply wanted stretch-invariance but do not know how best to state it. It is of course preferable if $V$ is $F^r$ for some field $F$, but if matrix multiplication is defined in terms of an action of a field on the elements of V, it would suffice for me.2011-12-28

2 Answers 2

3

Let us first consider the one-dimensional case, $V = \mathbb R$. Let $T = (x_1, x_2, \ldots, x_n)$ be the points sorted in ascending order with duplicates discarded, and $I = [x_1, x_n]$ be their convex hull. Associate each point $x_i$ with its Voronoi cell, that is, the interval of points in $I$ closer to it that to any other $x_j$. Define $f$ to be a weighted average of the $x_i$, with the weights being the length $\ell_i$ of the corresponding cell, $f((x_1,x_2,\ldots,x_n)) = \frac{\sum_{i=1}^n\ell_ix_i}{\sum_{i=1}^n\ell_i}.$

To show that this construction satisfies (2) and (5) even though we discarded exact duplicates, we only need to show that as two or more points simultaneously approach the same value, say $x^*$, the value of $f$ approaches its value with the points replaced with a single point at $x^*$. This follows from the fact that the total size of the corresponding Voronoi cells approaches the size of the cell that a single point at $x^*$ would have.

Since you only care about diagonal matrices $B$, you can apply this procedure independently to each coordinate axis of $V$.

  • 0
    Unfortunately I do not have a very good idea of what is the best way to analyse difference sources to obtain the most probable facts, given that the author of each source may not report what he knows but may simply state the same things as other sources, and some may even purposely state falsehoods, which may in turn be referred to, and so on.. For example, given 3 samples (0,0), (0,1), (1,1), the most likely original is (0,1), if the original is known to have elements from {0,1}. However if the original had elements from the real interval [0,1], what is the most probable original?2011-12-29
0

Your reason to want to find such a function, topped with Rahul's comment that says "Discard duplicates and take the mean" made me think of other such functions with a statistical background. Obviously the "Discard duplicates and take the mean" function does the job. But are there others? I thought about "Discarding duplicates and taking the variance of the vector $(v_1, \dots, v_n) \in V^n$ seen as a sample". That works too.

Note also that the set of all functions satisfying your properties is a convex space, because we've just shown it is non-empty, and given two functions $f$, $g$ that satisfy it, you can see that $\alpha f + (1-\alpha) g$ is in your function space also, for every $\alpha \in [0,1]$ (here I am assuming that $\alpha \times f(T)$ makes sense, thus the image of this function would need to be some subset of the complex numbers) or even better, for every $\alpha \in \mathbb R$ (i.e. it would be an affine space). I just thought I'd notice that.

Hope that helps,

  • 1
    I meant that I originally wanted $f$ to be a weighted sum of the input points where the weights are continuous functions, but thought it might be preferable to have only conditions on $f$ alone, so I included condition 4. If I remove condition 4, I would want the original condition to be satisfied. If we take the maximum in each coordinate, the resulting $f$ unfortunately cannot be expressed as a weighted sum of the input points where the weights are continuous functions, because they must each be 0 or 1 even in the 1-dimensional case. If $f$ is such a sum, I only need conditions 1,2,5.2011-12-31