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
