9
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ If we assume that the process stops once the bride enters the church, the probability is 10/11. $\endgroup$ – PM 2Ring Oct 18 '17 at 8:15
  • $\begingroup$ @PM2Ring Please explain. $\endgroup$ – MalayTheDynamo Oct 18 '17 at 9:17
  • 3
    $\begingroup$ Think about how many ways she can not enter the church. For this to happen, at all times, the number of steps back has to be at least the number of step forward. How many ways are there to do that? $\endgroup$ – Louis Oct 18 '17 at 9:21
  • $\begingroup$ @MalayTheDynamo I've added a proper answer, although it doesn't derive the formulas I've used; the interested reader can find standard proofs in the literature. $\endgroup$ – PM 2Ring Oct 18 '17 at 9:51
  • 2
    $\begingroup$ @MalayTheDynamo It may help to think of it in terms of the lattice paths on a 2D grid, as shown in the middle of the Applications in combinatorics section of the Wikipedia Catalan number article. The Dyck paths are those which don't cross the diagonal of the grid, they correspond to bride paths that don't enter the church. $\endgroup$ – PM 2Ring Oct 18 '17 at 10:04
19
$\begingroup$

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 & 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] < a[j + 1]:
                break
        else:
            return

        v = a[j]
        for k in range(n, j, -1):
            if v < 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 > 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}$$

$\endgroup$
  • $\begingroup$ +1 nice! So what about the expected value of the steps that the bride has to take to enter the church, given that she enters it? $\endgroup$ – Ant Oct 18 '17 at 11:51
  • 1
    $\begingroup$ @Ant I've added that info to my answer. $\endgroup$ – PM 2Ring Oct 18 '17 at 12:27
  • 1
    $\begingroup$ @PM 2Ring: Thanks a lot! Your answers are beautiful. $\endgroup$ – JackT Oct 18 '17 at 12:40
  • 1
    $\begingroup$ I'd like to share a solution in C++ here because I found the problem quite interesting. The program starts with the string "00000000001111111111" and goes through all lexicographic permutations. For each permutation it goes through the string and checks if the number of ones exceeds the number of zeros. You can click on 'edit' to change the string s and check the other cases, e.g. 6 red roses and 6 white roses. $\endgroup$ – Flatfoot Oct 18 '17 at 17:18
  • 1
    $\begingroup$ @Flatfoot You may be interested in some Python code I wrote last year that generates Dyck sequences: it's quite a bit faster than filtering all the permutations. $\endgroup$ – PM 2Ring Oct 18 '17 at 18:01
3
$\begingroup$

As per suggestion by @pm-2ring I'm posting my comment from above as an answer.

I'd like to share a solution in C++ because I found the problem quite interesting.

  • The program starts with the string "00000000001111111111" and goes through all lexicographic permutations by using Pandita's algorithm.
  • For each permutation it goes through the string and checks if the number of ones exceeds the number of zeros. You can click on 'edit' to change the string and check the other cases, e.g. set the string to "000111" to check the case with 3 red roses and 3 white roses.

I also implemented a solution in Python. As mentioned by @pm-2ring there is no built-in function that returns the next lexicographic permutation in Python, so I had to implement Pandita's algorithm.

Edit: - Added sourcecode in C++, Python and C

The program's output for 10 red and 10 white roses is:

number of times bride entered church: 167960
total permutations: 184756
probability: 0.909091

Code in C++:

#include <bits/stdc++.h>
using namespace std;


int main() {
    string s = "00000000001111111111";            // red and white roses 
    sort(s.begin(), s.end());

    int total_permutations = 0;
    int count_in_church = 0;


    // check next lexicographic permutation of s 
    do {
        total_permutations += 1;

        // check if bride steps into church by checking if
        // the number of ones exceeds the number of zeros
        int cnt_0 = 0;
        int cnt_1 = 0;

        for (char c : s) {
            if (c == '0') {cnt_0 += 1;}
            else {cnt_1 += 1;}

            if (cnt_1 > cnt_0) {
                count_in_church += 1;
                break;
            }
        }

    } while(std::next_permutation(s.begin(), s.end()));


    cout << "number of times bride entered church: " << count_in_church << '\n';
    cout << "total permutations: " << total_permutations << '\n';
    cout << "probability: " << 1.0 * count_in_church / total_permutations << '\n';
}

Code in Python:

def next_permutation(L):
    '''
    Permute the list L in-place to generate the next lexicographic permutation.
    Return True if such a permutation exists, else return False.
    '''

    n = len(L)

    #------------------------------------------------------------

    # Step 1: find rightmost position i such that L[i] < L[i+1]
    i = n - 2
    while i >= 0 and L[i] >= L[i+1]:
        i -= 1

    if i == -1:
        return False

    #------------------------------------------------------------

    # Step 2: find rightmost position j to the right of i such that L[j] > L[i]
    j = i + 1
    while j < n and L[j] > L[i]:
        j += 1
    j -= 1

    #------------------------------------------------------------

    # Step 3: swap L[i] and L[j]
    L[i], L[j] = L[j], L[i]

    #------------------------------------------------------------

    # Step 4: reverse everything to the right of i
    left = i + 1
    right = n - 1

    while left < right:
        L[left], L[right] = L[right], L[left]
        left += 1
        right -= 1

    return True



#-------------------------------------------------------------------
#-------------------------------------------------------------------

def example():
    count_in_church = 0
    total_permutations = 0
    k = 10
    L = k*[0] + k*[1]

    while True:
        total_permutations += 1

        # check if bride steps into church by checking if
        # the number of ones exceeds the number of zeros
        cnt_0 = 0
        cnt_1 = 0

        for c in L:
            if c == 0: cnt_0 += 1
            else: cnt_1 += 1

            if cnt_1 > cnt_0:
                count_in_church += 1
                break

        if not next_permutation(L):
            break

    print("number of times bride entered church: ", count_in_church)
    print("total permutations:", total_permutations)
    print("probability:", count_in_church / total_permutations)


#----------------------------------------------------------------

if __name__ == "__main__":
    example()

Code in C:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//-----------------------------------------------------------------

// Pandita's algorithm to generate next lexicographic permutation

bool next_permutation(char *L, int n) {
  // Step 1: find rightmost position i such that L[i] < L[i+1]
  int i = n - 2;
  while ((i >= 0) && (L[i] >= L[i+1])) i--;
  if (i==-1) return false;

  // Step 2: find rightmost position j to the right of i such that L[j] > L[i]
  int j = i + 1;
  while ((j < n) & (L[j] > L[i])) j += 1;
  j -= 1;

  // Step 3: swap L[i] and L[j]
  char tmp = L[i];
  L[i] = L[j];
  L[j] = tmp;

  // Step 5: reverse everything to the right of i
  int left = i + 1;
  int right = n - 1;

  while (left < right) {
    tmp = L[left];
    L[left] = L[right];
    L[right] = tmp;
    left += 1;
    right -= 1;
  }

  return true;
}


//-----------------------------------------------------------------

int main(){
  char L[] = "00000000001111111111";
  int n = strlen(L);

  int count_in_church = 0;
  int total_permutations = 0;

  while (1) {

    total_permutations += 1;
    // check if bride steps into church by checking if
    // the number of ones exceeds the number of zeros
    int cnt_0 = 0;
    int cnt_1 = 0;


    for (int i=0; i<n; i++) {
      char c = L[i];
      if (c == '0') cnt_0 += 1;
      else cnt_1 += 1;

      if (cnt_1 > cnt_0) {
        count_in_church += 1;
        break;
      }
    }


    if (!next_permutation(L,n)) break;
  }


  printf("number of times bride entered church: %d\n", count_in_church);
  printf("total permutations: %d\n", total_permutations);

  float ratio = 1.0 * count_in_church / total_permutations;
  printf("probability: %f\n", ratio);

    return 0;
}
$\endgroup$
  • $\begingroup$ @Flatfoot: Can you share the code in C? Thanks for a great answer though. $\endgroup$ – JackT Oct 18 '17 at 18:08
  • $\begingroup$ @Maths_student: Sorry, I'm not proficient in C. However, I have another approach that gives you an approximate value by using a Monte Carlo simulation. You take the string "00000000001111111111" and shuffle the ones and zeros to get a random permutation. For each permutation you check if the bride stepped into the church. Repeat this e.g. 10000 times to take the average. Here is the code in Python. $\endgroup$ – Flatfoot Oct 18 '17 at 19:38
  • 1
    $\begingroup$ @maths-student : I managed to implement the solution with the lexicographic permutation it in C. You can find the code here, here and here (just in case one of the websites goes down). $\endgroup$ – Flatfoot Oct 19 '17 at 0:27
  • 1
    $\begingroup$ Is code in three different languages (or even one) really an answer on Mathematics Stack Exchange? $\endgroup$ – David Richerby Oct 19 '17 at 8:16
  • $\begingroup$ @DavidRicherby I see your point. I was initially hesitant to post the code, however I was encouraged by another user to do so. And OP also asked for the C code. $\endgroup$ – Flatfoot Nov 2 '17 at 11:06
-1
$\begingroup$

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)>{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>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}$.

$\endgroup$
  • $\begingroup$ I am also 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 now 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 ($\leqslant 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. $\endgroup$ – JackT Oct 18 '17 at 7:42
  • $\begingroup$ @Maths_student Actually, if you have got $x_1$ Red Roses and $y_1$ White roses, then you must get $y_1-x_1+1$ more red roses to enter the church. Or, rather, $x_2-y_2$ should be $y_1-x_1+1$. $\endgroup$ – MalayTheDynamo Oct 18 '17 at 7:49
  • 4
    $\begingroup$ Your edit is incorrect. If she takes a red rose on the first try, she enters, so the probability has to be at least $1/2$ as you said. She can also enter the church if she initially takes a white rose, then takes two red roses in a row. Clearly, the probability is much greater than $1/20$. $\endgroup$ – N. F. Taussig Oct 18 '17 at 9:34
  • 3
    $\begingroup$ You seem to be calculating based on 20 roses of each colour, the question had 10. You've also removed all outcomes with $r > w+1$ from your numerator. That's fine so far, but then set your denominator to $20 \times 20 = 400$, which is the total number of possibilities for $(r,w)$ with $r \leq 20, w \leq 20$ - including all of the outcomes you just excluded from your numerator, all of which would correspond to the bride entering the church.You also seem to be assuming equal probabilities for each $(r,w)$, which isn't valid. $\endgroup$ – Chris H Oct 18 '17 at 11:36
  • 3
    $\begingroup$ @MalayTheDynamo Order is necessary because every time the father takes out a rose, he gives it to the Bride. He does not put it back into the basket. It means every time a rose has been taken out, the probability of the next rose to be taken out changes. At the end of the sequence, however, you may argue, that the arrangements did not matter because there were equal number of roses (assuming that the Bride never entered the Church). Nonetheless, you would have not considered those arrangements where the Bride already entered the Church. For instance the arrangement $WWRRRWR$. $\endgroup$ – JackT Oct 18 '17 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.