Efficiently solving this recurrence relation. [ Better than O(N^2) ]

Question

I've a recurrence relation which goes something like this:

E( i, j ) = A[ i ] + A[ j ] + E( i+1, j-1 ) + E( i+2, j ) + E( i, j-2 ) ; if i != j

E( i, j ) = A[ i ] ; if( i == j )

E( i, j ) = 0 ; if i < 0 or j < 0

A[ i ] 1 <= i <= N; is simple integer array.

I want to solve for E(1, N) in time complexity better than O(N^2). I was wondering if we could find some closed form formula for this recurrence or maybe a clever method of computing the value of E(1, N)?

Any hints are welcome,
Thanks in advance.

Edit:
The actual problem is like this:

1. We have an array A[], and 2 Players take turns to play this game.
2. A player can pick the leftmost or rightmost number with probability 0.5 and adds it to his score(if there's single element left in array he will simply pick that number and the game ends).
3. Question is to find the expected score that Player1 will achieve.

Answer 1

About your recurrence relation:

It appears somewhat difficult because the write-up suggests, that for E(1,N) we need E(2,..) and E(3,..), each of which in turn requires other entries with yet higher "i", etcetera.

Now, rearrange the terms such that we have the E-term with the highest "i" isolated (a good idea in general with recurrence relations is to have a look at different arrangements to isolate a particular index - the highest, the lowest, the middle one, ...):

E(i+2,j) = E(i,j) - E(i,j-2) - E(i+1,j-1) - A(i) - A(j)

Then, shift all i down by 2 (simply rewriting the formula)

E(i,j) = E(i-2,j) - E(i-2,j-2) - E(i-1,j-1) - A(i-2) - A(j).

Then, for {i=1, j=N}, which is what you're looking for, we get:

E(1,N) = E(-1,N) - E(-1,N-2) - E(0,N-1) - A(-1) - A(N) = -A(N), because all other terms are zero.

(I assume, of course, that E(i,j) and A(i) are zero for i=0 / j=0; your specification was presumably incomplete when you specified the zero-values only for NEGATIVE indices, but not for the zero-indices).

Then, about your (edited) description of the underlying case - two players taking in turn from A, arbitrarily from left or right, until A is exhausted:

From the previous result, I don't think it's likely that your recurrence relation describes the underlying game, given the outcome -A(N)... Therefore, leave that recurrence relation aside (it's solved anyway for i=1). and have a look at the game itself for what relations we may derive.

[CONTINUED AFTER EDIT]

So far, I haven't come up with something that I can cast in a closed form, i.e. something that is faster than processing some kind of recurrence relations. For the moment, therefore, let's write down how we might describe the game in a way that lends itself to calculation.

Define the following quantities:

Let X(i,k) be the probability that item #i (in array A) still exists (i.e. has not yet been taken by any player) at the end of turn #k (counting turns from both players). Of course, k runs in our game from 1 to N, and so does i. For verification purposes we may note, that X(i,N) must be zero for all i: at the end of the game all elements have been taken.

In case we may need (in formula-evaluations) any values of X(i,k) outside the "normal" range, we assess:

X(i,k)=1 for {1<=i<=N; k=0}: initially all elements in A are still there.
X(i,k)=0 whenever i<1 or i>N: no elements ever exist outside the (original) range of A.

Next, let T(i,k) be the probability that element #i is taken (by any player) at turn #k exactly. That must be 0.5 * the probability that it is the leftmost element (currently), which is equivalent to saying that element #(i-1) does NOT exist at the end of the PREVIOUS turn, plus 0.5 * the probability that it is the rightmost element (currently), which in turn amounts to saying that element #(i+1) does not exist at the end of the previous turn, while all of that must be multiplied by the probability that element #i itself exists in the first place:

T(i,k) = X(i,k-1) * ( (1-X(i-1,k-1)) + (1-X(i+1,k-1)) ) / 2

The probability X(i,k) that element #i still exists after turn #k is the probability that it existed at the end of the previous turn, minus the probability that it is taken at turn #k:

X(i,k) = X(i,k-1) - T(i,k)

The probability that element #i winds up with player#1 is the summation over all turns k of T(i,k), but only counting HIS turns. Let's denote that quantity by P(i,1), where 1 stands for player #1.

P(i,1) = sum{ k=1,3,...: T(i,k) }

Likewise, for player #2:

P(i,2) = sum{ k=2,4,...: T(i,k) }

The expected score of player #1 is then the sum S(1):

S(1) = sum( i=1..N: P(i,1)*A(i) }, and likewise for player #2: S(2) = sum( i=1..N: P(i,2)*A(i) }

Looking at the above formula's I don't see a way to avoid an O(N2) method as regards time. Memory-usage can be O(N) as we may keep running totals and discard older 'element-wise'-data that won't be needed anymore. Given that - assuming you're not processing arrays A that are excessively long - the players wouldn't survive! - the O(n2) time-performance shouldn't be such an issue in practice.

int N  = sizeof(A);

// note on the code below: we'll use i as an integer running over the elements in A, and k running over the turns that players make.
// while in human parlance we would have them (both) run from 1 to N, the zero-based arrays of C++ make it more convenient to let them 
// run from 0 to N-1.

// initialize the running totals P(i), the accumulated (over turns) probabilities that element #i winds up with player #1.
// if we ever need the same for player #2, it's values are of course 1-P (that is: at the end of the game).
double* P = new double[N];
for (int i=0; i<N; i++)
{
  P[i] = 0; // before we start, there's little chance that player #1 has already taken any element.
}
// initialize the existence-array for the elements.
int* X = new int[N];
for (int i=0; i<N; i++)
{
  X[i] = 1; // initially all elements exist, i.e. have not yet been taken by any player.
}
// declare an array for processing the probabilities that elements are taken at a particular turn.
double* T = new double[N];

// iterate over the turns.
for (int k=0; k<N; k++)
{
  // for each element, calculate the probability that it is taken NOW.
  // the current values of X - the existence array - refer to the (end of the) previous turn.
  for (int i=0; i<N; i++)
  {
    // note: take care of the boundaries i=0 and i=N-1.
    if (i == 0)
    {
      T[i] = X[i] * ( 2 - X[i+1] ) / 2;
    }
    else if (i == N-1)
    {
      T[i] = X[i] * ( 2 - X[i-1] ) / 2;
    }
    else
    {
      T[i] = X[i] * ( 2 - X[i-1] - X[i+1] ) / 2;
    }
  } // element i
  // with the take-probabilities for this turn in place, update P - only at odd turns (i.e. k=even): P is for player #1 only.
  if (k % 2 == 0)
  {
    for (int i=0; i<N; i++)
    {
      P[i] += T[i];
    }
  }
  // finally - in this turn - update the existence array.
  for (int i=0; i<N; i++)
  {
    X[i] -= T[i];
  }

} // turn k

// result: calculate the expected score for player #1.
double score = 0;
for (int i=0; i<N; i++)
{
  score += P[i] * A[i];
}

--

Answer 2

Since probabilities are equal, this is just a counting problem.

Can you figure out that chances of picking A[j] on the k^th turn?