Número de distintas muestras bootstrap

Question

Para $n$ distintas observaciones, hay ${2n - 1 \choose n-1}$ distintos bootstrap (re)de las muestras.

Podría alguien por favor proporcione una explicación sencilla?

He encontrado http://statweb.stanford.edu/~susan/courses/s208/node11.html, que incluye lo siguiente:

El conjunto de todos bootstrap remuestrea es el $n$ dimensiones simplex $$C_n=\{(k_1,k_2,\ldots,k_n), \,k_i \in \mathbb{N}, \,\sum k_i=n\}$$

Aquí está el argumento que he utilizado en clase para explicar cómo de grande $C_n$ es. Cada componente del vector es considerado un cuadro, hay $n$ cajas para contener $n$ bolas en todos, queremos que contener para contar el número de maneras de separar las n bolas en la $n$ cajas. Anote $n-1$ separadores de $\vert$ para hacer cajas, y $n$ bolas, habrá $2n-1$ posiciones desde las que elegir la $n-1$ bares posiciones, para instancia de vector de arriba corresponde a: o||o|oo| . Así $$\displaystyle \vert C_n \vert={{2n-1}\choose{n-1}}$$

Esto tiene sentido para mí, con la excepción de un punto crucial: ¿por qué no ser "$2n - 1$ puestos a elegir el $n-1$ bares "posiciones"?

Traté de justificar a mí mismo y me encontré con esto:

Necesito encontrar un conjunto de tamaño $2n - 1$ de los posibles barra de ubicaciones. A primera vista hay $n+1$ lugares en los que las barras pueden ser colocados, pero el problema es que las posiciones pueden ser elegida varias veces.

Para ser claros, el uso o para representar una pelota como en el bloque de la cita de arriba: _o_o_o_o_o_ es decir, el 5 bolas significa 6 ranuras (guiones bajos) en el que las barras pueden vivir. Pero puede haber varios bares en una ubicación, por ejemplo, ||ooo||oo .

El conjunto que se me ocurrió es $$L = \left\{0, 1, \ldots, n, s_1, \ldots, s_{n-2}\right\}$$ which has size $2n - 1$ as desired. The first $n+el 1$ elements are integers; the last $n-2$ elements are symbols: $s_i$ means "go to the same slot as bar $i$."

Los elementos de L son posibles ubicaciones para las barras. La regla para la colocación de las barras es:

1. Dibuja un ejemplo de $\tilde{L}$ del tamaño de la $n-1$ $L$
2. Orden de los elementos de $\tilde{L}$, de modo que los enteros venir primero (en orden ascendente), seguido por las $s_i$, en orden ascendente de la $i$; tenga en cuenta que no es necesariamente al menos un entero en $\tilde{L}$
3. El $j^{th}$ elemento $\tilde{L}$ nos dirá dónde colocar la barra de $j$. Si $\tilde{L}_j$ es un número entero, en lugar de la barra de $j$ en el número de ranura $\tilde{L}_j$; si es un $s_i$, en lugar de la barra de $j$ en la misma ranura de la barra de $i$ (la clasificación garantiza $i < j$)

Mi pregunta es doble: ¿mi explicación de sentido? Incluso si lo hace, parece innecesariamente confusa y complicada. Puede usted pensar en algo limpio y simple?

Answer 1

Vamos a pedirle a la computadora para generar algunos pequeños ejemplos. (El idioma es R.)

Tome $n=5$. Comience colocando $n-1$ bares (representados) de forma aleatoria dentro de $n + n-1 = 2n-1$ lugares; es decir, mediante la selección de $n-1$ elemento subconjunto de $\{1,2,\ldots,2n-1\}$:

n <- 5
set.seed(17)
y <- rep(0, 2*n-1)
y[sample.int(2*n-1, n-1, replace=FALSE)] <- 1
names(y) <- c("_","|")[y+1]
print(y)

La salida es

_ | _ | | _ _ | _ 
0 1 0 1 1 0 0 1 0

El $n-1=4$ elementos seleccionados se muestran con barras. Entre ellos aparecen cinco cajas de tamaños 1, 1, 0, 2, y 1, respectivamente. Estos cargos pueden ser fácilmente calculada:

x <- tabulate(cumsum(c(1,y)))-1
names(x) <- 1:n
print(x)

La salida es

1 2 3 4 5 
1 1 0 2 1 

Esta tabulación significa que 1 "1" fue seleccionado, 1 "2", no "3", 2 "4"y 1 "5". (Para apreciar lo que pasó, inspeccionar el resultado intermedio:

cumsum(c(1,y))

  _ | _ | | _ _ | _ 
1 1 2 2 3 4 4 4 5 5 

Comienzo con un 1 (que corresponde a ninguno de los cuadros o de barras), la suma total se incrementa el valor cada vez que un bar se cruzó. Porque hay $n-1=4$ bares, el valor final es $1+(n-1)=n=5$. Por lo tanto todos los resultados posibles en $\{1,2,\ldots,n\}$ se denomina al menos una vez. El código contó el número de veces que cada uno de los resultados fue mencionado y que disminuye el conteo de uno.)

Podríamos igualmente bien escribir la misma información como una matriz de valores de la muestra mediante la replicación de cada valor (en la primera fila) el número de veces indicado (en la segunda fila):

print(z <- unlist(mapply(rep, 1:n, x)))

La salida es

[1] 1 2 4 4 5

Estos son los valores de la muestra, ordenados para su comodidad. Por último, se puede convertir de nuevo a casillas y bares:

unlist(sapply(tabulate(z), function(i) c(1,rep(0, i))))[-1]

Este comando crea un cuadro por cada elemento de la muestra y se pega un bar en frente de la primera casilla para cada nuevo elemento de procesado. Después de la eliminación de la inicial de la barra, el resultado es lo que hemos iniciado con (y).

Debido a que este código va en un círculo completo, de uno de los tres representaciones diferentes de una muestra dada de vuelta a sí mismo, se muestra que cualquiera de las representaciones pueden ser convertidos de forma exclusiva a cualquiera de las otras dos formas. Por lo tanto, todas las configuraciones de cada una de las tres formas de representación están en una correspondencia uno a uno. En particular, el número de posibles matrices z que el nombre de los miembros de la muestra explícitamente es el mismo que el número de maneras de crear y, que (por definición) es $\binom{2n-1}{n-1}$.