Let X = the number of remaining open parenthesis required to reach your target length, and Y = the number of remaining close parenthesis.

Let P(X) = X/(X+Y) * (1 + 1/(Y-X+1)). Generate an open parenthesis with probability P(X), and otherwise a close parenthesis.

This will efficiently generate an unbiased random plane tree. The reason this works has to do with counting the valid ways to complete the plane tree, using a calculation similar to the one in the article.

I think the first sentence is very confusing, as the two most obvious ways to interpret it are wrong:

1. The tail sequence beginning at s_i consists of just 1 and -1 values, and it's certainly not the case that the "end" (last element) of that sequence must be 1 -- indeed, in the example it's -1.

2. What if we interpret "the end of the tail sequence beginning at s_i" as the sum of that sequence? But then this is also not always true: You can easily construct a tail sequence where this sum is much higher than 1.

I think the intended meaning is: "We know that the last element in the sequence of all partial sums must be 1 [because there is in total one more 1 than -1 in the original sequence, and the rest cancel in pairs]." I.e., with no mention of s_i at all (yet).

But even this is not enough to establish that the partial sums in just the tail sequence never dip below 1, which is required for the next step (rotating it to the front) to go through.

I think there's a much clearer way to prove this, which actually makes use of the "rightmost lowest" choice of i:

Suppose to the contrary that some j > i exists such that the sum of elements at positions i+1, i+2, ..., j is N' <= 0. Then this contradicts the "rightmost lowest" choice of i, since the sum of the first j elements of the entire sequence is N+N' <= N (at least as low) and j > i (strictly to the right).

That contradiction establishes that the tail sequence is itself free of dangerous dips. To establish that the sum of all elements in the sequence is 1-N (which is needed to show that rotating it to the start will be enough to boost the original "head" sequence to safety), it's enough to observe that the entire sequence sums to 1, and the head sequence sums to N, so what's left (which is exactly the elements of the tail sequence) must sum to 1-N.