Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose you have a set $S = \{r_1, ..., r_n :\, r_k \in (1, \infty)\, \forall \,k \in \{1,...,n\}\}$. Find a bijective mapping $f: \{0,...,n-1\}\rightarrow \{1,...,n\}$ that minimizes \begin{align*} \sum_{k=0}^{n-1}r_{f(k)}^{k} \end{align*} Solution: Let $f$ be a mapping that satisfies $k< j \, \rightarrow \, r_{f(k)} \ge r_{f(j)}$. In other words, $f$ sorts $S$ in non-increasing order. To prove optimality, consider a bijective mapping $g$ defined on the same domain and range, and suppose $g$ minimizes the sum. Further, suppose $g$ differs from $f$. Therefore, there must be some inversion: an index $i$ such that $r_{g(i)} < r_{g(i+1)}$. We will show that swapping these two images decreases the total sum, contradicting the optimality of $g$. Notice that if we only swap these two, then the remaining terms of the sum are unchanged. To show that the swap decreases the total sum, we must verify \begin{align*} r_{g(i+1)}^{i}+r_{g(i)}^{i+1} &< r_{g(i)}^{i}+r_{g(i+1)}^{i+1}\\ r_{g(i)}^{i+1} -r_{g(i)}^{i}&< r_{g(i+1)}^{i+1}-r_{g(i+1)}^{i}&\iff \\ r_{g(i)}^i(r_{g(i)} - 1)&<r_{g(i+1)}^i(r_{g(i+1)}-1)&\iff \end{align*} But this final inequality holds because each rate exceeds one and by assumption $r_{g(i)} < r_{g(i+1)}$. This contradicts the optimality of $g$, hence any mapping that deviates from sorting the rates in descending order is not optimal.


Now suppose you have a set $S = \{r_1, ..., r_n :\, r_k \in (0, 1)\, \forall \,k \in \{1,...,n\}\}$. Find a bijective mapping $f: \{0,...,n-1\}\rightarrow \{1,...,n\}$ that maxmizes \begin{align*} \sum_{k=0}^{n-1}r_{f(k)}^{k} \end{align*} Note: It is interesting to point out that the naïve attempt of sorting $S$ in ascending order fails to maximize the sum in certain cases. Take for example the set \begin{align*} \biggr\{\frac{1}{10}, \frac{1}{2}, \frac{4}{7}, \frac{3}{5}, \frac{2}{3}\biggr\}&\\ \biggr(\frac{1}{10}\biggr)^0 + \biggr(\frac{1}{2}\biggr)^1 + \biggr(\frac{4}{7}\biggr)^2 + \biggr(\frac{3}{5}\biggr)^3 + \biggr(\frac{2}{3}\biggr)^4&\approx 2.240061476\\ \biggr(\frac{1}{10}\biggr)^0 + \biggr(\frac{4}{7}\biggr)^1 + \biggr(\frac{2}{3}\biggr)^2 + \biggr(\frac{3}{5}\biggr)^3 + \biggr(\frac{1}{2}\biggr)^4&\approx 2.294373016 \end{align*}
You can verify that this second sum is optimal in Mathematica, using the following code

S = {1/10, 1/2, 4/7, 3/5, 2/3};
p = Range[0, 4];
perm = Permutations[S];
totals = Total[#^p] & /@ perm;
maxPos = First[Flatten[Position[totals, Max[totals]]]]
perm[[maxPos]]


So my question is: can you think of an efficient rule to maximize the second sum? Currently my best solution is to literally enumerate all $n!$ possible ways to order the terms. Also, why is this problem so much harder? I feel it has something to do with the unboundness of the first problem. A colleague of mine suggested that the solution space of first problem is convex while the second is not, though I do not have a good grasp on why that is. (I know the definition of convexity, but what part of the problem formulation makes the solution space second problem not convex?)

Any help / input would be greatly appreciated.

share|improve this question
    
One thing pointed out in math chat here by Dominic Michaelis and might help with the problem is that the smaller and larger numbers tend to be at the "end" of the summation, this is because they tend to change less with higher powers; numbers close to zero are still close to zero at high powers and numbers close to one are still close to one. I think this could help in understanding why 2/3 can "afford" to be later in the sum than one might naively think. –  Paul Plummer Jun 17 '13 at 8:06

3 Answers 3

up vote 2 down vote accepted
+100

Even though this won't answer your question here is some first input. Vincent Tjeng made and I made some numerics with Mathematica, this was his code (which I used too)

data = Table[someList = RandomReal[{0, 1}, 5];
    Ordering@
      Ordering@
        (Last@SortBy[{N[Total[#^(Range[Length@someList] - 1)]], #} & /@ 
      Permutations[someList], First])[[2]], {i, 1, 300000}];

If you want to try yourself take something smaller than 300000 because that takes several minutes.

And afterwards with Tally we counted which permutation was the best how often. The result ist the following one

\[ \begin{array}{cc} \text{Permutation} & \text{Count}\\ \{1,5,4,3,2\} & 18495 \\ \{1,3,4,5,2\} & 106342 \\ \{1,4,5,3,2\} & 81069 \\ \{1,2,3,4,5\} & 56819 \\ \{1,3,4,2,5\} & 14042 \\ \{1,4,3,5,2\} & 13085 \\ \{1,3,5,4,2\} & 2808 \\ \{1,2,4,5,3\} & 691 \\ \{1,2,3,5,4\} & 206 \\ \{1,3,2,4,5\} & 3136 \\ \{1,2,4,3,5\} & 1305 \\ \{1,4,3,2,5\} & 1994 \\ \{1,2,5,4,3\} & 8 \\ \end{array} \] Here 1 stands for the smalles and 5 for the biggest.

We see here that only in 905 Cases the last number wasn't the largest or the second smallest. This has a reason.

plot

In the plot you see how much the decrease if you put a number on another position. For example if you look at $x-x^2$ this says you how much the sum decreas if you put the number on the third position insteadt of the second position. As you see that for smaller numbers it is not that much of a problem if they are in the ende or only near the end.

So a better heuristic is the following: Put on position 1 the smallest value. Now it is much more difficult how to chose the next one. Should surely take one of the values which are around $0.5$ but you have to be carefull to take one which is in the middle of the values greater than $0.5$, because those values will decrease later more than small values do.

In the plot we see that very big and very small values don't change a lot when raising their powers. So in the last position there will be the largest, or the second smallest value. this is some heuristic I will think more about it.

share|improve this answer
    
Thank you for your research! Those graphs do begin to explain the strange behavior of optimal solutions, though I must say I am very surprised at the data you have compiled. I was beginning to think that all solutions followed an "ascending-descending" order (with potentially empty prefixes or suffixes), but clearly that is not always the case. I would like to know more about the values the data took on in the 905 outlier cases, as well as the cases where the up-down pattern is not present. I'll have to do some more test on my own. –  A.E Jun 17 '13 at 16:36
    
After no one took the bounty, I decided to give you the rep points. Thanks again for the work you did, even if it was a while ago. –  A.E Jul 20 '13 at 15:32
    
@Orangutango Oh thanks a lot. I will have holidays soon there I can think more about it –  Dominic Michaelis Jul 20 '13 at 15:39

In both cases, because of associativity of addition, the solutions have to be "swap-immune," meaning that the optimal order can't be improved by a position swap. In the first case, this is sufficient to show that the solution is unique and ordered.

So in the second case, on on (0,1), is swap-immunity sufficient to show uniqueness? If so, then a program like the one below (in perl) should reliably find the solution in polynomial time. I don't claim this to be a proof. I just tried it out on a few cases and the solution was invariant to the starting permutation.

use List::Util qw(shuffle);
@x= (.1,.5, 0.571428571,.6,.6666666667);
@s = shuffle(@x);
for ($i=0; $i<scalar(@x); $i++){
    	for ($j=0; $j<scalar(@x); $j++){
    		if ( $s[$i]**$i + $s[$j]**$j < $s[$i]**$j + $s[$j]**$i){
    			swap($i,$j);
    			$j=0; #restart the search
    		}
    	}
}
    print join(',',@s);
    sub swap {
    	my ($i,$j) = @_;
    	my $t = $s[$i];
    	$s[$i] = $s[$j];
    	$s[$j] = $t;
    }  
share|improve this answer
    
I am concerned that this could run into local maxima: what if no single swap improves the total, but rather it requires a permutation that would need multiple swaps? Can you show that this is cannot be the case? That is, can you show that a given solution can be iteratively transformed via a strictly increasing sequence of solutions to achieve optimality? Also, I am not convinced of polynomial runtime, since your inner counter resets an arbitrary number of times. Can you bound the number of times that you restart the search with a polynomial of the input size? –  A.E Jun 18 '13 at 21:49
    
You're right--I looked at 3-cycles and found a counter-example to my question above. It won't let me post the image as an update, so here's a link. –  Stanislav Jun 20 '13 at 1:17

Some additional input as a follow-up to Dominic Michaelis': I've modified the code slightly so that you can actually check the values of the "outlier" data.

The code now runs as follows:

n = 5;
(actualValues[#] = {}) & /@ Permutations[Range[n]];
rankingList = Table[sample = RandomReal[{0, 1}, n];
   sortedSample = (Last@
       SortBy[{N[Total[#^(Range[Length@sample] - 1)]], #} & /@ 
         Permutations[sample], First])[[2]];
   sortedSampleRanking = Ordering@Ordering@sortedSample;
   actualValues[sortedSampleRanking] = 
   Append[actualValues[sortedSampleRanking], sortedSample];
   sortedSampleRanking
   , {i, 1, 1000}];
Tally@rankingList

(*{{{1, 3, 4, 5, 2}, 367}, {{1, 4, 5, 3, 2}, 283}, {{1, 4, 3, 2, 5}, 6}, {{1, 3, 4, 2, 5}, 41}, {{1, 2, 3, 4, 5}, 173}, {{1, 5, 4, 3, 2}, 53}, {{1, 3, 5, 4, 2}, 10}, {{1, 4, 3, 5, 2}, 46}, {{1, 3, 2, 4, 5}, 16}, {{1, 2, 4, 5, 3}, 2}, {{1, 2, 4, 3, 5}, 3}}*)

You can now extract the actual values of certain rankings that you are interested in by running the following code

actualValues[{1, 2, 3, 5, 4}] (*or whatever other ranking*)

Which in the above case gives the following results.

(*{{0.150845, 0.579054, 0.693527, 0.636326, 0.8711}, {0.50505, 0.620839, 0.632839, 0.624155, 0.98465}, {0.342148, 0.555461, 0.630722, 0.604628, 0.927428}}*)

From the small sample size that we have, it does appear that "unexpected" rankings occur mostly when the two or more numbers that occur in unexpected positions are very close to each other in value.

share|improve this answer

Your Answer

 
discard

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.