Is there a formula to determine the approx. steps needed to calculate the area of a $N \times N$ grid?
Suppose we have a discrete random walk on $\mathbb{Z}^2$ starting at $(0,0)$ and each "step" is determined by adding one of the vectors $(1,0), (−1,0), (0,1), (0,−1)$. The walk continues in the same manner for many steps and cannot step outside its boundary edges or corners.
Anytime the walk completes a unit square perimeter, it's added to the total area so far. This walk continues until every unit square has been completed. As the comment section noted, this is equivalent to walking every segment.
Example
A random walk on a $150\times150$ grid in progress…
EDIT
Finally wrote a C program to traverse $N \times N$ grids.
For example, the $10 \times 10$ grid is iterated $100$ times and the average steps taken.
10x10 Grid, Total Steps: 2455
10x10 Grid, Total Steps: 2206
10x10 Grid, Total Steps: 1872
10x10 Grid, Total Steps: 2390
10x10 Grid, Total Steps: 2044
10x10 Grid, Total Steps: 2411
10x10 Grid, Total Steps: 2976
10x10 Grid, Total Steps: 2718
10x10 Grid, Total Steps: 2669
10x10 Grid, Total Steps: 3641
10x10 Grid, Total Steps: 1879
10x10 Grid, Total Steps: 2288
10x10 Grid, Total Steps: 1906
10x10 Grid, Total Steps: 1688
10x10 Grid, Total Steps: 1857
10x10 Grid, Total Steps: 2571
10x10 Grid, Total Steps: 3085
10x10 Grid, Total Steps: 2274
10x10 Grid, Total Steps: 3288
10x10 Grid, Total Steps: 2096
10x10 Grid, Total Steps: 2415
10x10 Grid, Total Steps: 1850
10x10 Grid, Total Steps: 2113
10x10 Grid, Total Steps: 1926
10x10 Grid, Total Steps: 3149
10x10 Grid, Total Steps: 2189
10x10 Grid, Total Steps: 1873
10x10 Grid, Total Steps: 1662
10x10 Grid, Total Steps: 3776
10x10 Grid, Total Steps: 3109
10x10 Grid, Total Steps: 1723
10x10 Grid, Total Steps: 2088
10x10 Grid, Total Steps: 2726
10x10 Grid, Total Steps: 1897
10x10 Grid, Total Steps: 1935
10x10 Grid, Total Steps: 1719
10x10 Grid, Total Steps: 2358
10x10 Grid, Total Steps: 2501
10x10 Grid, Total Steps: 3118
10x10 Grid, Total Steps: 2870
10x10 Grid, Total Steps: 2459
10x10 Grid, Total Steps: 3090
10x10 Grid, Total Steps: 1862
10x10 Grid, Total Steps: 2370
10x10 Grid, Total Steps: 1905
10x10 Grid, Total Steps: 2063
10x10 Grid, Total Steps: 2255
10x10 Grid, Total Steps: 2484
10x10 Grid, Total Steps: 2861
10x10 Grid, Total Steps: 1535
10x10 Grid, Total Steps: 2026
10x10 Grid, Total Steps: 3210
10x10 Grid, Total Steps: 3116
10x10 Grid, Total Steps: 2013
10x10 Grid, Total Steps: 2204
10x10 Grid, Total Steps: 1668
10x10 Grid, Total Steps: 1614
10x10 Grid, Total Steps: 2347
10x10 Grid, Total Steps: 2694
10x10 Grid, Total Steps: 4518
10x10 Grid, Total Steps: 2213
10x10 Grid, Total Steps: 3105
10x10 Grid, Total Steps: 2483
10x10 Grid, Total Steps: 1900
10x10 Grid, Total Steps: 2732
10x10 Grid, Total Steps: 3267
10x10 Grid, Total Steps: 2392
10x10 Grid, Total Steps: 2540
10x10 Grid, Total Steps: 2805
10x10 Grid, Total Steps: 2872
10x10 Grid, Total Steps: 5039
10x10 Grid, Total Steps: 3851
10x10 Grid, Total Steps: 2909
10x10 Grid, Total Steps: 2081
10x10 Grid, Total Steps: 2621
10x10 Grid, Total Steps: 2561
10x10 Grid, Total Steps: 2296
10x10 Grid, Total Steps: 1655
10x10 Grid, Total Steps: 3922
10x10 Grid, Total Steps: 3123
10x10 Grid, Total Steps: 4437
10x10 Grid, Total Steps: 2631
10x10 Grid, Total Steps: 2175
10x10 Grid, Total Steps: 2606
10x10 Grid, Total Steps: 2214
10x10 Grid, Total Steps: 2831
10x10 Grid, Total Steps: 2565
10x10 Grid, Total Steps: 3157
10x10 Grid, Total Steps: 2268
10x10 Grid, Total Steps: 1704
10x10 Grid, Total Steps: 2817
10x10 Grid, Total Steps: 2695
10x10 Grid, Total Steps: 2102
10x10 Grid, Total Steps: 4982
10x10 Grid, Total Steps: 2618
10x10 Grid, Total Steps: 2219
10x10 Grid, Total Steps: 4198
10x10 Grid, Total Steps: 3987
10x10 Grid, Total Steps: 1868
10x10 Grid, Total Steps: 2375
10x10 Grid, Average Steps: 2564
Similar grid and graph results follow:
10x10 Grid, Average Steps: 2564
20x20 Grid, Average Steps: 13829
30x30 Grid, Average Steps: 34849
40x40 Grid, Average Steps: 69704
50x50 Grid, Average Steps: 112535
60x60 Grid, Average Steps: 178182
70x70 Grid, Average Steps: 249028
80x80 Grid, Average Steps: 354800
90x90 Grid, Average Steps: 456223
100x100 Grid, Average Steps: 575570
QUESTION
Given an $N \times N$ grid, is there a way to devise a formula to find the approx. number of random steps needed to compute its area based upon these program results?
Maybe a Lagrange Interpolating Polynomial like this:
$f(x) = \\ \begin{array}{c} \frac{31381 x^9}{8640000000000}-\frac{1427173 x^8}{806400000000}+\frac{1549913 x^7}{4200000000}-\frac{123941687 x^6}{2880000000}+\frac{886369883 x^5}{288000000}-\frac{1602458819 x^4}{11520000}+\frac{17031670657 x^3}{4320000}-\frac{67368570503 x^2}{1008000}+\frac{1020468443 x}{1680}-2208005 \end{array}$
Thanks.
// Calculate the area of a N×N grid using a 2D random walk.
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <time.h>
#include <random>
unsigned int GRID_SIZE;
std::minstd_rand simple_rand;
typedef struct
{
int xF;
int yF;
int xT;
int yT;
} FromTo;
typedef struct
{
FromTo FT;
bool walked;
} segment;
int xFrom, yFrom, xTo, yTo;
segment* xPaths[1000];
segment* yPaths[1000];
void PathsCheck(segment** Paths)
{
int i=0, j=0;
segment* Segments;
for (i = 0; i < GRID_SIZE; i++)
{
Segments = Paths[i];
for (j = 0; j < GRID_SIZE; j++)
{
// Check for reversible walks {(0,0),(1,0)} or {(1,0),(0,0)}
if ((((Segments[j].FT.xF == xFrom) && (Segments[j].FT.yF == yFrom)) &&
((Segments[j].FT.xT == xTo) && (Segments[j].FT.yT == yTo))) ||
(((Segments[j].FT.xT == xFrom) && (Segments[j].FT.yT == yFrom)) &&
((Segments[j].FT.xF == xTo) && (Segments[j].FT.yF == yTo))))
{
Segments[j].walked = true;
return;
}
}
}
}
int PathsStats(segment** Paths)
{
int i = 0, j = 0, segmentsTraversed = 0;
segment* Segments;
for (i = 0; i < GRID_SIZE; i++)
{
Segments = Paths[i];
for (j = 0; j < (GRID_SIZE - 1); j++)
{
if (Segments[j].walked)
{
segmentsTraversed++;
}
}
}
return segmentsTraversed;
}
void GenerateRandomWalk(void)
{
// (0,3) (1,3) (2,3) (3,3)
// (0,2) (1,2) (2,2) (3,2)
// (0,1) (1,1) (2,1) (3,1)
// (0,0) (1,0) (2,0) (3,0)
xFrom = xTo;
yFrom = yTo;
do
{
switch (simple_rand() % 4)
{
case 0: if (yTo != (GRID_SIZE - 1)) yTo++; break; // up
case 1: if (yTo != 0) yTo--; break; // down
case 2: if (xTo != 0) xTo--; break; // left
case 3: if (xTo != (GRID_SIZE - 1)) xTo++; break; // right
}
} while ((xFrom == xTo) && (yFrom == yTo));
}
void CreateXsegments(void)
{
int x, y, i=0, j;
segment* xSegments;
// xSegments[0] = {(0,3),(1,3)} {(1,3),(2,3)} {(2,3),(3,3)}
// xSegments[1] = {(0,2),(1,2)} {(1,2),(2,2)} {(2,2),(3,2)}
// xSegments[2] = {(0,1),(1,1)} {(1,1),(2,1)} {(2,1),(3,1)}
// xSegments[3] = {(0,0),(1,0)} {(1,0),(2,0)} {(2,0),(3,0)}
for (y = (GRID_SIZE - 1); y >= 0; y--)
{
xSegments = (segment*)malloc((GRID_SIZE - 1) * sizeof(segment));
if (!xSegments)
{
exit(-1);
}
xPaths[i++] = xSegments;
j = 0;
for (x = 0; x < (GRID_SIZE - 1); x++)
{
xSegments[j++] = { {x,y,x + 1,y},false };
}
}
}
void CreateYsegments(void)
{
int x, y, i = 0, j;
segment* ySegments;
// ySegments[0] = {(0,3),(0,2)} {(0,2),(0,1)} {(0,1),(0,0)}
// ySegments[1] = {(1,3),(1,2)} {(1,2),(1,1)} {(1,1),(1,0)}
// ySegments[2] = {(2,3),(2,2)} {(2,2),(2,1)} {(2,1),(2,0)}
// ySegments[3] = {(3,3),(3,2)} {(3,2),(3,1)} {(3,1),(3,0)}
for (x = 0; x < GRID_SIZE; x++)
{
ySegments = (segment*)malloc((GRID_SIZE - 1) * sizeof(segment));
if (!ySegments)
{
exit(-1);
}
yPaths[i++] = ySegments;
j = 0;
for (y = (GRID_SIZE - 1); y > 0; y--)
{
ySegments[j++] = {{x,y,x,y - 1},false};
}
}
}
int main(int argc, char *argv[])
{
int WalksDone;
int xWalks, yWalks;
int TotalSteps, AvgSteps;
int ctr,ctrmax=102,avg,avgmax=100;
simple_rand.seed((unsigned int)time(0));
// Compute Grids 10x10, 20x20, ... ,100x100
for (ctr = 11; ctr < ctrmax; ctr += 10)
{
AvgSteps = 0;
for (avg = 0; avg < avgmax; avg++)
{
GRID_SIZE = ctr;
WalksDone = (GRID_SIZE * (GRID_SIZE - 1));
TotalSteps = 0;
xWalks = yWalks = 0;
xFrom = yFrom = xTo = yTo = 0;
CreateXsegments();
CreateYsegments();
do
{
TotalSteps++;
GenerateRandomWalk();
if (xWalks != WalksDone)
{
PathsCheck(xPaths);
xWalks = PathsStats(xPaths);
}
if (yWalks != WalksDone)
{
PathsCheck(yPaths);
yWalks = PathsStats(yPaths);
}
} while ((xWalks != WalksDone) || (yWalks != WalksDone));
printf("%ux%u Grid, Total Steps: %d\n", GRID_SIZE - 1, GRID_SIZE - 1, TotalSteps);
AvgSteps += TotalSteps;
// Release memory....
for (int i = 0; i < GRID_SIZE; i++)
{
free(xPaths[i]); xPaths[i] = NULL;
free(yPaths[i]); yPaths[i] = NULL;
}
}
printf("%ux%u Grid, Average Steps: %d\n", GRID_SIZE - 1, GRID_SIZE - 1, AvgSteps/avgmax);
}
return 0;
}
Best Answer
The number of steps needed for random walk to visit all vertices of an $n$ by $n$ square is asymptotic to $4n^2 \log^2 n/\pi$, see [1]. The upper bound was known earlier, and the result also applies to crossing all edges (with or without periodic boundary conditions.)
[1] Dembo, Amir, Yuval Peres, Jay Rosen, and Ofer Zeitouni. "Cover times for Brownian motion and random walks in two dimensions." Annals of mathematics (2004): 433-464.