# 2 aliens walk on a line meeting probability [closed]

2 aliens walk on a line randomly. At each timestep they walk independently either left or right (1 meter) with equal probability. They start 10 meters apart. What's the probability that after 7 time steps they have met (passed through the same point)?

Hello,

I'm trying to solve this puzzle but I'm struggling. I know that there are $4^7$ states in the tree. If we imagine them being on a number line. Alien $A$ starting at $0$ and Alien $B$ starting at $10$. I know that they can only meet at points $3$-$7$.

I know that the probability of Alien $A$ getting to $3$ after $3$ time steps is $\frac{1}{8}$.

I don't really know where to go from here. Thank you for your suggestions.

• they walk sideways? Or ahead and they go left/right after each step ? – Marius Mar 17 '17 at 20:36
• Sideways. Like this ______<-A->_________________<-B->______ – Rupert Gatwick Mar 17 '17 at 20:49
• this does not look much as a puzzle. Maybe you have more luck with it here: math.stackexchange.com – Marius Mar 17 '17 at 21:37

Let's start by tracing the probabilities with a single alien:

At the 1st step, he might be at positions $+1$ or $-1$ with $1/2$ probability each.
At the 2nd step, $-2$ ($1/4$), $0$ ($2/4$) or $+2$ ($1/4$).
At the 3rd step, $-3$ ($1/8$), $-1$ ($3/8$), $+1$ ($3/8$), $+3$ ($1/8$).
At the 4th step, $-4$ ($1/16$), $-2$ ($4/16$), $0$ ($6/16$), $+2$ ($4/16$), $+4$ ($1/16$).
At the 5th step, $-5$ ($1/32$), $-3$ ($5/32$), $-1$ ($10/32$), $+1$ ($10/32$), $+3$ ($5/32$), $+5$ ($1/32$).
At the 6th step, $-6$ ($1/64$), $-4$ ($6/64$), $-2$ ($15/64$), $0$ ($20/64$), $+2$ ($15/64$), $+4$ ($6/64$), $+6$ ($1/64$).
At the 7th step, $-7$ ($1/128$), $-5$ ($7/128$), $-3$ ($21/128$), $-1$ ($35/128$), $+1$ ($35/128$), $+3$ ($21/128$), $+5$ ($7/128$), $+7$ ($1/128$).

This can easily be seen when you build:

a triangle with a number 1 in the top and filling each row below it with the sum of the two numbers above.

Like this:

Each line has a position from $-7$ to $+7$ (the horizontal positions) and the probability of the alien being in that position is expressed as $\frac{x}{2^y}$, where $x$ is the number in the table for the step $y$. Blanks should be considered as $x = 0$.

Now, let's see where the two aliens might meet:

• [a]

At the 5th step with $+5$ and $-5$, coming from $+4$ and $-4$ with a probability of $\frac{1}{32} \times \frac{1}{32} = \frac{1}{1024}$.

Note that:

At the 6th step with $+6$ and $-6$, coming from $+5$ and $-5$ they would already had met at the 5th step;

• [b]

At the 6th step with $+6$ and $-4$ coming from $+5$ and $-3$. This gives a probability of $\frac{1}{64} \times \frac{5}{64} = \frac{5}{4096}$;

• [c]

The opposite of [b];

• [d]

At the 7th step, having the 5th as $+5$ and $-3$, 6th as $+6$ and $-2$ and 7th as $+7$ and $-3$;

• [e]

At the 7th step, having the 5th as $+5$ and $-3$, 6th as $+4$ and $-4$ and 7th as $+5$ and $-5$;

• [f]

At the 7th step, having the 5th as $+3$ and $-3$, 6th as $+4$ and $-4$ and 7th as $+5$ and $-5$;

• [g]

opposite of [d];

• [h]

opposite of [e].

For cases d, e, g and h, the probabilities of reaching the 5th step are calculated as:

$\frac{1}{32} \times \frac{5}{32} = \frac{5}{1024}$ for each.

For case f, the proability of reaching the 5th step is:

$\frac{5}{32} \times \frac{5}{32} = \frac{25}{1024}$

Each one of the cases d to h depend on exacts two steps performed by each of the aliens, so...

... we multiply each of those probabilities by $\frac{1}{16}$, because we have four steps to do, each one having $\frac{1}{2}$ of probability of happening.

This gives the probabilities as:

$P = p_a + p_b + p_c + p_d \times \frac{1}{16} + p_e \times \frac{1}{16} + p_f \times \frac{1}{16} + p_g \times \frac{1}{16} + p_h \times \frac{1}{16}$

However...

Given that $p_b = p_c$ and that $p_d = p_e = p_g = p_h$, then $p_b + p_c = 2 p_b$ and $p_d + p_e + p_g + p_h = 4 p_d$ and we can simplify the formula to:

$P = p_a + 2 p_b + 4 p_d \times \frac{1}{16} + p_f$

Now, we can solve this as...

\begin{align} P & = p_a + 2 p_b + 4 p_d \times \frac{1}{16} + p_f \\ & = \frac{1}{1024} + 2 \times \frac{5}{4096} + 4 \times \frac{5}{1024} \times \frac{1}{16} + \frac{25}{1024} \times \frac{1}{16} \\ & = \frac{16}{16384} + \frac{40}{16384} + \frac{20}{16384} + \frac{25}{16384} \\ & = ... \end{align}

And the final result is...

$$P = \frac{101}{16384}$$

And a final curiosity:

The aliens are always separated by an even number of meters. This also ensures that if they meet, they will collide and not pass one through the other swapping their positions.

• Oh, you typed all that math on phone? :-O Cool! – Techidiot Mar 18 '17 at 2:57
• @Techidiot Yes. And posting answers in SE using cellphones is an exercise of torture, specially when they feature math. Now that I am at my notebook, I edited the answer severely to put it in a more adequate format. – Victor Stafusa Mar 18 '17 at 11:08