3.3: Barajar cartas

Barajar cartas

Gran parte de esta sección se basa en un artículo de Brad Mann, ²⁸ que es una exposición de un artículo de David Bayer y Persi Diaconis. ²⁹

Riffle Shuffles

Dada una baraja de\(n\) cartas, ¿cuántas veces debemos barajarla para que sea “aleatoria”? Por supuesto, la respuesta depende del método de barajado que se utilice y de lo que entendemos por “aleatorio”. Comenzaremos el estudio de esta pregunta considerando un modelo estándar para el barajado de riffle.

Comenzamos con una baraja de\(n\) cartas, que asumiremos están etiquetadas en orden creciente con los enteros de 1 a\(n\). Un barajado de riffle consiste en un corte de la cubierta en dos pilas y un intercalado de las dos pilas. Por ejemplo, si\(n = 6\), el orden inicial es\((1, 2, 3, 4, 5, 6)\), y puede ocurrir un corte entre las tarjetas 2 y 3. Esto da lugar a dos pilas, a saber\((1, 2)\) y\((3, 4, 5, 6)\). Estos están intercalados para formar un nuevo orden de la cubierta. Por ejemplo, estas dos pilas podrían formar el orden\((1, 3, 4, 2, 5, 6)\). Para discutir tales barajados, necesitamos asignar una distribución de probabilidad al conjunto de todos los barajados posibles. Hay varias formas razonables en las que esto se puede hacer. Daremos varias estrategias de asignación diferentes, y demostraremos que son equivalentes. (Esto no quiere decir que esta asignación sea la única razonable.) Primero, asignamos la probabilidad\(b(n, 1/2, k)\) binomial al evento de que el corte se produzca después de la carta\(k\) th. A continuación, asumimos que todos los intercalados posibles, dado un corte, son igualmente probables. Así, para completar la asignación de probabilidades, necesitamos determinar el número de posibles intercalaciones de dos pilas de cartas, con\(k\) y\(n-k\) cartas, respectivamente.

Comenzamos por escribir la segunda pila en una línea, con espacios entre cada par de cartas consecutivas, y con espacios al principio y al final (entonces hay\(n-k+1\) espacios). Elegimos, con reemplazo,\(k\) de estos espacios, y colocamos las cartas de la primera pila en los espacios elegidos. Esto se puede hacer en

\[ n \choose{k} \]

maneras. Por lo tanto, la probabilidad de un entrelazado dado debe ser

\[{1\over{ n\choose{k} }}.\]

A continuación, observamos que si el nuevo ordenamiento no es el ordenamiento de identidad, es el resultado de un par único de corte-entrelazado. Si el nuevo ordenamiento es la identidad, es el resultado de cualquiera de los pares\(n+1\) corte-entrelazado.

Definimos a en un orden para ser una subsecuencia máxima de números enteros consecutivos en orden creciente. Por ejemplo, en el orden\[(2, 3, 5, 1, 4, 7, 6)\ ,\] hay 4 secuencias ascendentes; son\((1)\),\((2, 3, 4)\),\((5, 6)\), y\((7)\). Es fácil ver que un ordenamiento es el resultado de un barajado de riffle aplicado al ordenamiento de identidad si y solo si no tiene más de dos secuencias ascendentes. (Si el orden tiene dos secuencias ascendentes, entonces estas secuencias ascendentes corresponden a las dos pilas inducidas por el corte, y si el orden tiene una secuencia ascendente, entonces es el orden de identidad). Así, el espacio muestral de ordenamientos obtenidos aplicando una mezcla de riffle al ordenamiento de identidad se describe naturalmente como el conjunto de todos los ordenamientos con como máximo dos secuencias ascendentes.

Ahora es fácil asignar una distribución de probabilidad a este espacio muestral. A cada orden con dos secuencias ascendentes se le asigna el valor

\[ \frac{b(n, 1/2, k)}{n \choose{k}} = \frac{1}{2^n},\]

y al ordenamiento de identidad se le asigna el valor

\[{n+1}\over{2^n} .\]

Hay otra manera de ver un riffle shuffle. Podemos imaginarnos comenzando con una baraja cortada en dos pilas como antes, con la misma asignación de probabilidades que antes, es decir, la distribución binomial. Una vez que tenemos las dos pilas, tomamos cartas, una por una, de la parte inferior de las dos pilas, y las colocamos en una pila. Si hay\(k_1\) y\(k_2\) cartas, respectivamente, en las dos pilas en algún momento de este proceso, entonces hacemos la suposición de que las probabilidades de que la siguiente carta a tomar provenga de una pila dada es proporcional al tamaño de pila actual. Esto implica que la probabilidad de que tomemos la siguiente carta de la primera pila es igual a

\[{k_1}\over{k_1 + k_2} ,\]

y la probabilidad correspondiente para la segunda pila es

\[{k_2}\over{k_1 + k_2} .\]

Ahora demostraremos que este proceso asigna la probabilidad uniforme a cada una de las posibles intercalaciones de las dos pilas.

Supongamos, por ejemplo, que se produjo un intercalado como resultado de elegir cartas de las dos pilas en algún orden. La probabilidad de que se produzca este resultado es producto de las probabilidades en cada punto del proceso, ya que se asume que la elección de la tarjeta en cada punto es independiente de las elecciones anteriores. Cada factor de este producto es de la forma

\[{k_i}\over{k_1 + k_2}} ,\]

donde\(i = 1\) o\(2\), y el denominador de cada factor es igual al número de cartas que quedan por elegir. Así, el denominador de la probabilidad es justo\(n!\). En el momento en que se elige una carta de una pila que tiene\(i\) cartas en ella, el numerador del factor correspondiente en la probabilidad es\(i\), y el número de cartas en esta pila disminuye en 1. Así, se ve que el numerador es\(k!(n-k)!\), ya que finalmente se eligen todas las cartas en ambas pilas. Por lo tanto, este proceso asigna la probabilidad\[ {1\over{ n\choose{k} } }\]

a cada intercalado posible.

Pasamos ahora a la pregunta de qué sucede cuando riffle\(s\) tiempos de barajado. Debe quedar claro que si comenzamos con el ordenamiento de identidad, obtenemos un ordenamiento con como máximo secuencias\(2^s\) ascendentes, ya que un barajado de riffle crea como máximo dos secuencias ascendentes de cada secuencia ascendente en el orden inicial. De hecho, no es difícil ver que cada uno de esos ordenamientos es el resultado de\(s\) riffle shuffles. La pregunta es, entonces, ¿de cuántas maneras puede producirse un ordenamiento con secuencias\(r\) ascendentes aplicando\(s\) riffle shuffles al ordenamiento identitario? Para responder a esta pregunta, nos dirigimos a la idea de un\(a\) -shuffle.

\(a\)-Baraja

Hay varias formas de visualizar un\(a\) -shuffle. Una forma es imaginar a una criatura con\(a\) manos a la que se le da una baraja de cartas para riffle shuffle. La criatura naturalmente corta la baraja en\(a\) pilas, y luego las rifa juntas. (¡Imagínate eso!) Así, el barajado de rifas ordinario es un barajado de 2. Como en el caso del 2-shuffle ordinario, permitimos que algunas de las pilas tengan 0 cartas. Otra forma de visualizar un\(a\) -shuffle es pensar en su inverso, llamado un\(a\) -unshuffle. Esta idea se describe en la prueba del siguiente teorema.

Ahora mostraremos que un\(a\) -shuffle seguido de un\(b\) -shuffle es equivalente a un\(ab\) -shuffle. Esto significa, en particular, que los barajados de\(s\) riffle en sucesión son equivalentes a uno\(2^s\) -shuffle. Esta equivalencia se hace precisa por el siguiente teorema.

[thm 3.3.1] Let\(a\) y\(b\) ser dos enteros positivos. \(S_{a,b}\)Sea el conjunto de todos los pares ordenados en el que la primera entrada es un\(a\) -shuffle y la segunda entrada es un\(b\) -shuffle. Que\(S_{ab}\) sea el conjunto de todos los\(ab\) -barajados. Después hay una correspondencia 1-1 entre\(S_{a,b}\) y\(S_{ab}\) con la siguiente propiedad. Supongamos que\((T_1, T_2)\) corresponde a\(T_3\). Si\(T_1\) se aplica al ordenamiento de identidad, y\(T_2\) se aplica al ordenamiento resultante, entonces el ordenamiento final es el mismo que el ordenamiento que se obtiene al aplicar\(T_3\) al ordenamiento de identidad. La manera más fácil de describir la correspondencia requerida es a través de la idea de unshuffle. Un\(a\) -unshuffle comienza con una baraja de\(n\) cartas. Una a una, las cartas se toman de la parte superior de la baraja y se colocan, con igual probabilidad, en la parte inferior de cualquiera de\(a\) las pilas, donde las pilas se etiquetan de 0 a\(a-1\). Después de que todas las cartas hayan sido distribuidas, combinamos las pilas para formar una pila colocando pila\(i\) en la parte superior de la pila\(i+1\), para\(0 \le i \le a-1\). Es fácil ver que si uno comienza con una baraja, hay exactamente una manera de cortar la baraja para obtener las\(a\) pilas generadas por la\(a\) -unshuffle, y con estas\(a\) pilas, hay exactamente una manera de intercalarlas para obtener la baraja en el orden en que estaba antes de la unshuffle se realizó. Así, este\(a\) -unshuffle corresponde a un\(a\) -shuffle único, y este\(a\) -shuffle es el inverso del\(a\) -unshuffle original.

Si aplicamos un\(ab\) -unshuffle\(U_3\) a una baraja, obtenemos un conjunto de\(ab\) pilas, que luego se combinan, en orden, para formar una pila. Etiquetamos estas pilas con pares ordenados de números enteros, donde la primera coordenada está entre 0 y\(a-1\), y la segunda coordenada está entre 0 y\(b-1\). Después etiquetamos cada carta con la etiqueta de su pila. El número de etiquetas posibles es\(ab\), según se requiera. Usando este etiquetado, podemos describir cómo encontrar un\(b\) -unshuffle y un\(a\) -unshuffle, de tal manera que si estos dos unshuffles se aplican en este orden a la baraja, obtenemos el mismo conjunto de\(ab\) pilas que se obtuvieron por el\(ab\) -unshuffle.

Para obtener el\(b\) -unshuffle\(U_2\), ordenamos la baraja en\(b\) pilas, con la pila\(i\) th conteniendo todas las cartas con segunda coordenada\(i\), para\(0 \le i \le b-1\). Entonces estas pilas se combinan para formar una pila. El\(a\) -unshuffle\(U_1\) procede de la misma manera, excepto que se utilizan las primeras coordenadas de las etiquetas. Las\(a\) pilas resultantes se combinan para formar una pila.

La descripción anterior muestra que las cartas que terminan en la parte superior son todas aquellas etiquetadas\((0, 0)\). A estas le siguen las etiquetadas\((0, 1),\ (0, 2),\)\(\ \ldots,\ (0, b - 1),\ (1, 0),\ (1,1),\ldots,\ (a-1, b-1)\). Además, el orden relativo de cualquier par de tarjetas con las mismas etiquetas nunca se altera. Pero esto es exactamente lo mismo que un\(ab\) -unshuffle, si, al inicio de tal unshuffle, etiquetamos cada una de las tarjetas con una de las etiquetas\((0, 0),\ (0, 1),\ \ldots,\ (0, b-1),\ (1, 0),\ (1,1),\ \ldots,\ (a-1, b-1)\). Esto completa la prueba.

En la Figura [fig 3.14], mostramos las etiquetas para un 2-unshuffle de una baraja con 10 cartas. Hay 4 cartas con la etiqueta 0 y 6 cartas con la etiqueta 1, así que si se realiza la 2-unshuffle, la primera pila tendrá 4 cartas y la segunda pila tendrá 6 cartas. Cuando se realiza esta unshuffle, la baraja termina en el orden de identidad.

En la Figura [fig 3.15], mostramos las etiquetas para un 4-unshuffle de la misma baraja (porque se están utilizando cuatro etiquetas). Esta cifra también puede considerarse como un ejemplo de un par de 2-unshuffles, como se describe en la prueba anterior. El primer 2-unshuffle utilizará la segunda coordenada de las etiquetas para determinar las pilas. En este caso, las dos pilas contienen las cartas cuyos valores son

\[\{5, 1, 6, 2, 7\} {\rm and} \{8, 9, 3, 4, 10\}.\]

Después de que se haya realizado esta 2-unshuffle, la baraja se encuentra en el orden mostrado en la Figura [fig 3.14], ya que el lector debe verificar. Si deseamos realizar un 4-unshuffle en la baraja, usando las etiquetas mostradas, ordenamos las cartas lexicográficamente, obteniendo las cuatro pilas

\[\{1, 2\},\ \{3, 4\},\ \{5, 6, 7\},\ {\rm and}\ \{8, 9, 10\}.\]

Cuando se combinan estas pilas, obtenemos una vez más el orden de identidad de la baraja. El punto del teorema anterior es que ambos procedimientos de clasificación conducen siempre al mismo ordenamiento inicial.

Teorema 3.3.2

Si\(D\) hay algún orden que sea el resultado de aplicar un\(a\) -shuffle y luego un\(b\) -shuffle al ordenamiento de identidad, entonces la probabilidad asignada\(D\) por este par de operaciones es la misma que la probabilidad asignada\(D\) por el proceso de aplicar un\(ab\) - barajar al ordenamiento de identidad. Llame al espacio de muestra de\(a\) -barajados\(S_a\). Si etiquetamos las pilas por los enteros de\(0\) a\(a-1\), entonces cada par de intercalado de corte, es decir, barajar, corresponde exactamente a un\(a\) entero base de un\(n\) dígito, donde el dígito\(i\) th en el entero es la pila de la que la carta\(i\) th es miembro. Por lo tanto, el número de pares de intercalado de corte es igual al número de\(a\) enteros de base\(n\) -dígito, que es\(a^n\). Por supuesto, no todos estos pares llevan a diferentes ordenamientos. El número de pares que conducen a un orden dado se discutirá más adelante. Para nuestros propósitos es suficiente señalar que son los pares corte-entrelazado los que determinan la asignación de probabilidad.

El teorema anterior muestra que hay una correspondencia 1-1 entre\(S_{a,b}\) y\(S_{ab}\). Además, los elementos correspondientes dan el mismo orden cuando se aplican al ordenamiento de identidad. Ante cualquier ordenamiento\(D\), deja\(m_1\) ser el número de elementos de los\(S_{a,b}\) cuales, cuando se aplican al ordenamiento de identidad, resultan en\(D\). \(m_2\)Sea el número de elementos de los\(S_{ab}\) cuales, cuando se aplican al ordenamiento de identidad, resultan en\(D\). El teorema anterior implica eso\(m_1 = m_2\). Por lo tanto, ambos conjuntos asignan la probabilidad

\[

ParseError: EOF expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/03:_Combinatoria/3.03:_Barajar_cartas), /content/body/div/div[2]/div/p[3]/span/span, line 1, column 4

\]

a\(D\). Esto completa la prueba.

Conexión con el problema del cumpleaños

Hay otro punto que se puede hacer respecto a las etiquetas dadas a las tarjetas por los sucesivos unshuffles. Supongamos que desbarajamos 2 una baraja de\(n\) cartas hasta que las etiquetas de las cartas sean todas diferentes. Es fácil ver que este proceso produce cada permutación con la misma probabilidad, es decir, se trata de un proceso aleatorio. Para ver esto, tenga en cuenta que si las etiquetas se vuelven distintas en el\(s\) th 2-unshuffle, entonces uno puede pensar en esta secuencia de 2-unshuffles como una\(2^s\) -unshuffle, en la que todas las pilas determinadas por la unshuffle tienen como máximo una carta en ellas (recuerde, las pilas corresponden a las etiquetas). Si cada pila tiene como máximo una carta en ella, luego se le dan dos cartas cualesquiera en la baraja, es igualmente probable que la primera carta tenga una etiqueta más baja o más alta que la segunda carta. Por lo tanto, cada orden posible es igualmente probable que resulte de esta\(2^s\) -unshuffle.

\(T\)Sea la variable aleatoria que cuenta el número de 2-unshuffles hasta que todas las etiquetas sean distintas. Se puede pensar en dar una medida de cuánto tiempo tarda en el proceso de desbarajado hasta que se alcanza la aleatoriedad.\(T\) Dado que el barajado y el unshuffling son procesos inversos,\(T\) también mide el número de barajados necesarios para lograr aleatoriedad. Supongamos que tenemos una baraja\(n\) -card, y pedimos\(P(T \le s)\). Esto es igual\(1 - P(T > s)\). Pero\(T > s\) si y sólo si es el caso que no todas las etiquetas después de\(s\) 2-unshuffles son distintas. Esto es solo el problema del cumpleaños; estamos pidiendo la probabilidad de que al menos dos personas tengan el mismo cumpleaños, dado que tenemos\(n\) gente y hay\(2^s\) posibles cumpleaños. Usando nuestra fórmula del Ejemplo [examen 3.3], encontramos que

\[P(T > s) = 1 - {2^s \choose n} \frac{n!}{2^{sn}}.\]

En Capítulo [chp 6], definiremos el valor promedio de una variable aleatoria. Usando esta idea, y la ecuación anterior, se puede calcular el valor promedio de la variable aleatoria\(T\) (ver Ejercicio [sec 6.1]. [exer 6.1.42]). Por ejemplo, si\(n = 52\), entonces el valor promedio de\(T\) es de aproximadamente 11.7. Esto significa que, en promedio, se necesitan alrededor de 12 barajados de riffle para que el proceso se considere aleatorio.

Corte-entrelazado de pares y pedidos

Como se señaló en la prueba del Teorema [thm 3.3.2], no todos los pares corte-entrelazado conducen a diferentes ordenamientos. Sin embargo, existe una fórmula fácil que da el número de tales pares que conducen a un orden dado.

[thm 3.3.3] Si un orden de longitud\(n\) tiene secuencias\(r\) ascendentes, entonces el número de pares de intercalado de corte bajo una\(a\) -barajación del orden de identidad que conducen al ordenamiento es

\[ { n + a - r \choose{n} }.\]

Para ver por qué esto es cierto, necesitamos contar el número de formas en que se puede realizar el corte en un\(a\) -shuffle lo que conducirá a un orden dado con secuencias\(r\) ascendentes. Podemos despreciar los intercalados, ya que una vez que se ha realizado un corte, a lo sumo un intercalado conducirá a un pedido dado. Dado que el orden dado tiene secuencias\(r\) ascendentes,\(r-1\) de los puntos de división en el corte se determinan. Los puntos de\(a - 1 - (r - 1) = a - r\) división restantes se pueden colocar en cualquier lugar. El número de lugares para poner estos puntos de división restantes es\(n+1\) (que es el número de espacios entre los pares consecutivos de cartas, incluyendo las posiciones al principio y al final de la baraja). Estos lugares se eligen con repetición permitida, por lo que el número de formas de tomar estas elecciones es

\[{n + a - r \choose{a-r}} = {n + a - r \choose{n}} .\]

En particular, esto significa que si\(D\) es un ordenamiento que es el resultado de aplicar un\(a\) -shuffle al ordenamiento de identidad, y si\(D\) tiene secuencias\(r\) ascendentes, entonces la probabilidad asignada\(D\) por este proceso es

\[{ {n + a - r\choose{n}} \over{a^n}}.\]

Esto completa la prueba.

El teorema anterior muestra que la información esencial sobre la probabilidad asignada a un ordenamiento bajo un\(a\) -shuffle es solo el número de secuencias ascendentes en el orden. Así, si determinamos el número de ordenamientos que contienen exactamente secuencias\(r\) ascendentes, para cada uno\(r\) entre 1 y\(n\), entonces habremos determinado la función de distribución de la variable aleatoria que consiste en aplicar un aleatorio\(a\) -shuffle al ordenamiento de identidad.

El número de ordenamientos de\(\{1, 2, \ldots, n\}\) con secuencias\(r\) ascendentes se denota por\(A(n, r)\), y se llama un número euleriano. Hay muchas maneras de calcular los valores de estos números; el siguiente teorema da un método recursivo que sigue inmediatamente de lo que ya sabemos sobre\(a\) -barajados.

[thm 3.3.4] Dejar\(a\) y\(n\) ser enteros positivos. Entonces

\[a^n = \sum_{r = 1}^a {n + a - r \choose{n} } A(n, r). \]

Por lo tanto,

\[A(n, a) = a^n - \sum_{r = 1}^{a-1} { n + a - r \choose{n} }A(n, r) \]

Además,

\[A(n, 1) = 1\]

La segunda ecuación puede ser utilizada para calcular los valores de los números eulerianos, y sigue inmediatamente de la Ecuación [eq 3.6]. La última ecuación es consecuencia del hecho de que el único ordenamiento de\(\{1, 2, \ldots, n\}\) con una secuencia ascendente es el ordenamiento de identidad. Así, queda por probar la Ecuación [eq 3.6]. Contaremos el conjunto de\(a\) -barajados de una baraja con\(n\) cartas de dos maneras. Primero, sabemos que existen\(a^n\) tales barajadas (esto se anotó en la prueba del Teorema [thm 3.3.2]). Pero hay\(A(n, r)\) ordenamientos de\(\{1, 2, \ldots, n\}\) con secuencias\(r\) ascendentes, y el Teorema [thm 3.3.3] establece que para cada uno de esos ordenamientos, hay exactamente

\[{ n+a-r \choose n}\]

corte-entrelazado pares que conducen al pedido. Por lo tanto, el lado derecho de la Ecuación [eq 3.6] cuenta el conjunto de\(a\) -barajados de una baraja de\(n\) cartas. Esto completa la prueba.

Ordenamientos Aleatorios y Procesos Aleatorios

Pasamos ahora a la segunda pregunta que se hizo al inicio de esta sección: ¿Qué entendemos por un ordenamiento “aleatorio”? Es algo engañoso pensar en un orden dado como aleatorio o no aleatorio. Si queremos elegir un orden aleatorio del conjunto de todos los ordenamientos de\(\{1, 2, \ldots, n\}\), queremos decir que queremos que cada orden sea elegido con la misma probabilidad, es decir, cualquier orden es tan “aleatorio” como cualquier otro.

La palabra “aleatorio” debería usarse realmente para describir un proceso. Diremos que un proceso que produce un objeto a partir de un conjunto (finito) de objetos es un proceso aleatorio si cada objeto del conjunto es producido con la misma probabilidad por el proceso. En la situación actual, los objetos son los ordenamientos, y el proceso que produce estos objetos es el proceso de barajar. Es fácil ver que ningún\(a\) -shuffle es realmente un proceso aleatorio, ya que si\(T_1\) y\(T_2\) son dos ordenamientos con un número diferente de secuencias ascendentes, entonces son producidos por un\(a\) -shuffle, aplicado al ordenamiento de identidad, con diferentes probabilidades.

Distancia de variación

En lugar de requerir que una secuencia de barajados produzca un proceso que sea aleatorio, definiremos una medida que describa qué tan lejos está un proceso dado de un proceso aleatorio. Dejar\(X\) ser cualquier proceso que produzca un orden de\(\{1, 2, \ldots, n\}\). Definir\(f_X(\pi)\) ser la probabilidad que\(X\) produce el orden\(\pi\). (Así,\(X\) puede pensarse como una variable aleatoria con función de distribución\(f\).) Dejar\(\Omega_n\) ser el conjunto de todos los ordenamientos de\(\{1, 2, \ldots, n\}\). Por último, dejemos\(u(\pi) = 1/|\Omega_n|\) para todos\(\pi \in \Omega_n\). La función\(u\) es la función de distribución de un proceso que produce ordenamientos y que es aleatorio. Para cada pedido\(\pi \in \Omega_n\), la cantidad\[|f_X(\pi) - u(\pi)|\] es la diferencia entre las probabilidades reales y deseadas que\(X\) produce\(\pi\). Si sumamos esto sobre todos los ordenamientos\(\pi\) y llamamos a esta suma\(S\), vemos que\(S = 0\) si y solo si\(X\) es aleatorio, y de lo contrario\(S\) es positivo. Es fácil demostrar que el valor máximo de\(S\) es 2, por lo que multiplicaremos la suma por\(1/2\) para que el valor caiga en el intervalo\([0, 1]\). Así, obtenemos la siguiente suma como fórmula para el entre los dos procesos:\[\parallel f_X - u \parallel = {1\over 2}\sum_{\pi \in \Omega_n} |f_X(\pi) - u(\pi)| .\]

Ahora aplicamos esta idea al caso de barajar. Dejamos\(X\) ser el proceso de\(s\) sucesivos barajados de riffle aplicados al ordenamiento identitario. Sabemos que también es posible pensar en él\(X\) como un solo\(2^s\) barajado. También sabemos que\(f_X\) es constante en el conjunto de todos los ordenamientos con secuencias\(r\) ascendentes, donde\(r\) está cualquier entero positivo. Por último, conocemos el valor de\(f_X\) en un orden con secuencias\(r\) ascendentes, y sabemos cuántos ordenamientos de este tipo hay. Así, en este caso concreto, tenemos

\[\parallel f_X - u \parallel = {1\over 2}\sum_{r=1}^n A(n, r) \biggl| {2^s + n - r\choose{n}}/2^{ns} - {1\over{n!}}\biggr| \]

Dado que esta suma solo tiene\(n\) summands, es fácil computar esto para valores de tamaño moderado de\(n\). Para\(n = 52\), obtenemos la lista de valores dada en la Tabla [tabla 3.12].

Distancia al proceso aleatorio.

1	1
2	1
3	1
4	0.99995334
5	0.9237329294
6	0.6135495966
7	0.3340609995
8	0.1671586419
9	0.0854201934
10	0.0429455489
11	0.0215023760
12	0.0107548935
13	0.0053779101
14	0.0026890130

Para ayudar a comprender estos datos, se muestran en forma gráfica en la Figura [fig 3.13]. El programa VariationList produce los datos mostrados tanto en la Tabla [tabla 3.12] como en la Figura [fig 3.13]. Se ve que hasta que se han producido 5 barajadas, la salida de\(X\) está muy lejos de ser aleatoria. Después de 5 barajados, la distancia desde el proceso aleatorio se reduce esencialmente a la mitad cada vez que ocurre una barajación.

Dadas las funciones de distribución\(f_X(\pi)\) y\(u(\pi)\) como arriba, hay otra manera de ver la distancia de variación\(\parallel f_X - u\parallel\). Dado cualquier evento\(T\) (que es un subconjunto de\(S_n\)), podemos calcular su probabilidad bajo el proceso\(X\) y bajo el proceso uniforme. Por ejemplo, podemos imaginar que\(T\) representa el conjunto de todas las permutaciones en las que al primer jugador de una partida de póquer de 7 jugadores se le reparte una línea recta (cinco cartas consecutivas en el mismo palo). Es interesante considerar cuánto difiere la probabilidad de este evento después de un cierto número de barajados de la probabilidad de este evento si todas las permutaciones son igualmente probables. Esta diferencia puede pensarse como una descripción de lo cerca que\(X\) está el proceso del proceso aleatorio con respecto al evento\(T\).

Consideremos ahora el evento de\(T\) tal manera que el valor absoluto de la diferencia entre estas dos probabilidades sea lo más grande posible. Se puede demostrar que este valor absoluto es la distancia de variación entre el proceso\(X\) y el proceso uniforme. (Se pide al lector que demuestre este hecho en Ejercicio [exer 3.3.4].)

Acabamos de ver que, para una baraja de 52 cartas, la distancia de variación entre el proceso aleatorio de 7 riffle y el proceso aleatorio es de aproximadamente\(.334\). Es de interés encontrar un evento\(T\) tal que se acerque la diferencia entre las probabilidades que producen\(T\) los dos procesos\(.334\). Un evento con esta propiedad se puede describir en términos del juego llamado New-Age Solitaire.

Solitario New-Age

Este juego fue inventado por Peter Doyle. Se juega con una baraja estándar de 52 cartas. Repartimos las cartas boca arriba, una a la vez, en una pila de descartes. Si se encuentra un as, digamos el as de Corazones, lo usamos para iniciar un montón de corazones. Cada pila de palos debe construirse en orden, del as al rey, usando solo cartas repartidas posteriormente. Una vez que hayamos repartido todas las cartas, recogemos la pila de descartes y continuamos. Definimos los trajes Yin como Corazones y Clubes, y los trajes Yang para ser Diamantes y Espadas. El juego termina cuando se han completado ambas pilas de traje Yin, o se han completado ambas pilas de traje Yang. Está claro que si el orden de la baraja es producido por el proceso aleatorio, entonces la probabilidad de que las pilas de traje Yin se completen primero es exactamente 1/2.

Ahora supongamos que compramos una nueva baraja de cartas, rompemos el sello del paquete y riffle barajemos la baraja 7 veces. Si uno intenta esto, uno encuentra que los trajes Yin ganan alrededor del 75% del tiempo. Esto es un 25% más de lo que obtendríamos si el mazo estuviera en un orden verdaderamente aleatorio. Esta desviación es razonablemente cercana al máximo teórico de\(33.4\)% obtenido anteriormente.

¿Por qué ganan tan a menudo los trajes Yin? En una baraja de cartas completamente nueva, los palos están en el siguiente orden, de arriba a abajo: as a través de rey de corazones, as a rey de palos, rey a través de as de diamantes y rey a través de as de picas. Tenga en cuenta que si las cartas no se barajaban en absoluto, entonces los montones de traje Yin se completarían en el primer pase, antes de que se vean las cartas del palo Yang. Si fuéramos a seguir jugando el juego hasta que se completen las pilas de traje Yang, se necesitarían 13 pases por la baraja para hacer esto. Así, se puede ver que en una nueva baraja, los trajes Yin están en el orden más ventajoso y los trajes Yang están en el orden menos ventajoso. Bajo 7 barajados de riffle, la ventaja relativa de los trajes Yin sobre los trajes Yang se conserva hasta cierto punto.

Ejercicio\(\PageIndex{1}\)

Dado cualquier orden\(\sigma\) de\(\{1, 2, \ldots, n\}\), podemos definir\(\sigma^{-1}\), el orden inverso de\(\sigma\), para ser el orden en el que el elemento\(i\) th es la posición ocupada por\(i\) in\(\sigma\). Por ejemplo, si\(\sigma = (1, 3, 5, 2, 4, 7, 6)\), entonces\(\sigma^{-1} = (1, 4, 2, 5, 3, 7, 6)\). (Si uno piensa en estos ordenamientos como permutaciones, entonces\(\sigma^{-1}\) es la inversa de\(\sigma\).)

A ocurre entre dos posiciones en un orden si la posición izquierda está ocupada por un número mayor que la posición derecha. Será conveniente decir que cada pedido tiene una caída después de la última posición. En el ejemplo anterior,\(\sigma^{-1}\) tiene cuatro caídas. Ocurren después de las posiciones segunda, cuarta, sexta y séptima. Demostrar que el número de secuencias ascendentes en un orden\(\sigma\) es igual al número de caídas en\(\sigma^{-1}\).

Contestar

Agrega el texto de respuesta aquí y automáticamente se ocultará si tienes una plantilla de “AutoNum” activa en la página.

Ejercicio\(\PageIndex{2}\)

Demostrar que si comenzamos con el orden de identidad de\(\{1, 2, \ldots, n\}\), entonces la probabilidad de que un\(a\) -shuffle lleve a un orden con secuencias exactamente\(r\) ascendentes es igual a\[

ParseError: EOF expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/03:_Combinatoria/3.03:_Barajar_cartas), /content/body/div/div[7]/div[2]/p[2]/span[4]/span, line 1, column 10

A(n, r) ,\] para\(1 \le r \le a\).

Contestar

Agrega el texto de respuesta aquí y automáticamente se ocultará si tienes una plantilla de “AutoNum” activa en la página.

Ejercicio\(\PageIndex{3}\)

Deja\(D\) ser una baraja de\(n\) cartas. Hemos visto que hay\(a^n\)\(a\) -barajados de\(D\). Se dio una codificación del conjunto de\(a\) -unshuffles en la prueba del Teorema [thm 3.3.1]. Ahora daremos una codificación de los\(a\) -barajados que corresponde a la codificación de los\(a\) -unshuffles. Dejar\(S\) ser el conjunto de todos\(n\) -tuplas de enteros, cada uno entre 0 y\(a-1\). Dejar\(M = (m_1, m_2, \ldots, m_n)\) ser cualquier elemento de\(S\). \(n_i\)Sea el número de\(i\)'s en\(M\), para\(0 \le i \le a-1\). Supongamos que comenzamos con la baraja en orden creciente (es decir, las cartas están numeradas del 1 al\(n\)). Etiquetamos las primeras\(n_0\) cartas con un 0, las siguientes\(n_1\) cartas con un 1, etc. luego el\(a\) -barajado correspondiente a\(M\) es el barajado que da como resultado el orden en el que las cartas etiquetadas se\(i\) colocan en las posiciones en\(M\) contener la etiqueta\(i\) . Las tarjetas con la misma etiqueta se colocan en estas posiciones en orden creciente de sus números. Por ejemplo, si\(n = 6\) y\(a = 3\), vamos\(M = (1, 0, 2, 2, 0, 2)\). Entonces\(n_0 = 2,\ n_1 = 1,\) y\(n_2 = 3\). Así que etiquetamos las tarjetas 1 y 2 con un 0, la tarjeta 3 con un 1 y las tarjetas 4, 5 y 6 con un 2. Luego las cartas 1 y 2 se colocan en las posiciones 2 y 5, la tarjeta 3 se coloca en la posición 1, y las cartas 4, 5 y 6 se colocan en las posiciones 3, 4 y 6, dando como resultado el pedido\((3, 1, 4, 5, 2, 6)\).

1. Usando esta codificación, mostrar que la probabilidad de que en un\(a\) -shuffle, la primera carta (es decir, la carta número 1) se mueva a la posición\(i\) th, viene dada por la siguiente expresión:\[
   ParseError: EOF expected (click for details)

   Callstack:
       at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/03:_Combinatoria/3.03:_Barajar_cartas), /content/body/div/div[7]/div[3]/ol/li[1]/span[3]/span, line 1, column 6
   

   .\]

2. Da una estimación precisa de la probabilidad de que en tres barajas de riffle de un mazo de 52 cartas, la primera carta termine en una de las primeras 26 posiciones. Usando una computadora, estime con precisión la probabilidad del mismo evento después de siete barajadas de riffle.

Contestar

Agrega el texto de respuesta aquí y automáticamente se ocultará si tienes una plantilla de “AutoNum” activa en la página.

Ejercicio\(\PageIndex{4}\)

Dejar\(X\) denotar un proceso particular que produce elementos de\(S_n\), y dejar\(U\) denotar el proceso uniforme. Que las funciones de distribución de estos procesos sean denotadas por\(f_X\) y\(u\), respectivamente. Mostrar que la distancia de variación\(\parallel f_X - u\parallel\) es igual a\[\max_{T \subset S_n} \sum_{\pi \in T} \Bigl(f_X(\pi) - u(\pi)\Bigr).\]

: Escribir las permutaciones\(S_n\) en orden decreciente de la diferencia\(f_X(\pi) - u(\pi)\).

Contestar

Agrega el texto de respuesta aquí y automáticamente se ocultará si tienes una plantilla de “AutoNum” activa en la página.

Ejercicio\(\PageIndex{5}\)

aConsiderar el proceso descrito en el texto en el que una baraja\(n\) -card es etiquetada repetidamente y 2-unshuffled, de la manera descrita en la prueba del Teorema [thm 3.3.1]. (Ver Figuras [fig. 3.12] y [fig 3.13].) El proceso continúa hasta que las etiquetas son todas diferentes. Demostrar que el proceso nunca termina hasta que se hayan hecho al menos\(\lceil \log_2(n) \rceil\) unshuffles.

Contestar

Agrega el texto de respuesta aquí y automáticamente se ocultará si tienes una plantilla de “AutoNum” activa en la página.