Friam

GridPaths, Knuth's nifty book & a Question

Classic

List

Threaded

10 messages Options

Owen Densmore

GridPaths, Knuth's nifty book & a Question

Administrator

Lately I've been puzzling on the intersection between computing/
algorithms and mathematics. This lead me to look at:
Donald Knuth's Selected Papers on Computer Science
http://tinyurl.com/5zraag

In it he has several great essays, one of which is:
Mathematics and Computer Science: Coping with Finiteness
In it he has a section
Counting the Paths on a Grid.
Here are some scanned images of figures he uses:
http://backspaces.net/temp/GridPath1.png
http://backspaces.net/temp/GridPath2.png
And better yet, here's a netlogo model:
http://backspaces.net/temp/GridPath/

2 Questions/Puzzles I'd like to share with you:
1 - The probability for each path is calculated by looking at the
possible choices at each point in the path. If you see a "3" at a
node, for example, the probability assigned to the next move is 1/3.
The total probability for a given path is the product of the
individual ones.
Question: how can I show that this forms a true probability
space? .. i.e. the sum of the probabilities for all possible paths is
1.0.
2 - (Mainly for geeks) My solution for the model is to use a
floodfill after each move to find the possible next moves. For such a
small space (11x11), this is not computationally intensive, but seems
a bit heavy handed.
Question: is there an algorithm that uses a simpler approach?

-- Owen

============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org

Roger Critchlow-2

Re: GridPaths, Knuth's nifty book & a Question

On Mon, Aug 18, 2008 at 11:19 AM, Owen Densmore <[hidden email]> wrote:

1 - The probability for each path is calculated by looking at the
possible choices at each point in the path. If you see a "3" at a
node, for example, the probability assigned to the next move is 1/3.
The total probability for a given path is the product of the
individual ones.
Question: how can I show that this forms a true probability
space? .. i.e. the sum of the probabilities for all possible paths is
1.0.

Given the paths of length N, i, and their probabilities, p(i), we form the paths of length N+1 by one of the following steps:

1) if there is only one way to extend path i, then the probability of that extension is p(i) * 1.

2) if there are two ways to extend path i, then the probabilities of those two extensions are each p(i)/2.

3) if there are three ways to extend path i, then the probabilities of those three extensions are each p(i)/3.

There cannot be four or more ways to extend path i.

If the sum(i, p(i)) == 1, then the sum(i, p(i)*1 or 2*p(i)/2 or 3*p(i)/3) == 1.

Starting from the lower left corner, we have 2 choices, each assigned probability 1/2. 2 * 1/2 == 1.

If it's true for the paths of length N, then it's true for the paths of length N+1; and it's true for the paths of length 1.

-- rec --

============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org

Owen Densmore

Re: GridPaths, Knuth's nifty book & a Question

Administrator

Very nice indeed, thanks!

-- Owen

On Aug 18, 2008, at 2:19 PM, Roger Critchlow wrote:

> On Mon, Aug 18, 2008 at 11:19 AM, Owen Densmore
> <[hidden email]> wrote:
>
>> 1 - The probability for each path is calculated by looking at the
>> possible choices at each point in the path. If you see a "3" at a
>> node, for example, the probability assigned to the next move is 1/3.
>> The total probability for a given path is the product of the
>> individual ones.
>> Question: how can I show that this forms a true probability
>> space? .. i.e. the sum of the probabilities for all possible paths is
>> 1.0.
>>
>
> Given the paths of length N, i, and their probabilities, p(i), we
> form the
> paths of length N+1 by one of the following steps:
>
> 1) if there is only one way to extend path i, then the probability
> of that
> extension is p(i) * 1.
>
> 2) if there are two ways to extend path i, then the probabilities
> of those
> two extensions are each p(i)/2.
>
> 3) if there are three ways to extend path i, then the probabilities
> of
> those three extensions are each p(i)/3.
>
> There cannot be four or more ways to extend path i.
>
> If the sum(i, p(i)) == 1, then the sum(i, p(i)*1 or 2*p(i)/2 or
> 3*p(i)/3) ==
> 1.
>
> Starting from the lower left corner, we have 2 choices, each assigned
> probability 1/2. 2 * 1/2 == 1.
>
> If it's true for the paths of length N, then it's true for the paths
> of
> length N+1; and it's true for the paths of length 1.
>
> -- rec --
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9a-11:30 at cafe at St. John's College
> lectures, archives, unsubscribe, maps at http://www.friam.org

Robert Holmes

Re: GridPaths, Knuth's nifty book & a Question

In reply to this post by Owen Densmore

I'll take a top-down approach instead of Roger's bottom-up approach...

I'm guessing that the problem has a bunch of constraints that you've not specified in your email (can't double-back, path can't crossover) and--most importantly--you have to start at (0,0) and end at (10,10), so stopping somewhere in the middle or getting trapped Tron-like by your own wall is not a solution. So if the probability of getting to (10,10) is 1 then the sum of the probabilities of all the legitimate routes has to sum to 1 (and if it doesn't, you've missed some).

Regards,

Robert

On Mon, Aug 18, 2008 at 11:19 AM, Owen Densmore <[hidden email]> wrote:

Lately I've been puzzling on the intersection between computing/
algorithms and mathematics. This lead me to look at:
Donald Knuth's Selected Papers on Computer Science
http://tinyurl.com/5zraag

In it he has several great essays, one of which is:
Mathematics and Computer Science: Coping with Finiteness
In it he has a section
Counting the Paths on a Grid.
Here are some scanned images of figures he uses:
http://backspaces.net/temp/GridPath1.png
http://backspaces.net/temp/GridPath2.png
And better yet, here's a netlogo model:
http://backspaces.net/temp/GridPath/

2 Questions/Puzzles I'd like to share with you:
1 - The probability for each path is calculated by looking at the
possible choices at each point in the path. If you see a "3" at a
node, for example, the probability assigned to the next move is 1/3.
The total probability for a given path is the product of the
individual ones.
Question: how can I show that this forms a true probability
space? .. i.e. the sum of the probabilities for all possible paths is
1.0.
2 - (Mainly for geeks) My solution for the model is to use a
floodfill after each move to find the possible next moves. For such a
small space (11x11), this is not computationally intensive, but seems
a bit heavy handed.
Question: is there an algorithm that uses a simpler approach?

-- Owen

============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org

Owen Densmore

Re: GridPaths, Knuth's nifty book & a Question

Administrator

On Aug 19, 2008, at 9:47 PM, Robert Holmes wrote:

> I'll take a top-down approach instead of Roger's bottom-up approach...
>
> I'm guessing that the problem has a bunch of constraints that you've
> not
> specified in your email (can't double-back, path can't crossover)
> and--most
> importantly--you have to start at (0,0) and end at (10,10), so
> stopping
> somewhere in the middle or getting trapped Tron-like by your own
> wall is not
> a solution. So if the probability of getting to (10,10) is 1 then
> the sum of
> the probabilities of all the legitimate routes has to sum to 1 (and
> if it
> doesn't, you've missed some).

Unless I misunderstand, you'd like us to fine the N possible paths,
along with their probabilities (using the product of the inverse of
choices for each of their moves within the paths).

That's certainly a Good Thing, but the difficulty is counting all
these paths, and establishing their probabilities. I see no easy way
to do this. I don't even see a way to count all the paths.

Thus roger's argument avoids this issue by considering the incremental
probability of the paths, and showing the increment does not increase
the total probability sum, and shows the initial probability sum is .5
+ .5 = 1 as desired.

Note the other question I asked is whether or not creating these
restricted paths (no crossings, have to make it from lower left to top
right) can be done without resorting to floodfills at each step. I.e.
is there some local knowledge solution that would let a wanderer
create a path without a global floodfill to mark "legal" moves.

-- Owen

============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org

Robert Holmes

Re: GridPaths, Knuth's nifty book & a Question

Not quite: I'm saying that you don't need to calculate the probability of ANY of the paths because the constraints of your problem mean that the probabilities (whatever they are are) of all the paths (however many of them there are) MUST sum to one (because in your problem definition the path finally does have to get to the point (10,10))

Here's another (famous) problem that can be answered using a top-down technique rather than a bottom-up: if you have a regular 8x8 chess board and you remove the bottom left and top right squares, how many ways can you cover the remaining 62-squares completely using non-overlapping 2x1 rectangles?

Robert

On Thu, Aug 21, 2008 at 4:15 PM, Owen Densmore <[hidden email]> wrote:

On Aug 19, 2008, at 9:47 PM, Robert Holmes wrote:
> I'll take a top-down approach instead of Roger's bottom-up approach...
>
> I'm guessing that the problem has a bunch of constraints that you've
> not
> specified in your email (can't double-back, path can't crossover)
> and--most
> importantly--you have to start at (0,0) and end at (10,10), so
> stopping
> somewhere in the middle or getting trapped Tron-like by your own
> wall is not
> a solution. So if the probability of getting to (10,10) is 1 then
> the sum of
> the probabilities of all the legitimate routes has to sum to 1 (and
> if it
> doesn't, you've missed some).

Unless I misunderstand, you'd like us to fine the N possible paths,
along with their probabilities (using the product of the inverse of
choices for each of their moves within the paths).

That's certainly a Good Thing, but the difficulty is counting all
these paths, and establishing their probabilities. I see no easy way
to do this. I don't even see a way to count all the paths.

Thus roger's argument avoids this issue by considering the incremental
probability of the paths, and showing the increment does not increase
the total probability sum, and shows the initial probability sum is .5
+ .5 = 1 as desired.

Note the other question I asked is whether or not creating these
restricted paths (no crossings, have to make it from lower left to top
right) can be done without resorting to floodfills at each step. I.e.
is there some local knowledge solution that would let a wanderer
create a path without a global floodfill to mark "legal" moves.

-- Owen

============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org

Phil Henshaw-2

Re: GridPaths, Knuth's nifty book & a Question

That sounds like you’re saying that having an ability to predict an outcome with certainty, a ‘final cause’ in that sense, means that discovering the path the system will take in getting there is not relevant? I think that reversing that logic is the thing to do, that knowing the end gives you great tools for discovering the path.

It’s not whether a system that uses up resources ever faster will run out, after all. That’s a simple “no-brainer” that you can answer with certainty. The question is, knowing the answer is implied, how can you be the first on the block to identify when it’s happening, the path it’s taking and what the choices along that path might be.

Phil

From: [hidden email] [mailto:[hidden email]] On Behalf Of Robert Holmes
Sent: Thursday, August 21, 2008 8:59 PM
To: The Friday Morning Applied Complexity Coffee Group
Subject: Re: [FRIAM] GridPaths, Knuth's nifty book & a Question

On Thu, Aug 21, 2008 at 4:15 PM, Owen Densmore <[hidden email]> wrote:

On Aug 19, 2008, at 9:47 PM, Robert Holmes wrote:
> I'll take a top-down approach instead of Roger's bottom-up approach...
>
> I'm guessing that the problem has a bunch of constraints that you've
> not
> specified in your email (can't double-back, path can't crossover)
> and--most
> importantly--you have to start at (0,0) and end at (10,10), so
> stopping
> somewhere in the middle or getting trapped Tron-like by your own
> wall is not
> a solution. So if the probability of getting to (10,10) is 1 then
> the sum of
> the probabilities of all the legitimate routes has to sum to 1 (and
> if it
> doesn't, you've missed some).

-- Owen

============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org

Kenneth Lloyd

Re: GridPaths, Knuth's nifty book & a Question

And eventually you will re-invent back propagation through feed forward neural networks - assuming non-recurrence.

The solutions to the "problem" are ensembles of paths.

Ken

From: [hidden email] [mailto:[hidden email]] On Behalf Of Phil Henshaw
Sent: Friday, August 22, 2008 8:19 AM
To: 'The Friday Morning Applied Complexity Coffee Group'
Subject: Re: [FRIAM] GridPaths, Knuth's nifty book & a Question

That sounds like you’re saying that having an ability to predict an outcome with certainty, a ‘final cause’ in that sense, means that discovering the path the system will take in getting there is not relevant? I think that reversing that logic is the thing to do, that knowing the end gives you great tools for discovering the path.

It’s not whether a system that uses up resources ever faster will run out, after all. That’s a simple “no-brainer” that you can answer with certainty. The question is, knowing the answer is implied, how can you be the first on the block to identify when it’s happening, the path it’s taking and what the choices along that path might be.

Phil

From: [hidden email] [mailto:[hidden email]] On Behalf Of Robert Holmes
Sent: Thursday, August 21, 2008 8:59 PM
To: The Friday Morning Applied Complexity Coffee Group
Subject: Re: [FRIAM] GridPaths, Knuth's nifty book & a Question

Not quite: I'm saying that you don't need to calculate the probability of ANY of the paths because the constraints of your problem mean that the probabilities (whatever they are are) of all the paths (however many of them there are) MUST sum to one (because in your problem definition the path finally does have to get to the point (10,10))

Here's another (famous) problem that can be answered using a top-down technique rather than a bottom-up: if you have a regular 8x8 chess board and you remove the bottom left and top right squares, how many ways can you cover the remaining 62-squares completely using non-overlapping 2x1 rectangles?

Robert

On Thu, Aug 21, 2008 at 4:15 PM, Owen Densmore <[hidden email]> wrote:

On Aug 19, 2008, at 9:47 PM, Robert Holmes wrote:

> I'll take a top-down approach instead of Roger's bottom-up approach...
>
> I'm guessing that the problem has a bunch of constraints that you've
> not
> specified in your email (can't double-back, path can't crossover)
> and--most
> importantly--you have to start at (0,0) and end at (10,10), so
> stopping
> somewhere in the middle or getting trapped Tron-like by your own
> wall is not
> a solution. So if the probability of getting to (10,10) is 1 then
> the sum of
> the probabilities of all the legitimate routes has to sum to 1 (and
> if it
> doesn't, you've missed some).

Unless I misunderstand, you'd like us to fine the N possible paths,
along with their probabilities (using the product of the inverse of
choices for each of their moves within the paths).

That's certainly a Good Thing, but the difficulty is counting all
these paths, and establishing their probabilities. I see no easy way
to do this. I don't even see a way to count all the paths.

Thus roger's argument avoids this issue by considering the incremental
probability of the paths, and showing the increment does not increase
the total probability sum, and shows the initial probability sum is .5
+ .5 = 1 as desired.

Note the other question I asked is whether or not creating these
restricted paths (no crossings, have to make it from lower left to top
right) can be done without resorting to floodfills at each step. I.e.
is there some local knowledge solution that would let a wanderer
create a path without a global floodfill to mark "legal" moves.

-- Owen

============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org

Owen Densmore

Re: GridPaths, Knuth's nifty book & a Question

Administrator

In reply to this post by Robert Holmes

On Aug 21, 2008, at 6:59 PM, Robert Holmes wrote:
> ..
> Here's another (famous) problem that can be answered using a top-down
> technique rather than a bottom-up: if you have a regular 8x8 chess
> board and
> you remove the bottom left and top right squares, how many ways can
> you
> cover the remaining 62-squares completely using non-overlapping 2x1
> rectangles?

Wonderful! OK, I cheated, but the solution is, as you say, elegant.
I have to admit that I had to see what the chessboard looked like ..
two black squares on the two corners being eliminated.

-- Owen

============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org

Phil Henshaw-2

Re: GridPaths, Knuth's nifty book & a Question

In reply to this post by Kenneth Lloyd

If you just gaze into the math all you’ll see is math. If you learn to recognize the kind of things in your environment the math suggests could develop and then go look, then you might get to better see what to really do about them.

For example, the ABM idea is that lots of things are individually interacting, right? If you play with that in the computer, those behaviors can enrich your imagination for how interactions among independent agents might work in physical systems. If those insights then help you discover how individual real world agents (systems) are actually interacting with each other, it will then inform you on the gaps in your thinking in designing your computer model, but more importantly, let you see the real consequences of the real world interactions, coming right at you. It lets you directly respond to the consequences approaching you in a more informed way.

Yes, it’s no more, at first, than a ‘seeing eye dog’ kind of assist, some waving stick in the dark that bumps into things with no names. That is not much of an assist, granted. But when our survival is threatened and we’re stumbling around hurriedly, maybe it would keep us from falling in some great big hole.

Phil

From: Ken Lloyd [mailto:[hidden email]]
Sent: Friday, August 22, 2008 10:53 AM
To: [hidden email]; 'The Friday Morning Applied Complexity Coffee Group'
Subject: RE: [FRIAM] GridPaths, Knuth's nifty book & a Question

And eventually you will re-invent back propagation through feed forward neural networks - assuming non-recurrence.

The solutions to the "problem" are ensembles of paths.

Ken

From: [hidden email] [mailto:[hidden email]] On Behalf Of Phil Henshaw
Sent: Friday, August 22, 2008 8:19 AM
To: 'The Friday Morning Applied Complexity Coffee Group'
Subject: Re: [FRIAM] GridPaths, Knuth's nifty book & a Question

That sounds like you’re saying that having an ability to predict an outcome with certainty, a ‘final cause’ in that sense, means that discovering the path the system will take in getting there is not relevant? I think that reversing that logic is the thing to do, that knowing the end gives you great tools for discovering the path.

It’s not whether a system that uses up resources ever faster will run out, after all. That’s a simple “no-brainer” that you can answer with certainty. The question is, knowing the answer is implied, how can you be the first on the block to identify when it’s happening, the path it’s taking and what the choices along that path might be.

Phil

From: [hidden email] [mailto:[hidden email]] On Behalf Of Robert Holmes
Sent: Thursday, August 21, 2008 8:59 PM
To: The Friday Morning Applied Complexity Coffee Group
Subject: Re: [FRIAM] GridPaths, Knuth's nifty book & a Question

Not quite: I'm saying that you don't need to calculate the probability of ANY of the paths because the constraints of your problem mean that the probabilities (whatever they are are) of all the paths (however many of them there are) MUST sum to one (because in your problem definition the path finally does have to get to the point (10,10))

Here's another (famous) problem that can be answered using a top-down technique rather than a bottom-up: if you have a regular 8x8 chess board and you remove the bottom left and top right squares, how many ways can you cover the remaining 62-squares completely using non-overlapping 2x1 rectangles?

Robert

On Thu, Aug 21, 2008 at 4:15 PM, Owen Densmore <[hidden email]> wrote:

On Aug 19, 2008, at 9:47 PM, Robert Holmes wrote:
> I'll take a top-down approach instead of Roger's bottom-up approach...
>
> I'm guessing that the problem has a bunch of constraints that you've
> not
> specified in your email (can't double-back, path can't crossover)
> and--most
> importantly--you have to start at (0,0) and end at (10,10), so
> stopping
> somewhere in the middle or getting trapped Tron-like by your own
> wall is not
> a solution. So if the probability of getting to (10,10) is 1 then
> the sum of
> the probabilities of all the legitimate routes has to sum to 1 (and
> if it
> doesn't, you've missed some).

Unless I misunderstand, you'd like us to fine the N possible paths,
along with their probabilities (using the product of the inverse of
choices for each of their moves within the paths).

That's certainly a Good Thing, but the difficulty is counting all
these paths, and establishing their probabilities. I see no easy way
to do this. I don't even see a way to count all the paths.

Thus roger's argument avoids this issue by considering the incremental
probability of the paths, and showing the increment does not increase
the total probability sum, and shows the initial probability sum is .5
+ .5 = 1 as desired.

Note the other question I asked is whether or not creating these
restricted paths (no crossings, have to make it from lower left to top
right) can be done without resorting to floodfills at each step. I.e.
is there some local knowledge solution that would let a wanderer
create a path without a global floodfill to mark "legal" moves.

-- Owen

============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org