The javascript toy has a built-in bias towards paths going down and to the right, just because I wanted more visual interest than the short paths that came out of the uniform distribution over the four directions. I kind of wonder what happens in higher dimensions. My thoughts tend toward think along the paths 'upstream': suppose I've got some vertex in my hand and I want to extend the path by finding some one of my neighbors that's pointing at me. What are the odds there's at least one? (This line of thinking is just an approximation, ignoring the possibility that it turns out to actually be a node that's already in my 'downstream')

Well, in an n-dimensional square lattice, I've got 2n neighbors, and each one of them picks one of 2n directions at random. Each one has a 1 in 2n chance of pointing towards me. The chance of none of them pointing towards me is (1 - 1/2n)^(2n) which is 1/e in the limit. So my gut says that things don't actually spiral out of control in higher dimensions. I guess I could do an experiment with hash functions or something...

---

Huh! It empirically seems like the average time until you hit a cycle in n dimensions is exactly 2n.

2 4.8731

3 6.459

4 8.3785

5 10.2061

6 12.1667

7 14.2784

8 15.7819

9 17.8955

10 20.4033

11 22.0062

12 24.0271

13 26.1572

14 27.9639

15 30.0764

16 31.7978

17 34.1895

18 35.5108

#!/usr/bin/perl

use Digest::MD5 qw(md5);

$LIMIT = 1000;

sub iter {

my ($x, $salt) = @_;

my $new = [@$x];

my $str = join (" ", @$x);

my ($p, $n) = unpack("LL", md5($salt, $str));

$new->[$p % @$x] += 2 * ($n % 2) - 1;

($str, $new);

}

sub period {

my ($dim, $salt) = @_;

my $x = [(0) x $dim];

my %seen = ();

my $t = 0;

while ($t < $LIMIT) {

my $str2 = join (" ", map {sprintf("% 3d",$_)} @$x);

# print "> $str2\n";

($str, $x) = iter($x, $salt);

if ($seen{$str}) { return ($t, $t - $seen{$str}); }

$seen{$str} = $t;

$t++;

}

warn "exceeded limit";

return ($LIMIT, $LIMIT);

}

sub avg {

my ($dim, $sample) = @_;

my $sum = 0;

for my $i (1..$sample) {

my ($t, $per) = period($dim, $i);

$sum += $t;

}

return $sum / $sample;

}

for my $j (2 .. 18) {

my $a = avg($j, 10000);

print "$j $a\n";

}