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 <[EMAIL PROTECTED]> 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 >
============================================================ 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
