Two ants walk on a line in a random fashion. they begin 10cm apart. at each time step, each ant has a probability of 1/2 to move 1cm to the left, and probability 1/2 to move 1cm to the right. what is the probability that after 7 time steps, the ants have met one another (i. e., passed through the same point)?

121/16384 exactly, or approximately 0.739% Each time step, there are 4 possibilities that will happen. They are a1 a2 -1 -1 = Ants move to left, distance remains the same. -1 1 = Ants move away from each other, distance = distance + 2 1 -1 = Ants move to each other, distance = distance - 2 1 1 = Ants move to right, distance remains the same. For the rest of the discussion, I'll call the possible moves advance, retreat, and idle (and there's 2 ways idle can happen). If you consider the possible moves, the ants can reach each other only at time steps 5, 6, or 7. Let's consider each of those values separately. 5 time steps. This can only happen if all 5 moves are advances. And after they reach each other we don't care what happens for the remaining 2 steps so there is 1 * 4 * 4 = 16 possible sequences where the ant reach each other on the 5th step. 6 time steps. The only way this can happen is with 5 advances and 1 idle, with the idle happening during one of the 1st 5 steps. So there's 5 ways for that to happen. And since there's 2 different actions that are an idle, we multiply that 5 by 2 to get 10. And finally, we don't care what happens with the 7th step, so we multiply once again by 4, getting 40. 7 time steps. This can happen 2 ways. If the 1st 6 steps are 4 advances and 2 idles with the idles happening during any step, then we have 6!/(2!4!) = 15 different arrangements. Since we have 2 different types of idles, we need to multiply by 2 for each idle, so we have 15 * 2 * 2 = 60 possible ways to do this. It can also happen if during the 1st 6 steps we have 5 advances and 1 retreat with the retreat happening during one of the 1st 5 moves. So there's 5 ways to get the ants to meet if the sequence has a retreat. So with a sequence of 7 time steps, there are 16 + 40 + 60 + 5 = 121 possible sequences that have the ants at the same point at the same time. Now since there are 4 possibilities for each step, there are 4^7 = 16384 possible sequences that can be done. So the probability of the 2 ants meeting each other is 121/16384 = 0.007385254 = 0.7385254%