lack of convergence around cycles

[jeisner]

I was having trouble getting forward-backward to converge in the cyclic word graph, even when I kept only the swapadj edges (so there weren't many) and made them be low-probability (so we'd get fast numerical convergence).

I switched to trying tiny cyclic graphs and now I suspect the current version of the FIFO strategy is just not a stable way to solve a linear system.

The following makes a symmetric graph on n vertices and runs it to convergence. We should get a(I) = 1/(1-r), for all I from 1 to n. Converges instantly for n:=1 and also if I update n:=2, but hangs if I try n:=3.

% make n vertices.  Do we have any better way to enumerate integers in a range?
n := 1.
is_int(1). is_int(2). is_int(3). is_int(4). is_int(5). is_int(6). 
v(I) :- is_int(I) for I <= n.

% set up the linear system
a(I) += 1 for v(I).
a(I) += r*a(J) / n for v(I), v(J).
r := 1/2.

After a while waiting for n:=3, I interrupted and saw that the values had risen above the expected 2.0 (that is, 1/(1-r) with r=1/2), e.g.

a/1
===
a(1) = 4.391438444536755.
a(2) = 4.633680118549428.
a(3) = 2.8884755859682683.

and then when I tried to trace a(1) and interrupted again,

a/1
===
a(1) = 5.817270283134675.
a(2) = 5.629541956511834.
a(3) = 4.330876944346437.

If the numbers ever get above 2.0 on average, they will zoom off unstably to infinity (consider the case for 1 vertex). However, as long as all the numbers are <= 2.0, we are replacing the second summand with something <= 1, so the numbers should remain 2.0. Hence I don't understand what drives them above 2.0 in the first place.

[timvieira]

btw, there is a built in for get a list of numbers called range.

v(I) :- I in range(1,n+1).

range has three variants

> query range(4)
range(4) = [0, 1, 2, 3].
> query range(1,4)
range(1,4) = [1, 2, 3].
> query range(1,4,2)
range(1,4,2) = [1, 3].

[timvieira]

XREF: #19 - default prioritization.