Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: X/O Grid
Posted:
Dec 21, 2012 3:18 AM


On Tue, 18 Dec 2012 22:32:43 0800, William Elliot wrote:
> Consider an n by m grid of x's and o's. > > An xpath from the bottom squares of the grid to the top squares of > the grid constitutes a sequence of horizontally or vertically adjacent > xsquares from some bottom xsquare to some top xsquare. Similar > with opaths. > > An exit is a top square that is connected to a bottom square by > either an xpath or an opath. For example, in the 8 by 3, x/o grid > > x x o o x x o o x > x o o x o x x x x > o o x x x o x o x > > has two oexits and three xexits for a total of five exits. > > In an n by m, x/o grid, what is the expected number of exits?
I haven't looked for a specific formula, but wrote two programs, as at <http://pat7.com/jw/pathcounts/countPath.py> and <http://pat7.com/jw/pathcounts/expCount.py>, that compute expected values for xexits for ranges of m, n values. (It is straightforward to adapt the latter to produce expected values of exits, ie, the sum of expected xexits + oexits also.) The first program is fairly slow because it generates all possible mbyn grids for each (m,n) pair, and counts the number of paths. With a few minutes of work it generates data as below (see <http://pat7.com/jw/pathcounts/sampleresults> for more lines).
m,n: 3 2 Total: 54 Avg.: 0.84375 m,n: 3 3 Total: 1194 Avg.: 2.33203125 m,n: 3 4 Total: 18306 Avg.: 4.46923828125 m,n: 3 5 Total: 231634 Avg.: 7.06890869141 m,n: 3 6 Total: 2614194 Avg.: 9.97235870361
For example, the last line indicates that over the 2^18 possible 0,1 grids with 3 rows and 6 columns, there are 2614194 x paths, so an "average" 3x6 grid has ~ 9.97 x paths (and presumably the same number of o paths, since every grid has exactly one complement).
The other program, expCount.py, computes data like the following via a few milliseconds of work.
p= 0.5 m n= 2 3 4 5 6 7 8 3 0.8438 2.3320 4.4692 7.0689 9.9724 13.0664 16.2766 4 0.6328 2.1489 4.6596 7.9910 11.9236 16.2681 20.8833 5 0.4746 1.9803 4.8587 9.0363 14.2647 20.2720 26.8264 6 0.3560 1.8249 5.0666 10.2193 17.0690 25.2702 34.4792 7 0.2670 1.6817 5.2834 11.5575 20.4259 31.5051 44.3256 8 0.2002 1.5498 5.5094 13.0711 24.4436 39.2805 56.9899
Note that the numbers from the two programs match wherever (m,n) overlaps. expCount.py works by computing the expected number of xpaths into each cell, one row at a time, under the hypothesis that x's occur with probability p, for given p in (0,1). The sampleresults file linked earlier includes data from function calls runset(13, 9, 0.5), runset(16, 6, 0.46633), and runset(16, 9, 0.44475), where runset(mhi, nhi, p) generates a table like the one shown above (which was from runset(9, 9, 0.5)).
Let E(m,n,p) denote the (m,n)th table entry for a given probability. When p=0.46633, E(m,5,p) is between about 4.870 and 4.872 for n= 4 to 15, and when p=0.44475, E(m,7,p) is between about 6.685 and 6.695 for n= 4 to 15.
Evidently, for any given value of p, there exists an N such that as m goes to infinity, k<N implies lim(E(m,k,p)) = 0 while k>N implies lim(E(m,k,p)) = infinity. For any given value of p, suppose N_p is such an N. I imagine there does not exist any p such that lim{m>oo}(E(m, N_p, p)) is nonzero and finite. While it is also easy to imagine that there *could* exist some values of p with lim{m>oo}(E(m, N_p, p)) nonzero and finite, I think it's more likely that there's a reasonably trivial argument to show no such p exist.
Note that the paths considered by the two programs only continue (from a given square) by going left, right, or upward to a notyettraversed square. That is, they count the following grid as having no paths of either kind:
0 0 0 0 1 1 1 1 0 1 1 0 1 1 1 1 0 0 0 0
 jiw



