1
$\begingroup$

I came from the programming world, i saw an exercise: "Calculate the average of a list of numbers in a functional way", then i saw an interesting answer after provide my solution.

So, lets say i have this list: $\{2, 4, 6, 8, 10\}$ I want to calculate the average, so that solution proceeded as next:

$$ \text{avg} = \frac{2 - \mathbf{0}}{1} + \frac{4 - \mathbf{2}}{2} + \frac{6 - \mathbf{3}}{3} + \frac{8 - \mathbf{4}}{4} + \frac{10 - \mathbf{5}}{5} $$

So we can say, starting from $\text{currentAverage} = 0$ and starting $\text{index} = 1 \in \{1,2,3,4,5\}$, we can calculate the average as next: $$ \sum_{i=1}^n \text{currentAverage} + \frac{(n_i - \text{currentAverage})}{\text{index}_i} $$

Where did this deduction come from? Thanks!

$\endgroup$
3
$\begingroup$

Let your list be $\{x_1, \ldots, x_n\}$. Define the average of the first $k$ numbers to be: $$ A_k = \frac{x_1 + \cdots + x_k}{k} $$ We are asked to show that: $$ A_k = A_{k-1} + \frac{x_k - A_{k-1}}{k} $$ First, let's stare at the previous average for a bit. Notice that it's easy to get the current average if those pesky denominators didn't exist. That is, it's easy to see a recurrence if we work with the total sums instead. With a little bit more work, we've derived the formula: \begin{align*} kA_k &= (k - 1)A_{k-1} + x_k \\ kA_k &= kA_{k-1} - A_{k-1} + x_k \\ A_k &= A_{k-1} + \frac{x_k - A_{k-1}}{k} \end{align*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.