Probability of Bride entering the Church?
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}$$
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;
}