Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Re: X/O Grid
Posted:
Dec 23, 2012 1:17 PM
|
|
On Sun, 23 Dec 2012 00:16:38 -0800, William Elliot wrote:
> On Fri, 21 Dec 2012, James Waldby wrote:
>> On Tue, 18 Dec 2012 22:32:43 -0800, William Elliot wrote:
>>
>> > Consider an n by m grid of x's and o's.
>
> n is width, m is height.
>
>> > 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?
>> ...
>> <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
>>
> Yes, as the width n increases, the expected number of exits will incease.
>> ...
>> 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
> I don't see why as the height m increases, that the expected number of
> exits would increase. In fact, I'd expect just the opposite.
Yes. What the programs are counting are the number of expected paths
rather than the number of expected exits. I imagine I can revise the
programs to count exits rather than paths.
Percolation theory, mentioned by Michael Press, may provide some answers
for exits or paths. <http://en.wikipedia.org/wiki/Percolation_theory>
>> 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
>
> Oh oh. That grid has one exit. Note that the grid
>
> 1 1 1 0 1
> 1 0 1 1 1
> 1 0 0 0 0
>
> has four exits.
[rather than only three]
Allowing down-moves would complicate the programs quite a bit, so I left
them out. Also, your original post didn't have examples or text about
down-moves (vs left-, right-, or up-moves) from a square so it wasn't
clear if they were to be allowed. I'll have a look.
--
jiw
|
|
|
|
