```Date: Dec 21, 2012 3:18 AM
Author: James Waldby
Subject: Re: X/O Grid

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 x-path from the bottom squares of the grid to the top squares of > the grid constitutes a sequence of horizontally or vertically adjacent > x-squares from some bottom x-square to some top x-square.  Similar > with o-paths.> > An exit is a top square that is connected to a bottom square by > either an x-path or an o-path.  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 o-exits and three x-exits 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 x-exits for ranges of m, n values.  (It isstraightforward to adapt the latter to produce expected values ofexits, ie, the sum of expected x-exits + o-exits also.) The firstprogram is fairly slow because it generates all possible m-by-ngrids for each (m,n) pair, and counts the number of paths.  Witha few minutes of work it generates data as below (see <http://pat7.com/jw/pathcounts/sample-results> for more lines).m,n: 3 2 	Total: 54 	Avg.: 0.84375m,n: 3 3 	Total: 1194 	Avg.: 2.33203125m,n: 3 4 	Total: 18306 	Avg.: 4.46923828125m,n: 3 5 	Total: 231634 	Avg.: 7.06890869141m,n: 3 6 	Total: 2614194 	Avg.: 9.97235870361For example, the last line indicates that over the 2^18 possible0,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 thesame number of o paths, since every grid has exactly one complement).The other program, expCount.py, computes data like the followingvia 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.9899Note that the numbers from the two programs match wherever (m,n)overlaps.  expCount.py works by computing the expected number ofx-paths into each cell, one row at a time, under the hypothesisthat x's occur with probability p, for given p in (0,1).  The sample-results file linked earlier includes data from functioncalls runset(13, 9, 0.5), runset(16, 6, 0.46633), andrunset(16, 9, 0.44475), where runset(mhi, nhi, p) generates atable 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.695for 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 implieslim(E(m,k,p)) = infinity.  For any given value of p, suppose N_p issuch an N.  I imagine there does not exist any p such that lim{m->oo}(E(m, N_p, p)) is non-zero and finite.  While it is also easy to imagine that there *could* exist some values of p withlim{m->oo}(E(m, N_p, p)) non-zero and finite, I think it's more likelythat 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 not-yet-traversed square.  That is, they count the following gridas having no paths of either kind:0 0 0 0 11 1 1 0 11 0 1 1 11 0 0 0 0-- jiw
```