Solving algebraic recurrence relations on a cyclic graph

Question

I have a set of $n$ variables $p_1, \ldots p_n$ with $0 \leq p_i \leq 1$ and a defining equation for each of one of the forms:

1. $p_i = 0$.
2. $p_i = 1$
3. $p_i = p_j p_k$ for some $j, k$ with $i, j, k$ all distinct.
4. $p_i = q p_j + (1 - q) p_k$ for some other $j, k$ and $0 < q < 1$

(i.e. these are activation probabilities for distributions of boolean valued random variables, each of which is either a constant, a mixture of two others or a conjunction of two others)

In general there may be and probably are cycles in the equations where the definition of $i$ depends on the definition of $j$ depends on the definition of $i$, etc.

For a given set of equations, I would like to determine:

1. If there is a unique solution to these equations
2. A closed form for it, or at least an algorithm for producing an exact answer, if there is one.

(I am not optimistic about the second, but it sure would be nice)

I'd also appreciate literature pointers if this refers to a common class of things that I just don't know the term for.

In practice I will probably just solve this approximately as an iterative solution - the multiplicative terms suggest that it will tend to converge to a fixed point pretty fast - but I would like to know if there's a better way.

Answer 1

Here are a few comments. Perhaps with further conditions on the types of equations more can be said, but in this generality, I don't think much can.

• Equations of types (1) and (2) immediately allow one to eliminate variables. Ignore type (3) at first to get from the type (4) equations a system of simultaneous linear equations which can analyzed in the standard way to eliminate more variables and reduce to a set of independent variables. Some of the type (3) equations might become type (4) in the process (perhaps we have $p_1=p_2p_3$ but discover $p_2=1/3$ and $p_3=2/5p_4+1/2$). Expressing everything in terms of the independent variables and expanding out the type (3) equations gives a polynomial or perhaps a system of polynomials in several variables.

• Even if there is a single polynomial in one variable, there might be a unique solution but no closed form for it. The equation $x^5-3x+1=0$ has a unique real root (slightly bigger than $\frac13$) in $[0,1].$ But there is no closed form for it. The system of equations $$a=0, b=1, c=\frac12a+\frac12b, d=bx, e=dx, f=ex, g=fx, h=gx$$ together with $$x=\frac13h+\frac23c=\frac13x^5+\frac13$$ determine this $x.$

• Similar families of equations could give any polynomial (I think) $a_nx^n+\cdots+a_2x^2-x+a_0=0$ where the $a_i$ are non-negative with $a_0+\sum_{i=2}^na_i \le 1.$ Certainly a broader class of polynomials is possible.
• I imagine (though I might be wrong) that there might be two (or more) solutions but only one which is approached by iteration. It might depend delicately on the exact coefficients and no simple graph theory analysis would help with this.