|
[Oct. 15th, 2011|10: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 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";
}
|
|
