Probabilidad de que quede una tortita entera y no dos mitades.

Question

Una pregunta muy interesante. Es trivial para un número pequeño de tortitas pero para 100 no he podido encontrar una forma analítica o manual de averiguar la probabilidad. ¡Muchas gracias de antemano si puedes compartir tus ideas!

Supongamos que tienes 100 tortitas para comer. Cada día te comes la mitad de una tortita. De este modo, después de un día quedarán 99 tortitas enteras y una media tortita. Supongamos que la elección de la tortita es aleatoria. Es decir, es igual de probable que elija cualquier panqueque restante, no importa que sea un panqueque entero o medio panqueque, para comerlo todos los días. Formalmente, si hay $X$ panqueques enteros y $Y$ medias tortitas al principio de algún día, entonces la probabilidad de que cada trozo de tortita sea recogido es $\frac{1}{X+Y}$ . Entonces, ¿cuál es la probabilidad de que después de $99\times 2 = 198$ días de comer, quedará un panqueque entero en lugar de 2 mitades de panqueques?

Fíjate que la pregunta podría interpretarse de otra manera, como apuntaba @Acccumulation en su respuesta. Así que, por favor, tened cuidado con la interpretación.

Por ejemplo, denotemos el índice del día por $k$ y el número de tortas enteras al (final del) día $k$ como $X_k$ (es decir, después de comer el panqueque), entonces $P(X_0 = 100) = 1$ , $P(X_1 = 99) = 1$ , $P(X_2 = 99) =1/100, P(X_2 = 98) = 99/100 $ .

Si denotamos el número de medias tortas al (final del) día $k$ como $Y_k$ entonces es fácil ver que $2X_k + Y_k + k = 200$ y $$P(X_{k+1} = X_k - 1) = \frac{X_k}{X_k+Y_k}, P(X_{k+1} = X_k) = \frac{Y_k}{X_k+Y_k}.$$ O lo que es lo mismo, $$P(X_{k+1} = X_k - 1) = \frac{X_k}{200-k-X_k}, P(X_{k+1} = X_k) = \frac{200-k-2X_k}{200-k-X_k}.$$ Sin embargo, esta relación depende tanto de los valores de $X_k$ y $k$ que es difícil de utilizar para la recursión a mano. ¿Alguien tiene alguna idea para hacer recursión o ir en otras direcciones? ¡Muchas gracias!

Answer 1

He aquí un método que proporciona la respuesta exacta $(0.14218003717754\ldots)$ que como fracción en términos mínimos tiene un numerador y un denominador con $3189$ dígitos decimales cada .

Para una notación conveniente, podemos representar $n$ panqueques por una cadena de $n$ números, donde cada número representa cuántas mitades de la torta correspondiente están presentes, eliminando cualquier $0$ s a medida que se producen. El procedimiento es entonces el siguiente:

1. Comience con una cadena de $n\ 2\text{s}$ y repite los siguientes pasos $2n-2$ tiempos.
2. Elige una posición en la cadena uniformemente al azar.
3. Resta $1$ del número en la posición elegida.
4. Si la resta da $0$ y luego eliminar ese elemento de la cadena.

La pregunta equivalente a la del OP es si el resultado del procedimiento es la cadena $2$ (que representa una tortita entera) o la cadena $11$ (que representan las mitades de dos panqueques diferentes).

Sea pS (donde S es una cadena) la probabilidad de que la repetición de los pasos 2-3-4 reduzca finalmente S a $2$ . Entonces encontramos el siguiente sistema de ecuaciones construyendo los árboles relevantes de caminos posibles, anotando los que llegan a la cadena $2$ :

p2 = 1

p12 = (1/2)*p2
p22 = p12

p112 = (2/3)*p12
p122 = (1/3)*p22 + (2/3)*p112
p222 = p122

p1112 = (3/4)*p112
p1122 = (2/4)*p122 + (2/4)*p1112
p1222 = (1/4)*p222 + (3/4)*p1122
p2222 = p1222

p11112 = (4/5)*p1112
p11122 = (3/5)*p1122 + (2/5)*p11112
p11222 = (2/5)*p1222 + (3/5)*p11122
p12222 = (1/5)*p2222 + (4/5)*p11222
p22222 = p12222

p111112 = (5/6)*p11112
p111122 = (4/6)*p11122 + (2/6)*p111112
p111222 = (3/6)*p11222 + (3/6)*p111122
p112222 = (2/6)*p12222 + (4/6)*p111222
p122222 = (1/6)*p22222 + (5/6)*p112222
p222222 = p122222

etc.

Aquí hay una imagen para el caso de p222, donde el número sobre una flecha indica el número de casos igualmente probables con sólo uno de los casos mostrados (por ejemplo, aquí 222 puede convertirse en cualquiera de los tres igualmente probables 122, 212 o 221, y sólo se muestra 122, etc.):

Así, las probabilidades de interés (es decir, p22, p222, p2222, etc.) están todas determinadas por las ecuaciones anteriores, con la condición inicial p2 = 1. Este sistema de ecuaciones puede escribirse como la siguiente recursión, con $n\ge1,\ 0\le i\le n-1$ :

$$\begin{align}P_i^{(n)} &= \begin{cases} 1, & \text{if}\ \ n=1,\ i=0\\[2ex] {n-1\over n}P_0^{(n-1)}, & \text{if}\ \ n>1,\ i=0\\[2ex] {n-(i+1)\over n}P_i^{(n-1)}+{i+1\over n}P_{i-1}^{(n)}, & \text{if}\ \ n>1,\ 0<i<n-1\\[2ex] P_{n-2}^{(n)}, & \text{if}\ \ n>1,\ i=n-1.\\ \end{cases} \end{align}$$

Aquí $P_i^{(n)}=$ pS $_i^{(n)}$ donde S $_i^{(n)}$ es cualquier cadena compuesta por $i+1\ 2s$ y $n-(i+1)\ 1s$ Así que la probabilidad que responde a la pregunta de la OP es $P_{n-1}^{(n)}$ con $n=100$ .

Estas ecuaciones se pueden programar (en Sage) de la siguiente manera, utilizando iteración en lugar de llamadas a funciones recursivas para calcular el caso $n=100$ en un tiempo razonable...

def next(L): # routine to be iterated   
# input the list L of n probabilities 
# output the list M of n+1 probabilities
    n = len(L) + 1
    M = [0]*n
    M[0] = L[0]*(n-1)/n
    for i in [1..n-2]: M[i] = L[i]*(n-i-1)/n + M[i-1]*(i+1)/n
    M[n-1] = M[n-2]
    return M

def prob(n): # iterate next() n-1 times, starting with L = [1]
# return the desired probability for a starting string of n 2s
    L = [1]
    for _ in [1..n-1]: L = next(L)
    return L[-1]

for n in [1..100]:
    p = prob(n) 
    print n, p.n(), p

Algunos resultados:

  1 1.00000000000000 1
  2 0.500000000000000 1/2
  3 0.388888888888889 7/18
  4 0.336805555555556 97/288
  5 0.305538888888889 54997/180000
  6 0.284236419753086 460463/1620000
  7 0.268560305649710 51185279267/190591380000
  8 0.256411353406832 200170674968477/780662292480000
  9 0.246639514750182 11369422537341929933/46097327708651520000
 10 0.238557094011412 6873027837417268175729/28810829817907200000000
 20 0.196966565034451             116 digits/116 digits
 50 0.161160193091085             793 digits/794 digits 
100 0.142180037177541            3189 digits/3189 digits
200 0.127470565382368           13921 digits/13921 digits
500 0.112388292456287           86903 digits/86904 digits

NB : Las simulaciones de Monte Carlo verifican estos resultados con tres decimales para $n$ hasta $100$ .

---

NB : La respuesta anterior utiliza una recursión diferente a la "más sencilla" mencionada por @lulu en un comentario, pero son equivalentes en el sentido de que dan exactamente las mismas probabilidades. Sin embargo, ninguna de las dos recursiones permite un cálculo factible del caso $n=100$ a menos que las llamadas a funciones recursivas (y los tiempos de ejecución exponencialmente crecientes) puedan evitarse utilizando la iteración en su lugar -- y no pude hacerlo con la recursión "más simple". Como referencia, la siguiente es una implementación (en Sage) de la recursión de @lulu usando llamadas a funciones recursivas, donde $P(n,m)$ es la probabilidad de que un estado $(n,m)$ (es decir $n$ panqueques enteros y $m$ mitades) finalmente alcanza el estado $(1,0)$ (es decir, una tortita entera y sin mitades):

$$\begin{align} P(n,m) &= \begin{cases} 0,&\text{if}\ \ m\ge0,n=0\\[2ex] \frac n{n+m} P(n-1,m+1)+\frac m{n+m} P(n,m-1), & \text{if}\ \ m>0,n>0\\[2ex] P(n-1,m+1),& \text{if}\ \ m=0,n>1\\[2ex] 1,&\text{if}\ \ m=0,n=1\\[2ex] \end{cases} \end{align}$$

def P(n,m):
    if n==0: return 0
    if n==1 and m==0: return 1
    if m==0: return P(n-1,m+1)
    return (n/(n+m))*P(n-1,m+1) + (m/(n+m))*P(n,m-1)

Ahora P(n,0) es igual a prob(n) pero en mi sistema el tiempo de ejecución de P(n,0) es al menos $3.6$ veces que para P(n-1,0) y P(100,0) requeriría más de $10^{45}$ horas (en comparación con menos de $1$ segundo para la iteración prob(100) ).

Answer 2

Si elige cada uno de los restantes medio panqueque con igual probabilidad, entonces estás creando efectivamente una secuencia aleatoria de $200$ medias tortitas. Por lo tanto, la probabilidad del $199$ -que el medio panqueque sea del mismo panqueque que el $200$ -ésima, es la misma que la probabilidad de que la segunda mitad de la tortita proceda de la misma tortita que la primera: cualquier consideración al considerar la secuencia desde un extremo es, por supuesto, completamente simétrica a considerar la secuencia desde el otro extremo (si no te dijera cuál es el primero y el último, no sabrías cuál es el extremo). Y, como la probabilidad de que la segunda mitad provenga del mismo panqueque que la primera es $\frac{1}{199}$ la probabilidad del $199$ -que el medio panqueque sea del mismo panqueque que el $200$ -th también es $\frac{1}{199}$ .

Sin embargo, parece que cada día se elige cada panqueque restante con igual probabilidad, tanto si está entero como si no, y esto introduce una asimetría. En particular, dado que en cualquier momento la probabilidad de elegir una tortita de la que ya se ha comido la mitad sigue siendo igual de alta que la de elegir una tortita que aún está entera, es más probable que se "acaben" las tortitas en comparación con la primera situación en la que cada medio se elige con la misma probabilidad. Por lo tanto, es de esperar que posteriormente se produzcan más pares de medias tortas provenientes de la misma torta, y por lo tanto mientras la probabilidad de que las dos primeras medias tortas provengan de la misma torta es $\frac{1}{100}$ la probabilidad de que las dos últimas mitades provengan del mismo panqueque será mayor.

Otra forma de ver esto es la siguiente: supongamos que cerca del final te quedas con $3$ medias tortitas, dos de las cuales son de la misma tortita, es decir, te quedas con $A1$ , $A2$ y $B1$ . Ahora, si cada medio panqueque se elige con igual probabilidad, entonces la probabilidad de obtener los dos $A$ como sus dos últimas mitades es $\frac{1}{3}$ . Sin embargo, ahora que estamos eligiendo si tomar un medio panqueque de $A$ o $B$ con igual probabilidad, la probabilidad de obtener los dos $A$ como sus dos últimos medios en esta situación es $\frac{1}{2}$ .

OK ... entonces ... Todavía no veo una forma rápida de calcular la probabilidad en estas condiciones. Hmmm...

Hice los cálculos para $3$ panqueques, y encontró que mientras la probabilidad de obtener los dos primeros medios panqueques provenientes del mismo panqueque es por supuesto $\frac{1}{3}$ la probabilidad de que las dos últimas medias tortas provengan de la misma torta es $\frac{7}{18}$ .. así que sí, efectivamente un poco más alto que $\frac{1}{3}$

Answer 3

Si interpretas cada media tortita como una entidad distinta (y así tienes 200 entidades distintas), la probabilidad de que hayas consumido 99 tortitas enteras después de 198 días comiendo viene dada por $\frac{100\choose 99}{200 \choose 198}=\frac{1}{199}$ .

Answer 4

La pregunta está redactada de forma imprecisa. Supongamos que interpretamos que hay esencialmente 200 medias tortas, cada una emparejada con un compañero. Cada día, se elige al azar una media torta para cada uno. ¿Cuál es la probabilidad de que las dos medias tortas restantes sean parejas? Podemos elegir libremente la "primera" media torta, y quedan 199 medias tortas, de las cuales sólo una es la pareja, por lo que la probabilidad es de 1/199.

Sin embargo, podría interpretarse como que eliges al azar entre las tortitas que tienen al menos la mitad restante, y te comes la mitad. Así, en la primera interpretación, cada media tortita restante tiene la misma probabilidad de ser comida, pero en la segunda interpretación, cada tortita tiene la misma probabilidad de que se coma la mitad. Así, en la primera interpretación, las tortitas enteras tendrían el doble de probabilidades que las medias tortitas de que se coman la mitad, mientras que en la segunda interpretación, tendrían la misma probabilidad. En la segunda interpretación, podemos ver esto como la elección de qué tortitas nos comeremos los días 199 y 200. Si hacemos la misma elección cada vez, entonces nos comimos una tortita entera el día 198. La probabilidad de que ambas elecciones sean iguales es de 1/100.

Answer 5

Cuando lo haces por $3$ panqueques, el estado final tendrá $18$ entero o $36$ mitades que conducen a una probabilidad de entero $1/3$ . No hay garantía de que la probabilidad siga siendo la misma para $4$ o más panqueques.

En concreto, el argumento de elegir $2$ mitades del total es incorrecto, ya que las mismas mitades pueden llegar por varios caminos.