Supongamos que hay n bolas con diferentes colores unos con otros en una bolsa. En un bucle, Una toma de dos bolas en la secuencia de la bolsa y reemplazarlos con dos bolas con el mismo color de la primera bola. P: ¿cuántos bucles se tarda en hacer todas las bolas del mismo color en promedio?
Respuesta
¿Demasiados anuncios?
Muy interesante problema, y esto es más bien una escritura de un cálculo experimento para explorar.
Como ya se ha señalado en los comentarios, la dinámica de la urna puede ser descrito por una cadena de Markov en el entero de las particiones de $n$. Deje $\{m_1, \ldots, m_k \}$ ser una partición. Supongamos que $i$, $j$, tal que $1 \leqslant i,j\leqslant k$, son los dos tipos de bola dibujado en un bucle. Si $i=j$, la urna permanece en el mismo estado con la probabilidad de $\frac{m_i}{n} \frac{m_i-1}{n-1}$, de lo contrario, la transición a una nueva partición con $m_i$ incrementa de uno en uno, y $m_j$ disminuyeron en 1 con una probabilidad de $\frac{m_i}{n} \frac{m_j}{n-1}$.
Aquí un Mathematica código que construye un número finito de Markov del proceso:
computeProbabilities[p : {n_}, as_] := {{as[p], as[p]} -> 1}
computeProbabilities[p_List, as_] :=
Module[{n = Length[p], tot = Total[p], bag, pnew},
bag = {};
Do[
If[i == j,
If[p[[i]] > 1,
AppendTo[bag, {as[p], as[p]} -> p[[i]]/tot (p[[i]]-1)/(tot-1)]
],
pnew = DeleteCases[p + UnitVector[n, i] - UnitVector[n, j], 0];
pnew = Sort[pnew, Greater];
AppendTo[bag, {as[p], as[pnew]} -> p[[i]] p[[j]]/tot/(tot - 1)]
], {i, n}, {j, n}];
Normal[Total /@ GroupBy[bag, First -> Last]]
]
buildMarkovProcess[n_Integer?Positive] := Module[{ip, as, tm, lip},
ip = IntegerPartitions[n];
as = AssociationThread[ip, Range[lip = Length[ip]]];
tm = SparseArray[Flatten[computeProbabilities[#, as] & /@ ip], {lip, lip}];
DiscreteMarkovProcess[lip, tm]
]
El menor número de ciclos necesario para obtener todas las bolas que tienen el mismo color, es el primer paso de la distribución de tiempo para llegar a la partición de $\{n\}$, que tiene índice 1 en este código, y que es el estado de absorción de la cadena de Markov.
StepsToSameColorDistribution[n_Integer?Positive] :=
FirstPassageTimeDistribution[buildMarkovProcess[n], 1]
Ahora nos podemos preguntar por el número medio de pasos $K_n$ necesario para alcanzar el estado de absorción:
In[392]:= Table[{n, Mean[StepsToSameColorDistribution[n]]}, {n, 2, 12}]
Out[392]= {{2, 1}, {3, 4}, {4, 9}, {5, 16}, {6, 25}, {7, 36}, {8,
49}, {9, 64}, {10, 81}, {11, 100}, {12, 121}}
Que se ajusta al patrón de $\mathbb{E}(K_n) = (n-1)^2$:
In[392]:= FindSequenceFunction[%, n]
Out[392]= (-1 + n)^2
La interesante característica de la $K_n$ variable aleatoria es revelado por mirar a su probabilidad de generación de función:
Esto revela que el $K_n - (n-1)$ puede ser representada como una suma de $n-2$ independiente geométricas variables aleatorias con algunas específicas distintas probabilidades de fallo. Poniendo este código:
toTransformedDistribution[n_Integer] := Module[{pgf, den, z, ps, fgm, xvec},
fgm = FactorialMomentGeneratingFunction[StepsToSameColorDistribution[n], z];
pgf = Factor[fgm];
den = Denominator[pgf];
If[FreeQ[den, z],
TransformedDistribution[n - 1, Distributed[x, GeometricDistribution[1/2]]]
,
ps = Part[Rest[FactorList[den]], All, 1];
ps = Map[1 + Coefficient[#, z, 1]/Coefficient[#, z, 0] &, ps];
xvec = Array[x, n - 2];
TransformedDistribution[n - 1 + Total[xvec],
Distributed[xvec, ProductDistribution @@ Map[GeometricDistribution, ps]]]
]
]
Tenemos la comprobación de la coherencia:
In[424]:=
Table[FactorialMomentGeneratingFunction[toTransformedDistribution[n],
z] == FactorialMomentGeneratingFunction[
StepsToSameColorDistribution[n], z], {n, 2, 8}] // Simplify
Out[424]= {True, True, True, True, True, True, True}
Y ahora muestran la descomposición. $K_3 \stackrel{d}{=} 2 + X_1$ donde $X_1 \sim \mathrm{Geo}\left(\frac{1}{3}\right)$:
In[431]:= toTransformedDistribution[3]
Out[431]= TransformedDistribution[
2 + X1, Distributed[X1, GeometricDistribution[1/3]]
$K_4 \stackrel{d}{=} 3 + X_1 + X_2$ donde$X_1 \sim \mathrm{Geo}\left(\frac{1}{2}\right)$$X_2 \sim \mathrm{Geo}\left(\frac{1}{6}\right)$, e $X_1$ $X_2$ son independientes:
In[432]:= toTransformedDistribution[4]
Out[432]= TransformedDistribution[
3 + X1 + X2, {X1, X2} \[Distributed]
ProductDistribution[GeometricDistribution[1/2],
GeometricDistribution[1/6]]]
Asimismo,$K_5 = 4 + X_1 + X_2 + X_3$, donde $X_1 \sim \mathrm{Geo}\left(\frac{3}{5}\right)$, $X_2 \sim \mathrm{Geo}\left(\frac{3}{10}\right)$, $X_3 \sim \mathrm{Geo}\left(\frac{1}{10}\right)$, y $X_1$, $X_2$ y $X_3$ son independientes:
In[433]:= toTransformedDistribution[5]
Out[433]= TransformedDistribution[
4 + X1 + X2 + X3, {X1, X2, X3} \[Distributed]
ProductDistribution[GeometricDistribution[3/5],
GeometricDistribution[3/10], GeometricDistribution[1/10]]]
Por supuesto, si alguien puede ofrecer una idea de por qué una descomposición debe tener lugar, yo le quito el sombrero a la melodía de un bono.
Agregó
: Más experimental de matemáticas análisis revela un patrón de la distribución geométrica de los índices de fracaso en la descomposición de la $K_n$, específicamente $$ K_n \stackrel{\mathrm{ley}}{=} n - 1 + \sum_{i=1}^{n-2} X_i, \quad X_m \sim \mathrm{Geom}\left(\frac{m (m+1)}{n(n-1)}\right) \, \mathrm{ para } \,\, 1 \leqslant m \leqslant n-2 $$ Por lo tanto, denotando $p_i = i(i+1)/n/(n-1)$ $$\begin{eqnarray} \mathbb{E}\left(K_n\right) &=& n-1 + \sum_{i=1}^{n-2} \left(\frac{1-p_i}{p_i}\right) = n - 1 + \sum_{i=1}^{n-2} \left( \frac{n(n-1)}{i} - \frac{n(n-1)}{i+1} - 1 \right) \\ &\stackrel{\mathrm{telesc.}}{=}& (n-1) + \frac{n(n-1)}{1} - \frac{n(n-1)}{n-1} - (n-2) = 1 + n(n-1) - n \\ &=& \fbox{%#%#%} \end{eqnarray} $$
La pregunta queda abierta en cuanto a porqué $\left(n-1\right)^2$ puede ser descompuesto en la suma de independiente geométricas variables aleatorias?
