Sum considers RandomInteger[] as a constant

Question

Perhaps this is expected behavior, but I was kind of surprised by the following:

a[k_] := RandomInteger[{-1, 1}]; 
f[n_] := Sum[a[m], {m, n}]
Table[f[n], {u, 5}]
(*{0, n, -n, -n, -n}*)

I was expecting it to simply give up, and return Sum[RandomInteger[{-1, 1}], {m, n}]. Instead, it looks like when doing the symbolic sum, Sum considers a[m] to be a constant that is independent of m, pulls it outside of the sum, and then evaluates Sum[1, {m, n}] times it.

In contrast, using an explicit value of $n=5$ gives the expected results:

Table[f[6], {u, 5}]
(*{-2, 2, -5, 0, 1}*)

I looked in the Possible Issues section of Sum and didn't see anything addressing this. Is there a reason for why Sum considers a RandomInteger[] term in the summand to have the same value for all terms?

Answer 1

If you don't want a[k] to evaluate in Sum's symbolic probes you can add ?NumericQ:

a[k_?NumericQ] := RandomInteger[{-1, 1}];

f[n_] := Sum[a[m], {m, n}]

f[n]

Sum[a[m], {m, n}]

---

I am by no means an advanced user of Sum but belisarius encouraged me to make this answer more useful so I shall attempt to do so.

Your expectation of having Sum[RandomInteger[{-1, 1}], {m, n}] returned would be truly surprising as it would require a[m] to partially evaluate to RandomInteger[{-1, 1}] but evaluate no further. (That is a rather tricky problem in itself and one I devoted considerable effort to in How do I evaluate only one step of an expression?). Normal evaluation requires that it either stay as a[m] or fully evaluate to -1 or 1.

I am not qualified to discuss the intent of the developers or the implications of the design they chose but it seems that (often) Sum first attempts to symbolically evaluate the summand (a[m]) and then uses its evaluated form in place of the original. This is what I meant by "Sum's symbolic probes" in my first remark.

Given this (apparent) design you must make sure than the summand never symbolically evaluates to something incomplete or the sum may be incorrect.

f[_?EvenQ] = -1;
f[_?OddQ] = 8;
f[s_Symbol] = 0;

Sum[f[n], {n, 1000}]
Sum[f[n], {n, 1*^11}]
Sum[f[n], {n, x}]

3500

0

0

With {n, 1000} Sum proceeds numerically therefore the problem does not appear. However the other two sums symbolic evaluation is attempted and the result is equivalent to Sum[0, . . .].

I don't know if you will find this helpful or if I am merely restating what you already know but there it is.

Answer 2

To add to Mr.Wizard's answer: There are some remarks in the documentation for Sum that hint at the behavior DumpsterDoofus has observed.

From the "Details" section:

• If the range of a sum is finite, i is typically assigned a sequence of values, with f being evaluated for each one.
  ...
• If a sum cannot be carried out explicitly by adding up a finite number of terms, Sum will attempt to find a symbolic result. In this case, f is first evaluated symbolically.

I'm not sure I would call the hints definitive. The threshold of 10^6 terms might change over time as version and technology evolve. The threshold is one of the SystemOptions, "SymbolicSumThreshold" -> 1000000.

I think of Total as the function for adding up, although you have to generate the whole list of values first, which can be a drawback. I think of Sum and NSum as a symbolic sum evaluator and estimator, respectively. But given the drawback of Total on very long sums, there is a way to force Sum to work step by step.

From the "Possible Issues" section:

Force procedural summation to obtain the expected result:

Sum[f[n], {n, 10^6 + 1}, Method -> "Procedural"]

However, note that the OP's example, Table[f[n], {u, 5}], would still be done symbolically because a "procedural" evaluation with a symbolic limit is impossible.