Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: X/O Grid
Replies: 2   Last Post: Dec 23, 2012 3:16 AM

 Messages: [ Previous | Next ]
 James Waldby Posts: 545 Registered: 1/27/11
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 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 is
straightforward to adapt the latter to produce expected values of
exits, ie, the sum of expected x-exits + o-exits also.) The first
program is fairly slow because it generates all possible m-by-n
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/sample-results> 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
x-paths 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
sample-results 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 non-zero 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)) non-zero 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
not-yet-traversed 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

Date Subject Author
12/21/12 James Waldby
12/23/12 William Elliot