Two ants are on the opposite corners of a grid of size $8 × 8$ if they move then what is the probability that they will meet after each travelled eight steps (Assuming that they move rightward or upward).

Now for each step, both ants have 2 option, move upward or rightward. So for 8 steps, total cases=$2^8 \cdot 2^8=2^{16}$ but how to calculate favorable cases?

Given answer is $\frac{C(16,8)}{2^{16}}$

enter image description here

I hope the image provides some clarification

Can we say that overall $8$ rightward and $8$ upward steps must be taken in all by two ants?

  • 1
    $\begingroup$ Formatting note: if your exponent requires more than one character you need to isolate it with curly brackets as in "2^{16}". This is true even if it renders as a single character, as in "2^{\pi}" $\endgroup$ – lulu Nov 22 '17 at 16:40
  • $\begingroup$ \binom{16}{8} renders $$\binom{16}{8}$$ as does {16\choose8} $\endgroup$ – gen-z ready to perish Nov 22 '17 at 16:42
  • $\begingroup$ Also, the rules are not clear to me. What do you mean by "opposite corners"? If, say, one ant starts in the upper right most corner, is it blocked from moving at all? $\endgroup$ – lulu Nov 22 '17 at 16:42
  • $\begingroup$ "Can we say that overall 8 rightward and 8 upward steps must be taken in all by two ants?" No. What if ant one makes 2 rightward moves and 6 upward moves, and ant two make 8 upward moves? $\endgroup$ – XRBtoTheMOON Nov 22 '17 at 16:44
  • 1
    $\begingroup$ Ok. So say that ant $i$ moves $(v_i,h_i)$ . Here $v$ stands for vertical, $h$ stands for horizontal. Then the upper ant winds up at height $8-v_1$ and the lower winds up at height $v_2$. For these to be equal we must have $v_1+v_2=8$ and similarly for $h$. $\endgroup$ – lulu Nov 22 '17 at 17:16
  1. Focus on the first ant (bottom left). Let the ant's position be (0, 0). Observe that if we know the final x-coordinate of the first ant as $X_1$, we know that the y-coordinate is $8 - X_1$. $X_1$ is a binomial random variable with parameters $8$ and $\frac{1}{2}$. $\mathbb{P}(X_1 = i) = \binom{8}{i}\frac{1}{2^8}$.
  2. Similarly the second ant. Let the x-coordinate be $X_2$. $X_2$ is $8 - X_2'$, where $X_2'$ is a binomial random variable with the same parameters as above. Due to symmetry of the binomial distribution, we have the same distribution for $X_2$ as for $X_2'$. This in turn means that $X_1$ and $X_2$ have the same distribution.
  3. Thus, for the ants to meet, we need $X_2 = X_1$, where both are binomial random variables with parameters $8$ and $\frac{1}{2}$. We obtain the final probability as $$\sum_{i=0}^8 \mathbb{P}[X_1 = i] \cdot \mathbb{P}[X_2 = i] = \sum_{i=0}^8 \left[\binom{8}{i}\frac{1}{2^8}\right] \cdot \left[\binom{8}{i}\frac{1}{2^8}\right] = \frac{1}{2^{16}}\sum_{i=0}^8 \binom{8}{i}^2 = \frac{\binom{16}{8}}{2^{16}}.$$ I used this result for the last equality.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.