Probability of Bride entering the Church? A Bride is standing at the entrance of a church with her father (one step forward will take her into the church). Her father has a basket containing $10$ White roses and $10$ Red roses. He takes $1$ rose at a time from the basket and gives it to the Bride. If the rose is Red, the Bride takes $1$ step towards the church and if it is White, she takes $1$ step away from the church. What is the probability that the Bride enters the church? Assume that Bride's father can not see the rose until he takes the rose out of the basket.

I am stuck at this point: If the first rose is Red then the Bride enters the Church and in that case the probability is $\frac{10}{20}$. But then come the cases when the first rose is White: WRR, WWRRR, WRWRR and so on. No matter what, if the first rose is White, the last two roses must be Red. And the total number of roses required (⩽20) to enter the church is Odd, where the number of Red roses will never exceed that of the White roses but once when the Bride finally enters the church. Leaves me in doldrums, though
This problem can be stated in terms of Dyck Paths. Let $n$ be the number of roses of each colour, so there are a total of $2n$ roses. A rose sequence will take the bride into the church if at any point in the sequence the number of red roses exceeds the number of white roses. So the sequences that keep the bride out of the church are those where the number of red roses never exceeds the number of white roses. Those sequences that keep her out of the church correspond to Dyck paths of length $2n$.

Dyck paths / Dyck words are often represented using parentheses, with a Dyck path corresponding to a correctly-nested sequence of parentheses.

To illustrate, here are the sequences for $n = 3$, using parentheses, w &amp; r for the roses, and - and + for the bride's steps.

1 ()()() wrwrwr -+-+-+
2 ()(()) wrwwrr -+--++
3 (())() wwrrwr --++-+
4 (()()) wwrwrr --+-++
5 ((())) wwwrrr ---+++


From the '-+' strings we can easily see that the number of '+'s never exceeds the number of '-'s.

The Wikipedia article on Catalan numbers has some good information on this topic. In particular, see the second and third proofs, which have helpful diagrams.

The total number of Dyck paths of length $2n$ is 

$$\frac{1}{n+1} \binom{2n}{n}$$

where $\binom{m}{r}$ is the binomial coefficient. $\binom{m}{r} = \frac{m!}{r!(m-r)!}$

The total number of all the paths is 

$$\binom{2n}{n}$$ 

So the number of non-Dyck paths is 

$$\binom{2n}{n} - \frac{1}{n+1} \binom{2n}{n} = \frac{n}{n+1} \binom{2n}{n}$$ 

Hence the probability we seek is 

$$\frac{\frac{n}{n+1} \binom{2n}{n}}{\binom{2n}{n}} = \frac{n}{n+1}$$

For the case of $n = 10$, the probability is 10/11 = 0.909090...



In the comments, Ant asks 


  What's the expected number of steps that the bride has to take to enter the church, given that she enters it?


The answer is given in OEIS A008549, 

Number of ways of choosing at most n-1 items from a set of size 2n+1.


  Area under Dyck excursions (paths ending in 0): a(n) is the sum of the
  areas under all Dyck excursions of length 2*n (nonnegative walks
  beginning and ending in 0 with jumps -1,+1).


The relevant formula says that the total number of steps is given by

$$4^n - \binom{2n+1}{n}$$

So to get the expected number of steps we need to divide that by the number of successful paths, i.e., non-Dyck paths. 

$$\left(\frac{4^n - \binom{2n+1}{n}}{\binom{2n}{n}}\right)\frac{n+1}{n}$$
$$= \left(\frac{4^n}{\binom{2n}{n}} - \frac{2n+1}{n+1}\right)\frac{n+1}{n}$$
$$= \frac{4^n}{\binom{2n}{n}}\frac{n+1}{n} - \frac{2n+1}{n}$$
$$= \frac{4^n}{\binom{2n}{n-1}} - \frac{2n+1}{n}$$



Here's a table showing the relevant numbers for $n$ = 1..10

 n: paths success     prob :  steps expected
 1:      2      1 0.500000 :      1 1.000000
 2:      6      4 0.666667 :      6 1.500000
 3:     20     15 0.750000 :     29 1.933333
 4:     70     56 0.800000 :    130 2.321429
 5:    252    210 0.833333 :    562 2.676190
 6:    924    792 0.857143 :   2380 3.005051
 7:   3432   3003 0.875000 :   9949 3.313020
 8:  12870  11440 0.888889 :  41226 3.603671
 9:  48620  43758 0.900000 : 169766 3.879656
10: 184756 167960 0.909091 : 695860 4.143010


That table was created using this Python 3 code:

from itertools import product

def lexico_permute(a):
    a = list(a)
    yield a
    n = len(a) - 1
    while True:
        for j in range(n-1, -1, -1):
            if a[j] &lt; a[j + 1]:
                break
        else:
            return

        v = a[j]
        for k in range(n, j, -1):
            if v &lt; a[k]:
                break

        a[j], a[k] = a[k], a[j]
        a[j+1:] = a[j+1:][::-1]
        yield a

def bride(num):
    success = 0
    steps = 0
    base = [-1] * num + [1] * num
    for i, seq in enumerate(lexico_permute(base), 1):
        pos = 0
        for j, u in enumerate(seq, 1):
            pos += u
            if pos &gt; 0:
                success += 1
                steps += j
                break
    return i, success, steps

print(' n: paths success     prob :  steps expected')
fmt = '{:2}: {:6} {:6} {:0.6f} : {:6} {:0.6f}'
for n in range(1, 11):
    total, success, steps = bride(n)
    prob = success / total
    expected = steps / success
    print(fmt.format(n, total, success, prob, steps, expected))




I guess it's worth mentioning (especially in relation to the expected number of steps) that

$$\binom{2n}{n} \approx \frac{4^n}{\sqrt{\pi n}}$$

as mentioned in Central binomial coefficient.

A better approximation is 

$$\frac{4^n}{\sqrt{\pi n}} \frac{16n-1}{16n+1}$$

Thus the expected number of steps is approximately

$$\sqrt{\pi n} \left(\frac{16n+1}{16n-1}\right) \left(\frac{n+1}{n}\right) - \frac{2n+1}{n}$$
The obvious answer should be $1\over2$, but it is not. If you get a red rose at first, then she enters. Since the Probability of this is $1\over2$, therefore $P(x)&gt;{1\over2}$. But if she tales a white one, then you need two consecutive red ones to get into the church. This continues.

I can't figure out the final answer but it should help.



Edit

The only outcomes in which the bride enters the church is where $r&gt;w$, and the order does not matter. But, of all possible outcomes the only ones in which $r=w+1$ will do, since if it was more than one, it would not make sense, as the father would not choose roses after the bride had entered the Church.

There are only 20 possiblities in which $r=w+1$, namely:

$(1,0),(2,1),(3,2),(4,3),(5,4),\dots,(17,16),(18,17),(19,18),(20,19)$.

Out of the $20\cdot20=400$ possiblites. Therefore, the probablity is ${20\over400}={1\over20}$.