sum of a geom series declaying at exp(-kx)

Question

Resource allocation problem

Given

1. T, total amount of resources
2. N, targets of resource allocation
3. T > 0; N > 1; T < N

Allocate resources amongst targets, s.t.

$$0 <= allocation_{i} < 1$$ $$allocation_{i+1} < allocation_{i}$$ $$\sum_{i=1}^N allocation_i <= T$$

$$minimize (T - \sum_{i=1}^N allocation_i)$$

An important freedom and a constraint is that the solution need not be the most optimal; however it must arrive within just a few iterations (like, say, < 10) because of runtime limitations.

I started with $$allocation_i = e^{-ki}$$ and locate k but that only led me to a problem with a numerical solution which can take long to solve. I want to explore if there are other monotonically decreasing functions that will solve faster and provide a reasonably good allocation.

Some illustrative values of T, N if it helps. N typically in (10, 1000); T/N typically in (0.05, 0.5)

EDIT: I rewrote the question taking into account the comments, and also reformatted it. I hope this is clearer. This is my first post here and I am just learning how-to form the question :-)

Thanks

Answer 1

As I read it, the terms of the series are $e^{-ki}, i=0..N $.

This is just a geometric series with sum

$\begin{array}\\ s &=\sum_{i=0}^N e^{-ki}\\ &=\sum_{i=0}^N (e^{-k})^{i}\\ &=\dfrac{1-(e^{-k)^{N+1}}}{1-e^{-k}}\\ &=\dfrac{1-r^{N+1}}{1-r}\\ \end{array} $

where $r = e^{-k} $.

So you want $T = \dfrac{1-r^{N+1}}{1-r} =\sum_{i=0}^N r^i $.

This can only be solved numerically for $N \ge 5$. Once we get $r$, then $k = -\ln(r)$.

If $T$ is close to $N+1$, then, if we approximate $r = 1-d$ where $d$ is small, the sum is

$\begin{array}\\ T &=\sum_{i=0}^N r^i\\ &=\sum_{i=0}^N (1-d)^i\\ &\approx\sum_{i=0}^N (1-id) \qquad\text{for quite small }d\\ &=N+1-d\sum_{i=0}^N i\\ &=N+1-dN(N+1)/2\\ \end{array} $

so $d =2\dfrac{N+1-T}{N(N+1)} $.

Answer 2

I post this as another answer for clarity.

There seems to be a much simpler way to allocate resources for you in the special case of:

$$T \leq \frac{N+1}{2}$$

Considering the value ranges you provided this condition seems to be fulfilled.

Then we use the simple fact:

$$\sum_{i=1}^N i=\frac{N(N+1)}{2}$$

Now let us divide both sides by $N$ and reverse the order of summation:

$$\sum_{i=1}^N \frac{i}{N}=\frac{N+1}{2}$$

$$\sum_{i=1}^N \frac{N-i+1}{N}=1+\frac{N-1}{N}+\frac{N-2}{N}+\dots+\frac{1}{N}=\frac{N+1}{2}$$

Finally we introduce a parameter $p$ such that:

$$p=\frac{2T}{N+1} \leq 1$$

Then:

$$p \sum_{i=1}^N \frac{N-i+1}{N}=T$$

$$T=\frac{2T}{N+1}+\frac{2T(N-1)}{N(N+1)}+\frac{2T(N-2)}{N(N+1)}+\frac{2T(N-3)}{N(N+1)}+ \dots$$

Each term above is the part of a resource allocated to each of the $N$ targets.

The largest part is:

$$A_1=p=\frac{2T}{N+1}$$

The smallest part is:

$$A_N=\frac{p}{N}=\frac{2T}{N(N+1)}$$

---

In addition:

If the first recipient should always get a full resource ($A_1=1$) you can just put it aside and rename the parameters:

$$T-1 \to T^*$$

$$N-1 \to N^*$$

---

Important update!

We can actually relax the above condition on $T$ using the relations:

$$\sum_{i=N+1}^{2N} i=\frac{N(3N+1)}{2}$$

$$\sum_{i=2N+1}^{3N} i=\frac{N(5N+1)}{2}$$

and so on.

Thus, we can make the condition to be:

$$T \leq \frac{3N+1}{4}$$

$$T \leq \frac{5N+1}{6}$$

And finally for any integer $M \geq 1$:

$$T \leq \frac{M N+1}{M+1}$$

I will allow you to derive the expression for $p$ and the allocations yourself.

Answer 3

Considering the edited question and marty cohen's answer, I don't see a more simple way that the geometric series.

Even though I don't see which function $f(i)$ under the sum could get us an analytic solution for the parameter, geometric series with $f(i)=p^i$ still allow us a simple numerical scheme to find $p$.

---

Let's first allow the first target to get a full resource. It would be easy to subtract some part of it and add to the second target if needed.

So denoting the allocations $A_i$ we always have $A_1=1$.

---

For the geometric series we have the condition:

$$\sum_{i=0}^{N-1} A_{i+1}=\sum_{i=0}^{N-1} p^i=T$$

$$p<1$$

$$\frac{1-p^N}{1-p}=T$$

We obtain an algebraic equation of degree $N$:

$$p^N-T p+T-1=0$$

Note that for $N >> 1$ and $p<1$ we have approximately:

$$p \approx \frac{T-1}{T}$$

This will be our first guess for the numerical iterations.

Newton's method consists of picking some $p_0$ and then computing the next iterations as:

$$p_{k+1}=p_k-\frac{F(p_k)}{F'(p_k)}$$

In our case:

$$F(p)=p^N-T p+T-1$$

$$F'(p)=Np^{N-1}-T$$

Thus:

$$p_0=\frac{T-1}{T}$$

$$p_{k+1}=p_k-\frac{p_k^N-T p_k+T-1}{Np_k^{N-1}-T}$$

---

Let's check this method for $T=300$ and $N=1000$:

$$p_0=\frac{299}{300}=\color{blue}{0.996}6666\dots$$

$$p_1=p_0-\frac{p_0^{1000}-300 p_0+299}{1000p_0^{999}-300}=\color{blue}{0.99680}083907776694848\dots$$

$$p_2=\color{blue}{0.996802135}036332828\dots$$

$$p_3=\color{blue}{0.99680213516858413}5\dots$$

Since Newton's method has quadratic convergence, the number of correct digits approximately doubles at each step.

---

Now everything depends on the computational resources you have and the accuracy you need.

(Update: See another answer for a more simple method, for a certain condition on $T,N$)