¿Probabilidad de que la novia entre en la Iglesia?

Question

Una novia está de pie en la entrada de una iglesia con su padre (un paso adelante la llevará a la iglesia). Su padre tiene una cesta que contiene $10$ Rosas blancas y $10$ Rosas rojas. Él toma $1$ rosa a la vez de la cesta y se la da a la novia. Si la rosa es roja, la novia toma $1$ paso hacia la iglesia y si es blanca, toma $1$ alejarse de la iglesia. ¿Cuál es la probabilidad de que la Novia entre en la iglesia? Supongamos que el padre de la novia no puede ver la rosa hasta que la saca de la cesta.

Estoy atascado en este punto: Si la primera rosa es Roja entonces la Novia entra en la Iglesia y en ese caso la probabilidad es $\frac{10}{20}$ . Pero luego vienen los casos en que la primera rosa es blanca: WRR, WWRRR, WRWRR y así sucesivamente. Sea como sea, si la primera rosa es blanca, las dos últimas deben ser rojas. Y el número total de rosas necesarias (20) para entrar en la iglesia es impar, donde el número de rosas Rojas nunca superará al de las rosas Blancas sino una vez cuando la Novia entre finalmente en la iglesia. Sin embargo, me deja de piedra

Answer 1

Este problema puede plantearse en términos de Caminos de Dyck . Sea $n$ sea el número de rosas de cada color, por lo que hay un total de $2n$ rosas. Una secuencia de rosas llevará a la novia a la iglesia si en algún momento de la secuencia el número de rosas rojas supera al de rosas blancas. Por lo tanto, las secuencias que mantienen a la novia fuera de la iglesia son aquellas en las que el número de rosas rojas nunca supera el número de rosas blancas. Las secuencias que la mantienen fuera de la iglesia corresponden a caminos de Dyck de longitud $2n$ .

Los caminos de Dyck / las palabras de Dyck suelen representarse mediante paréntesis, correspondiendo un camino de Dyck a una secuencia de paréntesis correctamente anidada.

Para ilustrar, aquí están las secuencias para $n = 3$ , utilizando paréntesis, w & r para las rosas, y - y + para los pasos de la novia.

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

A partir de las cadenas "-+" podemos ver fácilmente que el número de "+" nunca supera al de "-".

El artículo de Wikipedia sobre Números catalanes tiene buena información sobre este tema. En particular, véase el segundo y tercera pruebas, que tienen diagramas útiles.

El número total de trayectorias Dyck de longitud $2n$ es

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

donde $\binom{m}{r}$ es el coeficiente binomial. $\binom{m}{r} = \frac{m!}{r!(m-r)!}$

El número total de todas las trayectorias es

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

Así que el número de trayectorias no Dyck es

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

Por lo tanto, la probabilidad que buscamos es

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

Para el caso de $n = 10$ la probabilidad es 10/11 = 0,909090...

---

En los comentarios , Ant pregunta

¿Cuál es el número esperado de pasos que la novia tiene que dar para entrar en la iglesia, dado que entra en ella?

La respuesta se da en la OEIS A008549 ,

Número de formas de elegir como máximo n-1 elementos de un conjunto de tamaño 2n+1.

Área bajo excursiones de Dyck (caminos que terminan en 0): a(n) es la suma de las áreas bajo todas las excursiones de Dyck de longitud 2*n (paseos no negativos que comienzan y terminan en 0 con saltos -1,+1).

La fórmula correspondiente dice que el número total de pasos viene dado por

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

Por lo tanto, para obtener el número esperado de pasos tenemos que dividirlo entre el número de trayectorias exitosas, es decir, las trayectorias que no son de Dyck.

$$\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}$$

---

Aquí hay una tabla que muestra los números relevantes para $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

Esa tabla se creó con este código de Python 3:

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))

---

Supongo que vale la pena mencionar (especialmente en relación con el número esperado de pasos) que

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

como se menciona en Coeficiente binomial central .

Una mejor aproximación es

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

Por lo tanto, el número esperado de pasos es aproximadamente

$$\sqrt{\pi n} \left(\frac{16n+1}{16n-1}\right) \left(\frac{n+1}{n}\right) - \frac{2n+1}{n}$$

Answer 2

Según la sugerencia de @pm-2ring estoy publicando mi comentario de arriba como respuesta.

Me gustaría compartir un solución en C++ porque el problema me pareció bastante interesante.

• El programa comienza con la cadena "000000000011111111" y recorre todas las permutaciones lexicográficas utilizando El algoritmo de Pandita .
• Para cada permutación recorre la cadena y comprueba si el número de unos supera al de ceros. Puedes hacer clic en "editar" para cambiar la cadena y comprobar los otros casos, por ejemplo, poner la cadena a "000111" para comprobar el caso con 3 rosas rojas y 3 rosas blancas.

También implementé un solución en Python . Como mencionó @pm-2ring no hay ninguna función incorporada que devuelva la siguiente permutación lexicográfica en Python, así que tuve que implementar el algoritmo de Pandita.

Editar: - Añadido el código fuente en C++, Python y C

La salida del programa para 10 rosas rojas y 10 blancas es:

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

---

Código en 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';
}

---

Código en 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()

---

Código en 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;
}

Answer 3

La respuesta obvia debería ser $1\over2$ pero no lo es. Si al principio se obtiene una rosa roja, entonces ella entra. Como la probabilidad de esto es $1\over2$ Por lo tanto $P(x)>{1\over2}$ . Pero si ella cuenta una blanca, entonces necesitas dos rojas consecutivas para entrar en la iglesia. Esto continúa.

No puedo averiguar la respuesta final pero debería ayudar.

---

Editar

Los únicos resultados en los que la novia entra en la iglesia es cuando $r>w$ y el orden no importa. Pero, de todos los resultados posibles los únicos en los que $r=w+1$ servirá, ya que si fuera más de uno, no tendría sentido, ya que el padre no elegiría las rosas después de que la novia hubiera entrado en la Iglesia.

Sólo hay 20 posibilidades en las que $r=w+1$ a saber:

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

Fuera del $20\cdot20=400$ posibles. Por lo tanto, la probabilidad es ${20\over400}={1\over20}$ .