fast string fixing Hi I'm trying to prove something and i would appreciate some help.
Given an uniformly 2n long randomly  selected string  of Parenthesis( "(",")" ) prove that
it is possible to generate  a valid sequence of parenthesis by changing  csqrt(nlogn) chars
at most where c is constant in probability of 1-o(1) .
 A: Given a string of parentheses, and $i\in \{1,\dots,2n\}$, let $o_i$ be the number of open parentheses in the first $i$ symbols of the string, and let $c_i$ be the number of closed parentheses in this prefix. There are two quantities of interest:

*

*Let $X=o_{2n}-c_{2n}$ be the excess of open parentheses over closed parentheses.


*Let $Y=\max_{0\le i\le 2n}(c_i-o_i)$ be the worst case excess of closed parentheses over open parentheses in any prefix.
I claim that you can make a permutation valid in $O(X+Y)$ moves. This can be done as follows:

*

*As long as there is an unmatched closed parenthesis, flip the leftmost unmatched parenthesis. This decreases $Y$ by at least one, and increases $X$ by two.


*Then, until the number of parentheses of each type are equal, flip the rightmost open parenthesis. This decreases $X$ by two without changing $Y$.
Therefore, all that remains is to show that $X+Y$ is at most $c\sqrt{n\log n}$ with probability at least $1-o(1)$. It is easy to see this is true of $X$, since $X$ is approximately normal with a mean of $0$ and a variance of $O(\sqrt{n})$. The variable $Y$ is much trickier. However, using the reflection principle, you can show that $Y$ shares the same probabilistic bound.
To give some details, identify parenthesis string with lattice walks, where an open parenthesis is the step $(1,1)$ and a closed parenthesis is the step $(1,-1)$. Then $Y$ is the absolute value of the lowest height of the path, while $X$ is the final height of the path. You can then show that, for any $k\ge 0$,
$$
P(Y> k)\le 2P(X> k)\tag{*}
$$
This is because paths whose lowest height is at least $k$ come in two flavors:

*

*Those paths whose final height is less than $-k$; the probability of this is exactly $P(X>k)$.


*Those whose final height is more than $-k$, but which attain $-k$ at some intermediate point. By taking the first point this path hits $-k$ and reflecting everything (that is, switching $(1,-1)$ with $(1,1)$), you get a path whose final height is less than $-k$. Since this process is reversible, the probability of these paths is at most $P(X>k)$.
As long as you believe $(*)$, you know now that $Y$ enjoys the same probability bound that $X$ does, which means the same is true of $X+Y$.
