Una generalización del problema del coleccionista de cupones: tomar un par adyacente cada vez.

Question

Tenemos $n$ distintos tipos de cupones (de suministro ilimitado), las categorías son denotados $1\dots n$.Cada vez que podemos sacar de dos cupones, pero los dos deben estar adyacentes al tipo (que podría ser cualquiera de $\{(1,2),(2,3)...,(n-1,n),(n,1)\}$, la probabilidad de sacar cualquier par es igual). ¿Cuál es el número esperado de sorteos antes de recoger todos los $n$ distintos cupones?

Algunos avances: Esto es diferente que sólo dibujar dos cupones con reemplazo al azar, donde ya conozco una fórmula. Y el "patrón" de la selección no importa, esto significa que la elaboración $\{(1,3),(2,4)...,(n-1,1),(n,2)\}$ da el mismo resultado.

Answer 1

Aquí hay una fórmula. Por mi culpa, debería haberme dado cuenta de que este problema es equivalente al Proyecto Euler 645, que resolví anteriormente. $$E(n)=1-n\sum_{i=1}^{n-1}\frac{1}{i}\left((-1)^i\binom{n-1}{i}+\frac{\binom{n-i}{i}}{\binom{n-1}{i}}\right)$ $ Ahora estoy trabajando en el caso cuando un sorteo incluye más de 2 cupones.

Answer 2

(Después de la respuesta de @mayoi, este enfoque está superado, sin embargo, me estoy poniendo simplemente una Markovian enfoque).

Supongamos que, a su vez $t$, ha adquirido $m$ cupón de la $n$ disponible.
Supongamos también, por el momento, que el cupón adquirido en la sucesión de $\{1,2, \cdots,m \}$.

Ahora,
- si usted recibe cupones $(m,m+1)$ o $(n,1)$ que aumenta el monto recaudado;
- si usted recibe cupones $(m+1,m+2), \cdots (n-1,n)$ aumentar por dos la cantidad recogida;
- en cualquier otro caso de permanecer con la recogida de cantidad;

El caso 1 corresponde a $2$ de las extracciones, caso 2 a $n-m-1$ de las extracciones y el caso 3 se presenta el resto de $m-1$ extracciones de la total $n$.
Cuando $m=0$ tenemos $0,n,0$, mientras que si se $m=1$ (pero no puede ocurrir) tendríamos $2, n-2,0$, entonces cuando $m=n-1$ tenemos $[2,0,n-2]$ e de $n=m$ es $[0,0,n]$.

Debido a la simetría, es fácil deducir que el anterior recuento mantiene sea cual sea el tipo se la $m$ cupón recogidos.

Por lo tanto, la matriz de transición para el número de cupones de recogida, indexado $[0,n] \times [0,n]$, es $$ \eqalign{ & T_ {\m\,q} \quad \left| {\;0 \le m,q \le n} \right.\quad = \cr & = \left[ {0 = n} \right] + {{\left[ {1 \le n} \right]} \over n}\left( {\left( {m - \left[ {m < n} \right]} \right)\left[ {1 \le m} \right]\left[ {q = m} \right] + 2\left[ {1 \le m} \right]\left[ {q = m + 1} \right] + \left( {n - m - \left[ {1 \le m} \right]} \right)\left[ {q = m + 2} \right]} \right) \cr} $$

donde $[P]$ indica el soporte de Iverson $$ \left[ P \right] = \left\{ {\begin{array}{*{20}c} 1 & {P = TRUE} \\ 0 & {P = FALSE} \\ \end{array} } \right. $$

Por ejemplo, para $n=4,5$ las matrices son $$ \eqalign{ & {\bf T}_{\,4} = \left( {\matriz{ 0 & 0 & 1 & 0 & 0 \cr 0 & 0 & {1/2} & {1/2} & 0 \cr 0 & 0 & {1/4} & {1/2} & {1/4} \cr 0 & 0 & 0 & {1/2} & {1/2} \cr 0 & 0 & 0 & 0 & 1 \cr } } \right) \cr & {\bf T}_{\,5} = \left( {\matriz{ 0 & 0 & 1 & 0 & 0 & 0 \cr 0 & 0 & {2/5} & {3/5} & 0 & 0 \cr 0 & 0 & {1/5} & {2/5} & {2/5} & 0 \cr 0 & 0 & 0 & {2/5} & {2/5} & {1/5} \cr 0 & 0 & 0 & 0 & {3/5} & {2/5} \cr 0 & 0 & 0 & 0 & 0 & 1 \cr } } \right) \cr} $$

La matriz presenta una interesante simetría.
Sus autovalores sigue un trazado regular $\left\{ {{k \over h}\quad \left| {\;0 \le k \ne h - 1 \le h} \right.} \right\}$ (para $2 \le h$), con el valor null ser doble. La matriz es diagonalizable, y podemos aplicar la de Markov, teoría de obtener varios parámetros de interés.