I created a certain algorithm and now I try to prove it's convergence. Here is the essence of the algorithm:

Given are finite sets $A_i$, positive constants $\alpha_a$, and a sequence $ \vec{\delta}^{(k)} \in \mathbb{R}^n$: $$ A_1,\; \ldots,\; A_n \subset \mathcal{A} $$ $$ B_a = \{i : a \in A_i\}$$ $$ \sum_{a\in \mathcal{A}}\alpha_a = n, \quad 0 < \alpha_a < |B_a| $$ $$\delta_i^{(0)} = 1 \quad i = 1,2,\; \ldots, \;n$$ $$ \beta_a^{(k)} = \sum_{i \in B_a} \delta_i^{(k)} $$ $$ \delta_i^{(k+1)} = \left(\sum_{a\in A_i} \frac{\alpha_a}{\beta_a^{(k)}}\right)^{-1} $$ Prove that $\vec{\delta}^{(k)}$ converges.

I did some numerical experiments but I am not sure that the bounds on $\alpha_a$ are sufficient. You can make stronger assumptions if you want. I'm just lookgin for an idea how to prove this.

Edit: This may help: in experiments this function is always increases: $$ \sum_{a \in A} \alpha_a \log\frac{\alpha_a}{\beta_a} - \sum^n_{i=1} \log \sum_{a\in A_i} \frac{\alpha_a}{\beta_a}$$

Edit 2: You can assume $|A_i| \geq 2 $

  • 1
    $\begingroup$ Is the third line a condition you impose on the constants $\alpha_a$ ? $\endgroup$ Feb 17, 2011 at 12:06
  • $\begingroup$ I suppose the $\alpha_a$ can be positive reals? Otherwise, if you pick singletons for all the sets in $\mathcal{A}$, the third line implies that no integer $\alpha_a$ can satisfy the inequalities. I'm trying to figure out what this all means and I can't see why you would need such a contrived sequence. Some background would definitely help! $\endgroup$ Feb 17, 2011 at 12:18
  • $\begingroup$ Looking at the final line, I can see a problem. Suppose $a \notin A_i$, then the sum is empty and $\delta_i^{(k+1)}$ is infinite. $\endgroup$ Feb 17, 2011 at 12:24
  • $\begingroup$ @Raskolnikov: $a$ is the summation variable, it's not free. The sum is only empty if $A_i$ is empty; I presume it was a tacit assumption that the $A_i$ are non-empty. $\endgroup$
    – joriki
    Feb 17, 2011 at 12:39
  • 1
    $\begingroup$ BTW, I agree with Raskolnikov that some background would definitely help. I pointed out some of the structure of the problem in my attempt at an answer, but since you came up with all this, and from what your doing with the logarithms, I would expect that you could tell us a bit more about what it all means? $\endgroup$
    – joriki
    Feb 17, 2011 at 12:49

1 Answer 1


It's not quite clear what you mean by "$\vec{\delta}^{(k)}$ converges to a unique point", since you've specified initial values, so if $\vec{\delta}^{(k)}$ converges this will by definition be to a unique point. I assume that you mean that it converges to a point which is independent of the initial values? If so, that is not the case, since multiplying the initial values by a constant factor results in the entire sequence being multiplied by a constant factor, so the limit could only be "unique" in the above sense up to a constant factor.

It seems that a useful way to approach these equations is to eliminate $\beta_a^{(k)}$ by substituting it from the upper iteration step into the lower iteration step, and then bringing the reciprocal on the right-hand side over to the left-hand side, yielding

$$\sum_{a\in A_i} \frac{\alpha_a \delta_i^{(k+1)}}{\sum_{j\in B_a} \delta_j^{(k)}} = 1\;.$$

If we drop the superscripts labeling the iterations steps, we get the equation that determines the fix point(s). Note a) that the sum of these equations over all $i$ is automatically satisfied, and b) all $n$ equations would be satisfied if $\sum_{j\in B_a} \delta_j$ were independent of $a$. So the iteration can be viewed as solving the problem of choosing weights $\delta_i$ for the sets such that for each point $a$ the sum over the weights of the sets in which it is contained is the same. This also makes sense of the fact that a constant factor in the weights is irrelevant.

  • $\begingroup$ I updated the quesion. The problem is to show that the sequence does not diverge to infinity. $\endgroup$ Feb 17, 2011 at 12:47
  • $\begingroup$ @Łukasz Lew: That's not what you wrote in the updated question. It says there whether $\delta$ converges. It can either converge, diverge to infinity, or diverge without going to infinity. $\endgroup$
    – joriki
    Feb 17, 2011 at 12:51
  • $\begingroup$ Indeed. I want it to converge. I hope it converges. $\endgroup$ Feb 17, 2011 at 14:24

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.