Why does this algorithm converge?

52 Views Asked by At

Consider the following problem.

Let $p_1, \dots, p_n \in (0,1)$ such that $\sum p_i = 1$. Let $m > 0$ such that

$$ q_i := p_i + m \frac{p_i \log(p_i)}{\sum p_k \log(p_k)} < 1 $$

Suppose all $p_i$ are unknown and every $q_i$ is given. Note that also $m$ is given, because $\sum q_i =1+m$. The problem is to invert the relation to find $p_i$. Of course, one could use standard Newton methods for nonlinear systems, but consider this iterative algorithm:

Step 1: Let $p_i^0 = q_i$

Step 2: Let $p^{j+1}_i = q_i - m \frac{p^j_i \log (p^j_i)}{\sum p^j_k \log (p^j_k)}$

The sequences $p_1^j, \dots, p_n^j$ converge at the wanted $p_1, \dots, p_n$ (I made many simulations with Matlab).

I have absolutely no idea of why this happens. Is this a standard method? If you remove the assumption on $m$ such that $q_i < 1$ the algo fails.