Número máximo esperado de calcetines sin par

Question

Como todos los combinatoric problemas, este es probablemente equivalente a otro, bien conocido, pero no he logrado encontrar un equivalente problema (y OEIS no ayuda), por lo que ofrecen esta siendo posiblemente nuevos y posiblemente interesante.

Declaración del problema

He a$2N$ calcetines en la canasta de la ropa, y yo estoy colgando de ellos en las tuberías calientes para que se seque. Para hacer la vida más fácil, más adelante, quiero colgar en pares. Ya es de noche cuando los tubos son, adopto el siguiente algoritmo:

1. Tomar un calcetín al azar de la canasta.
2. Si coincide con uno que ya está en mi brazo, colgar tanto en las tuberías: el uno en mi mano y la coincidencia de una tomada de mi brazo.
3. Si no coincide con uno que ya está en mi brazo, colgarlo en mi brazo con el de los demás.
4. Hacer esto $2N$ veces.

La pregunta es: ¿Cuánto tiempo de mi brazo?

Claramente, la duración mínima es de $1$, por ejemplo si los calcetines vienen en el orden $AABBCC$. Con igual claridad, la longitud máxima es de $N$, por ejemplo si los calcetines salir como $ABCABC$. Pero, ¿qué es lo más probable longitud? O el promedio de longitud? O qué tipo de distribución de hacer las longitudes requeridas?

Resulta ser más fácil de parametrizar los resultados no por $2N$, el número de calcetines, pero por $2N-1$, que voy a llamar a $M$.

Los primeros resultados

(Notación: $n!!$ es el semifactorial, el factorial incluyendo sólo los números impares; lo $7!!=7\times 5\times 3\times 1$).

En cada caso, yo proporcionan la frecuencia para cada posible la longitud del brazo, comenzando con una longitud de 1. Yo uso de frecuencias en lugar de probabilidades, porque son más fáciles de escribir, pero usted puede obtener las probabilidades dividiendo por $M!!$.

$$ \begin{array}{c|rrrrr} M \\ \hline 1 & 1 \\ 3 & 1 & 2 \\ 5 & 1 & 8 & 6 \\ 7 & 1 & 30 & 50 & 24 \\ 9 & 1 & 148 & 340 & 336 & 120 \\ \end{array} $$ Sería bueno saber (por ejemplo) si estas frecuencias tienden a algún tipo de distribución conocida como $M\to\infty$, así como los coeficientes binomiales hacer.

Pero, como he dicho al principio, esto puede ser una re-codificación de un problema combinatorio, la realización de una gran cantidad de trabajado previamente los resultados junto con él. Pensé, por ejemplo, de las longitudes de los caminos aleatorios en $N$ dimensiones con sólo un paso hacia adelante y un paso atrás de ser permitidos en cada una de las dimensiones–, pero que se veía muy complicado dar ningún directa de la dirección a seguir.

Antecedentes: los métodos de

En caso de que sea interesante o útil, he obtenido los resultados anteriores por medio de una de dos dimensiones de generación de función, en la que el coeficiente de $y^n$ identificados de la longitud del brazo necesarios y el coeficiente de $x^n$ identificado cuántos calcetines habían sido recuperados en la [primera] el tiempo que esta longitud fue alcanzado. Llamar a la resultante de la generación de la función de $A_M(x,y)$, la recurrencia he utilizado:

$$A_M=MxyA_{M-2}+x^2(x-y)\frac\partial{\partial x}A_{M-2}+(1-x^2)xy$$

que se basa en el sonido de los primeros principios y coincide con los resultados de cálculo manual a $M=5$. Después de haber encontrado un polinomio, yo sustituto $x=1$ y los números en la tabla de arriba son entonces los coeficientes de las potencias de $y$.

Pero, matemáticas estar cerca de la comedia, toda esta elaboración puede ser innecesariamente complicados para llegar a un resultado demasiado trivial para ser encontrados incluso en OEIS. Es?

Answer 1

Hice un poco de Monte Carlo con este interesante problema y llegó a algunas conclusiones interesantes. Si usted tiene $N$ pares de calcetines la máxima longitud del brazo está ligeramente por encima de $N/2$.

Primero, hice 1.000.000 de experimentos con 100 pares de calcetines y de máxima registrada de la longitud del brazo alcanzado en cada uno de ellos. Por ejemplo, la máxima longitud del brazo de 54 fue alcanzado cerca de 90.000 veces. Y todo se ve como una distribución normal para mí. El valor medio de la máxima longitud del brazo fue 53.91, confirmó varias veces en una fila.

Nada cambió con 100 pares de calcetines y 10.000.000 de experimentos. Promedio de valor sigue siendo el mismo. Así que parece que necesita alrededor de un millón de pistas para elaborar una conclusión significativa.

Aquí es lo que me dieron cuando me duplicó el número de calcetines de 200 pares. La máxima longitud del brazo en promedio fue de 105.12, todavía por encima del 50%. Tengo el mismo valor en varios repetidos experimentos ($\pm0.01$).

Finalmente, me decidí a comprobar máximo esperado de la longitud del brazo para diferente número de calcetín de pares, de 10 a 250. Cada número de pares fue probado de 2.000.000 de veces antes de que el valor promedio fue calculado. Aquí están los resultados:

$$ \begin{array}{c|rr} \textbf{Pairs} & \textbf{Arm Length} & \textbf{Increment} \\ \hline 10 & 6.49 & \\ 20 & 12.03 & 5.54 \\ 30 & 17.41 & 5.38 \\ 40 & 22.71 & 5.30 \\ 50 & 27.97 & 5.26 \\ 60 & 33.20 & 5.23 \\ 70 & 38.40 & 5.20 \\ 80 & 43.59 & 5.19 \\ 90 & 48.75 & 5.16 \\ 100 & 53.91 & 5.16 \\ 110 & 59.07 & 5.16 \\ 120 & 64.20 & 5.13 \\ 130 & 69.33 & 5.13 \\ 140 & 74.46 & 5.13 \\ 150 & 79.58 & 5.12 \\ 160 & 84.69 & 5.11 \\ 170 & 89.80 & 5.11 \\ 180 & 94.91 & 5.11 \\ 190 & 100.02 & 5.11 \\ 200 & 105.11 & 5.09 \\ 210 & 110.20 & 5.09 \\ 220 & 115.29 & 5.09 \\ 230 & 120.38 & 5.09 \\ 240 & 125.47 & 5.09 \\ 250 & 130.56 & 5.09 \end{array} $$

It looks like a straight line but it's actually an arc, slightly bended downwards (take a look at the increment column).

Finally, here is the Java code that I used for my experiments.

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Basket {
    public static final int PAIRS = 250;
    public static final int NUM_EXPERIMENTS = 2_000_000;    

    int n;
    List<Integer> basket;
    Set<Integer> arm;

    public Basket(int n) {
        // basket size
        this.n = n;
        // socks are here
        this.basket = new ArrayList<Integer>();
        // arm is just a set of different socks
        this.arm = new HashSet<Integer>();
        // add a pair of same socks to the basket
        for(int i = 0; i < n; i++) {
            basket.add(i);
            basket.add(i);
        }
        // shuffle the basket
        Collections.shuffle(basket);
    }

    // returns maximum arm length
    int hangSocks() {
        // maximum arm length
        int maxArmLength = 0;
        // we have to hang all socks
        for(int i = 0; i < 2 * n; i++) {
            // take one sock from the basket
            int sock = basket.get(i);
            // if the sock of the same color is already on your arm...
            if(arm.contains(sock)) {
                // ...remove sock from your arm and put the pair over the hot pipe
                arm.remove(sock);
            }
            else {
                // put the sock on your arm
                arm.add(sock);
                // update maximum arm length
                maxArmLength = Math.max(maxArmLength, arm.size());
            }
        }
        return maxArmLength;
    }

    public static void main(String[] args) {
        // results of our experiments will be stored here
        int[] results = new int[PAIRS + 1];
        // run millions of experiments
        for(int i = 0; i < NUM_EXPERIMENTS; i++) {
            Basket b = new Basket(PAIRS);
            // arm length in a single experiment
            int length = b.hangSocks();
            // remember how often this result appeared
            results[length]++;
        }
        // print results in CSV format so that we can plot them in Excel
        for(int i = 0; i < results.length; i++) {
            System.out.println(i + "," + results[i]);
        }
        // find average arm length
        int sum = 0;
        for(int i = 0; i < results.length; i++) {
            sum += i * results[i];
        }
        double average = (double) sum / (double) NUM_EXPERIMENTS;
        System.out.println(String.format("Average arm length is %.2f", average)); 
    }

}

EDIT: For N=500, the average value of maximum arm length after 2,000,000 tests is 257.19. For N=1000, the result is 509.23.

It seems that for $N\to\infty$, the result goes down to $N/a 2$. No sé cómo probar esto.

Answer 2

El número esperado de una sola calcetines se maximiza cuando están a medio camino a través de. Cuando usted ha dibujado $N$ calcetines de la probabilidad de que un determinado par de divisas tiene uno en el brazo es $\frac {2N^2}{2N^2+2N(N-1)}=\frac{N^2}{2N^2-N}\approx \frac 12+\frac 1{2N}$. Si hacemos los calcetines distinguibles, para tener uno en su brazo calcetín $1$ de un par de ha $2N$ posiciones puede ser, entonces calcetín $2$ ha $N$ opciones de estar en la otra mitad de la carrera. Para no tener uno en su brazo calcetín $1$ nuevo ha $2N$ opciones, pero calcetín $2$ sólo ha $N-1$ como debe ser en la misma mitad de la carrera. Esto dice el número esperado en el brazo es $\frac {N^2}{2N-1}\approx \frac {N+1}2$.

El valor esperado está por debajo de la modalidad de Oldboy distribución de la que se dice que la distribución no es simétrica alrededor de la modalidad.

Tenga en cuenta que esto se refiere a la máxima esperada en un punto dado. La máxima prevista a través de una distribución puede ser mayor a lo Empy2 explica.

Answer 3

Los bits adicionales, por encima de $N/2$ en Oldboy de la tabla, están cerca de $\sqrt[3]{N}$. Tengo algunas ideas de por qué esto podría ser cierto.

En primer lugar, el número esperado de calcetines en el brazo, en el $N+x$th calcetín es $(N^2-x^2)/(2N-1)$.

Cerca de la $N$th calcetín, el número de calcetines en el brazo sigue un paseo aleatorio. Es simétrica en la $N$th calcetín, pero tiene un sesgo negativo de $x^2/2N$ a $N+x$th calcetín.
Alrededor de la $N+yN^{2/3}$th calcetín, una caminata aleatoria simétrica habría movido $O(\sqrt{yN^{2/3}})$, pero la tendencia negativa también es $O((yN^{2/3})^2/N)$, por lo tanto se $O(N^{1/3})$. El sesgo negativo que dominan grandes $y$, por lo que el valor máximo será en este dominio. La variación aleatoria domina para las pequeñas $y$.

Por lo que el máximo es probable que el ser $N/2+O(N^{1/3})$.

EDIT: la variación en el número de calcetines en el brazo, en el $N$th calcetín es $$\frac{2N^2(N-1)^2}{(2N-1)^2(2N-3)}\approx\frac N4$$ Por lo que el ancho de la curva de campana en Oldboy gráficos es de aproximadamente $\sqrt{N}$. Pero este efecto es simétrica por encima y por debajo de la media $N^2/(2N-1)$. El máximo de la caminata aleatoria no es simétrica, y desplaza la curva de la campana a la derecha, pero que el efecto de $(O(N^{1/3}))$ es menor que la variación de un cesto de la ropa para la próxima $(O(N^{1/2}))$