Ants on a checkerboard

[bonanova]

Two ants named Al and Bert sit at diagonal corners of a checkerboard and decide to change places. Al, at the lower left,  walks randomly upward or to the right, and Bert, at the upper right, walks randomly downward or to the left. They follow the boundaries of the checkerboard squares. That is, except when following the extreme boundary of the checkerboard, their left and right feet always touch squares of opposite color.

What is the probability of their meeting (1) if they walk at the same speed, or (2) if Al walks 3 times as fast as Bert?

[plasmid]

Here's what I came up with

Spoiler

As Captain Ed said, if Al walks three times as fast as Bert, they’ll meet at the diagonal that goes from halfway through one side of the board and halfway through a neighboring side. To calculate the probability that the ant will land at any one of those vertices along that diagonal, one might think it suffices to calculate the number of paths that could lead to each of those vertices.

In general, if an ant is walking to a square at (x, y) where the ant can either take a step going +1 along the x-axis or +1 along the y-axis, then the number of possible paths it could take to reach square (x, y) is the number of paths it could take to reach square (x-1, y) plus the number of paths it could take to reach square (x, y-1). That’s shown in the following figure. (Unfortunately, I mixed up Al and Bert and I have the faster walking ant starting in the upper right corner, but nevertheless this shows the number of different paths that the ant could take to reach that diagonal.)

But notice in the first paragraph, I said “one might think it suffices to calculate the number of paths that could lead to each of those vertices.” It happens to be the case that I am not one. If we’re dealing with an ant that walks along the edges of each square, then when it reaches the halfway point of the board, it no longer has a 50/50 chance of going in any direction – if the ant is on an edge of the entire checkerboard, then there’s only one direction it can go that would not have it scurrying off the edge of the board. Since it doesn’t have two choices, the probability that it would walk in a direction that would take it off the board should instead be redirected to move it along the only available path. In that case, the probability of ending up in each vertex is proportional to the numbers in the following figure.

Odds that the upper right ant ends up in each of the five possible intersections are
794/4096, 792/4096, 924/4096, 792/4096, 794/4096

Odds that the lower left ant ends up in each of the five possible intersections are the same as the odds that the upper right ant will end up at the corresponding spot on the diagonal from the middle of the top edge to the middle of the right edge.
1/16, 4/16, 6/16, 4/16, 1/16

So the odds that they meet are
(794 x 1 + 792 x 4 + 924 x 6 + 792 x 4 + 794 x 1) / (4096 x 16) = 13468 / 65536 ~= 0.2055

Edit: an aside

Spoiler

It can't be the case that the probability of the ants meeting is, in general, not dependent on their speed. Suppose the ant in the upper right moved 15 squares by the time the lower left ant moved 1. In that case, the ants would meet on one of two vertices in the bottom left square, either its upper left or its lower right vertex, and the odds of meeting would of course be 50/50.

Edit2: even further aside

Spoiler

But if you allow an ant to walk off the edge of the board, then the probabilities of meeting might become independent of speed. I haven't mathed that out.

 

Edited January 29, 2018 by plasmid

[CaptainEd]

Cute puzzle, Bonanova, as always.

(1) 

after 8 steps, each of them is in one of the 9 vertices going SE from the upper left corner. The probabilities are C(8,1)/256, C(8,2)/256, etc. So the probability of Al and Bert arriving at the same corner is the sum of the squares of those probabilities

(2) partially

after 12 Al steps, (and therefore 4 Bert steps), they are each on the shorter NW-SE diagonal beginning in the middle of the top of the board.. For Bert, the probabilities are C(4,1)/16, C(4,2)/16, etc. I have not figured out the probabilities for Al, however

[plasmid]

I got a different answer for question #2...

Spoiler

... approximately 0.2055

 

[bonanova]

22 hours ago, CaptainEd said:

Cute puzzle, Bonanova, as always.

(1)

  Hide contents

 

after 8 steps, each of them is in one of the 9 vertices going SE from the upper left corner. The probabilities are C(8,1)/256, C(8,2)/256, etc. So the probability of Al and Bert arriving at the same corner is the sum of the squares of those probabilities

 

(2) partially

 

  Hide contents

after 12 Al steps, (and therefore 4 Bert steps), they are each on the shorter NW-SE diagonal beginning in the middle of the top of the board.. For Bert, the probabilities are C(4,1)/16, C(4,2)/16, etc. I have not figured out the probabilities for Al, however

 

 

 

Right so far, and the one not yet calculated is interesting.

[CaptainEd]

 

 

 

My previous wasn’t exactly right, but now I think I’ve got it

A) the 9 vertices from NW corner to SE corner get probabilities

C(8,0)*C(8,0) + C(8,1)C(8,1) + ... + C(8,8)*C(8,8), divided by 2^16, because Al and Bert each take 8 steps

B) the 5 vertices from top center in Se direction get probabilities

C(12,4)*C(4,0) + C(12,5)*C(4,1) + C(12,6)*C(4,2) + C(12,7)*C(4,3) + C(12,8)*C(4,4), all divided by 2^16, because Al takes 12 steps and Bert takes 4. 

Edited January 29, 2018 by CaptainEd
Elephant font, please remove

[CaptainEd]

Oh, when you calculate them out...

both probabilities are .196380615!

Thanks, Bonanova!

[bonanova]

@CaptainEd I agree with your reasoning but my numbers different enough for me to recheck them.

@plasmid The fact you're that close to the Captain, I suspect my numbers are the incorrect ones.

What I have convinced myself of, though, is that

Spoiler

The two probabilities are the same

 

[CaptainEd]

For @plasmid, your argument sways me for part b, but I’m certain of part a.

A) for the 8 step case, there are no places where the ant can’t go in a particular direction, so it seems like the 9 endpoints exhaust all the possibilities of 2^8. So I believe the C(8,0),...,C(8,8) counts are accurate, as well as the denominator. So, unless my iPhone Excel formula fell victim to roundoff rot, my number feels right.

B) for the 12 step case, though, your argument feels reasonable, that we don’t want the denominator to count trajectories that would take Al off the board.

I still like the calculation of the paths actually taken to the five vertices. For example, the vertex that requires 8 up and 4 to the right should receive all combinations of 8 ups and 4 rights, which feels like C(12,4). 

We may have to ask the philosophical question, “what does it mean for a choice to be uniformly randomly distributed if the ant gets to the end of the world?”

I have to look more deeply, if I can.

[CaptainEd]

I think for part (b), I’ve got the right answer for the wrong question.

If Al starts at the SW corner, and makes 12 steps, one per vertex, some of his paths will go outside the checkerboards, to the north and to the east. The only vertices that Bert can reach are the five beginning at top center and proceeding SW to the right side of the board, as we have said before.

The number of paths is 2^12, so the probabilities if meeting Bert is as I said earlier.

 

The problem is, as plasmid points out, this doesn’t meet the OP, which seems to require the ant to stay on the board (or at least keep one foot track on the board).

 

One approach, as plasmid says, is to divert all the wayward paths to remain on the top edge or right edge. That would preserve the denominator, and add to the numerator.

 

Another approach is to reduce the denominator by the paths that would have gone out of bounds. That would reduce the denominator to the total of the paths that end on the same 5 vertices. That ought to raise the total probability, even higher than plasmid’s calculation. And it makes it hard to justify the notion of choosing steps at random.

[aiemdao]

Spoiler

 

(1)  Each ant have 14C7 = 3432 ways to go

because their speed is equal sao thay will met when they go 7 step 

=> the probability = ( (7C0)^4 + (7C1)^4 + ... (7C7)^4)/(3432^2) = 0.288

 

 

Edited February 17, 2018 by bonanova
Added spoiler

[bonanova]

Regarding the 5 probabilities after 12 ant moves:

Spoiler

Enumerating paths and treating them as equals gives { C(12,8) C(12,7) C(12,6) C(12,5) C(12,4) } / (3498) multiplied by { 1 4 6 4 1 } / 16 and summing for a result of .22995. But Al (the faster ant)'s paths involve from 8 to 12 choices, so they are not equally likely. Probabilities derived by dividing each path by the sum of all paths (3498 in this case) will be incorrect. What is the right approach?

• @plasmid augments paths that touch an intermediate border point, where a choice is eliminated, by multiplying by 2 at each point. The effect is to create virtual paths that increase the count to each end point by 299, making 4096 = 2¹² total paths and leads to the correct probability of .20551.
  
  I have three other approaches. The first is the one I thought would be found here. Another is quick and dirty. The last one occurred to me as I'm writing this.
   
• This one seems evidently correct but is the most involved of the three.
  
  Call the Final points { F₁ F₂ F₃ F₄ F₅ } with probabilities of { f₁  f₂  f₃  f₄  f₅ }.
  
  Start with a result from the first problem, the probabilities { d₁ d₂ d₃ d₄ d₅ d₆ d₇ d₈ d₉ } of reaching the 9 diagonal points. Then (by inspection) determine the probabilities of reaching each F_i from the one-to-five possible starting diagonal points Dj. Call those p(Dj, Fi). There are 25, but really only 15 due to symmetry, and some are trivial. Others take just a little thought. Clearly p(D1 ,F1)=1. Then, since p(D2, F2) (4 E moves) = 1/16, we have p(D2, F1) = 15/16, and so on. Then we have
  
  f_i = sum(j) { dj x p(Dj, Fi) }
   
• This one involves the least work.
  
  Paths to { F2 F3 F4 } don't hit an edge. So { f2  f3  f4 } = { C(12,7) C(12,6) C(12,5) } / 2¹²
  Then  f₁ = f₅ = 1/2 ( 1 - sum { f₂  f₃  f₄ } )
       
• This one recognizes an equivalent calculation.
  
  What is the probability of flipping 8 heads before flipping 5 tails? I don't know whether this is an easy question or not, but the answer gives f₁ and f₅.

•