Polite Near-Sighted Drunk Bot on a Minefield

Question

As the title may suggest, this problem is semi-inspired by the Polite Near-Sighted Drunk Bot by @N.P.

Our poor bot is placed on a cartesian grid at the origin, and after each minute, it moves 1 unit in one of four directions (Up, Down, Left, Right).

After n minutes, all of the latent mines on the grid activate, killing any poor bot that might find themselves over them. The mines are located at all integer coordinates satisfying the equation |y|=|x|.

Challenge

You will be provided n, the number of minutes before the mines blast, as an input, and as an output, you must find the probability that the bot is dead.

Input: An natural number representing n.

Output: Let the probability the bot is dead be p/q, where p and q are relatively prime whole numbers (q can't be 0, but p can). Output p.

Rules

• Your algorithm must not run in exponential or higher time. It ideally should run in polynomial time or less.
• Your algorithm must be able to handle inputs of n<20 (can be adjusted if too hard) in a reasonable time.
• This is a code-golf challenge.
• Iterating over all possibilities for a given n will most definitely not be accepted as an answer.

Test Cases

1->0

2->3

4->39

6->135

8->7735

10->28287

Example Calculation for n=6

We have 4 possible moves: U, D, R, and L. The total number of paths that could be taken is 4^6, or 4096. There are 4 possible cases that land along the line y = x: x,y = ±1; x,y = ±2; x,y = ±3; or x = y = 0. We will count the number of ways to end up at (1,1), (2,2), and (3,3), multiply them by 4 to account for the other quadrants, and add this to the number of ways to end up at (0,0).

Case 1: The bot ends at (3, 3). In order for the bot to end up here, it must have had 3 right moves, and 3 up moves. In other words, the total number of ways to get here is the ways to rearrange the letters in the sequence RRRUUU, which is 6 choose 3 = 20.

Case 2: The bot ends at (2,2). In order for the bot to end up here, it could have had 2 up moves, 3 right moves, and 1 left move; or 2 right moves, 3 up moves, and 1 down move. Thus, the total number of ways to get here is sum of the ways to rearrange the letters in the sequences RRRLUU and UUUDRR, both of which are (6 choose 1) * (5 choose 2) = 60, for a total of 120 possibilities.

Case 3: The bot ends at (1,1). In order for the bot to end up here, it could have had: 1 right move, 3 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence RUUUDD is (6 choose 1)*(5 choose 2) = 60.

1 up move, 3 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence URRRLL is (6 choose 1)*(5 choose 2) = 60.

2 right moves, 1 left move, 2 up moves, and 1 down move. In this case, the number of ways to rearrange the letters in the sequence UUDRRL is (6 choose 1)* (5 choose 1)*(4 choose 2) = 180.

Thus, the total number of ways to end up at (1,1) is 300.

Case 4: The bot ends at (0,0). In order for the bot to end up here, it could have had:

3 right moves and 3 left moves. In this case, the number of ways to rearrange the letters in the sequence RRRLLL is (6 choose 3) = 20.

3 up moves and 3 down moves. In this case, the number of ways to rearrange the letters in the sequence UUUDDD is (6 choose 3) = 20.

1 right move, 1 left move, 2 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence RLUUDD is (6 choose 1)* (5 choose 1)*(4 choose 2) = 180.

1 up move, 1 down move, 2 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence RRLLUD is (6 choose 1)* (5 choose 1)*(4 choose 2) = 180.

Thus, the total number of ways to end up at (0,0) is 400.

Adding these cases together, we get that the total number of ways to end up on |y| = |x| is 4(20 + 120 + 300) + 400 = 2160. Thus, our probability is 2160/4096. When this fraction is fully reduced, it is 135/256, so our answer is 135.

Answer 1

Python 2, 65 bytes

def p(n):b=2**n;r=b*b-((~b)**n/b**(n/2)%-b)**2;print~n%2*r/(r&-r)

Try it online!

The probability the bot is dead can be expressed as:

$$ f(n) = 2s-s^2\text{, where } s=\frac{1}{2^n}\binom{n}{n/2}$$

and the binomial is understood to equal \$0\$ when \$n/2\$ isn't whole.

We can reason like this. What's the probability that the bot lands on the \$y=x\$ line? This happens if the total number of up and left moves equals the total number of down and right moves. This is the same probability that, say, you flip a coin \$n\$ times and get as many tails as heads. You must choose \$n/2\$ flips to be heads of \$n\$ flips, which can be done in \$\binom{n}{n/2}\$ ways, of \$2^n\$ possible sequences overall, giving probability

$$s=\frac{1}{2^n}\binom{n}{n/2}$$

The probability of landing the \$y=-x\$ line is also \$s\$. So, the probability of landing on either line is the sum of these or \$2s\$, except we're double-counting the probability of landing of \$x=y=0\$ in both lines, and must subtract it to compensate.

It turns out the probability of landing on \$x=y=0\$ is just \$s^2\$, the product of the probability of landing on each line. We can argue the events are independent as follows: if we pick a random sequence of equal numbers of "Up or Left" and "Down or Right" to land on \$x=y\$ and likewise with "Up or Right" and "Down or Left" for \$x=-y\$, we can uniquely combine them into a sequence of Up, Down, Left, Right by taking the intersection of the pairs of directions at each position.

So, the probability of landing on \$x=y\$ or \$x=-y\$ is \$2s-s^2\$.

The code computes the binomial \$\binom{n}{n/2}\$ using this expression as (b+1)**n/b**(n/2)%b with base b=2**n. To extract the numerator from the probability fraction, we note that the denominator is a power of 2, so we use the expression r/(r&-r) to divide out the maximal power of 2 is r, expressed as the classic bit trick r&-r.

The solution is golfed by writing \$2s-s^2\$ as \$1-(1-s)^2\$ so that \$s\$ is only referenced once, and working without the \$1/2^n\$ fractions to stay within the integers. The computation is polynomial-time in \$n\$ even with the funky way of computing binomials.

---

After writing the proof of the probability the bot dies, I found a possibly cleaner way to prove it and present it.

Let's keep track of the values of \$a=x+y\$ and \$b=x-y\$ after each move of the bot. Each of the four directions up, down, left, and right either increments or decrements each of \$a\$ and \$b\$, with the four directions corresponding to the four combinations.

So, a random move is equivalent to randomly adding \$\pm 1\$ to \$a\$ and independently \$\pm 1\$ to \$b\$. This is equivalent to doing separate random walks on \$a\$ and \$b\$.

Now, the robot ends on the line \$x=y\$ or \$x=-y\$ exactly when \$a=0\$ or \$b=0\$. So, the probability of ending with \$a=0\$ is \$s=\frac{1}{2^n}\binom{n}{n/2}\$ and likewise for \$b=0\$. Since the walks are independent, the probability that \$a\neq 0\$ and \$b\neq 0\$ is \$(1-s)^2\$, so the probability that at least one is zero is the complement \$1-(1-s)^2\$.