This a followup to a question I asked here. I am hoping to get some feedback on a possible proof of the claim (showing that the probability of winning the match for either player is equal). Specifically, the "Reversing Arrows" section below and any glaring errors.
Grid Representation
Let us start by visualizing the problem using a grid.
Consider the case where $n = 3$. We have P1 starting on Char 1 and P2 starting on Char 3. We can represent this via the diagram below, where each box represents a possible matchup; moving to the right is a win for P2 and moving down is a win for P1. This means that P1 winning the match is represented by a sequence of down and right moves leading off the bottom of the grid whereas P2 winning the match is represented by a similar sequence leading off the right side of the grid. We also consider any set of probabilities (with the assumption of no 100/0 matchups).
Now consider generalizing to a set of unique characters (so every matchup is unique). For convenience, let us label P2's characters 3 to 1 and P1's characters 4 through 6. The grid now looks like the following:
Ordered Games BO5 as Motivation
Taking a quick detour, let us consider a "1-D" version of this problem with ordered games in a best of five.
Suppose we have two players (P1 and P2) who play games against each other. They play a match with 5 games (labeled 1 through 5) where each game has a unique probability for P1 or P2 to win (which is where the ordering comes into play). So Game 1 has probability $p_1$ for P1 and $q_1 = 1-p_1$ for P2, Game 2 is $p_2$ and $q_2$ and so on, with the assumption that $p_i$ is not necessarily equal to $p_j$ for all $i$ and $j$ (and standard assumption of no 100/0 matchups).
In this situation an interesting symmetry arises: the probability for P1 to win when playing the games in order from 1 to 5 is the same as the probability of P1 winning when playing the games in the reverse order (or any other order for that matter). This is because once P1 has won three games, essentially the rest of the games in that particular match don't matter (playing them doesn't change the fact that P1 has already won). Mathematically this is accounted for in the probability when extending every match to five games and considering all the possible W/L sequences.
Connection to Grid Idea (Reversing Arrows)
How does this relate to the "2-D" version of the problem? Looking at our diagram, we have a parallel to the "1-D" example: P1 winning a "2-D" match consists of P1 winning valid BO5s (each path corresponding to a particular configuration) starting with the (3,4) matchup (the specific probabilities per game changing based on the W/L record).
With this motivation, consider changing the order of the matchups -- specifically, let us reverse the order of the matchups. This amounts to reversing the arrows on the grid in a consistent manner.
Instead of starting with P1 on 4 and P2 on 3, we start P1 on 6 and P2 on 1 -- the last possible matchup. In every game, we have two states that we can go to based on the W/L probability in the forward direction. When reversing we have to choose which probability leads to which outcome.
For example, winning (5, 1) or losing (6, 2) both lead to the state (6, 1). Reversed, we have winning (6, 1) leads to (5, 1) and losing (6, 1) leads to (6, 2). This assignment counts the paths in the same way since we have the winner switching character. The following diagram shows the original paths on the left and the new reversed paths on the right with probabilities.
Now consider the probability that P1 wins in this new grid. When reversing the arrows we must maintain the total probability of P1 winning because (1) every path to victory traverses the same P1 win matchups (the reversed arrows in the vertical direction are the same for every path) and (2) we counted the paths the same way.
So the probability of P1 winning in the "forward" configuration is the same as the probability of P1 winning in the "reverse" configuration.
Application to Original Problem
Finally we consider our original case (with P1 playing 1 to 3 and P2 playing 3 to 1). It is clear to see that by symmetry, the paths defined by reversing arrows corresponding to P1 winning are exactly the paths that correspond to P2 winning (shown below).
By the reverse arrow argument in the previous section, the total probabilities of winning are the same (being a specific case of the general claim above with 4 = 1, 5 = 2, and 6 = 3) and since the sum of their probabilities must add up to 1, the probability of P1 and P2 winning must both be 0.5.
Therefore the claim is proved for $n = 3.$ We can extend this analysis to other $n$ with some minor modifications.