
[Oct. 15th, 201110:06 am]
Jason

Here is a tiny javascript thing that reacts a little if you mouseover. I just threw it together in an hour after waking up wondering what sort of shapes you'd get if you randomly assigned directions to lattice points and followed them. It's regrettably slow in firefox although speedy enough in chrome. Dunno why.
The javascript toy has a builtin 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 ndimensional 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"; }


