Esperar cola y longitud de la cabeza de $\rho$ para una función aleatoria finita

Question

Deje $F: D \rightarrow D$ ser un azar de la función en el dominio finito $D$ del tamaño de la $n$. Es bien sabido que, desde cualquier $x \in D$, iterando $F$ $x$ traza una secuencia de valores de $x, F(x), F(F(x)), \ldots$, que finalmente han de repetir (ya $D$ es finito) y se asemeja a un griego "$\rho$". El espera que el número total de elementos en esta $\rho$ $\sqrt{n\pi/2}$ con la mitad de la cola y la mitad en la cabeza. He visto este declaró en varios lugares, pero no puede encontrar una prueba.

Ilustración: con el fin De aclarar lo que estoy haciendo (ya que los comentarios de dejar claro que esto podría ser útil), fijar un número entero $n$. Uniforme de la muestra $a_0 \in [1,n]$ y hacer un vértice con la etiqueta $a_0$. Hacer esto de nuevo, la obtención de un vértice etiquetados $a_1$ y hacer un borde dirigido de $a_0$ $a_1$(esto no excluye $a_0 = a_1$). El pigeon-hole principio nos dice que con el tiempo vamos a crear un ciclo en este dígrafo; damos por terminado el proceso cuando este se produce. Claramente el gráfico se verá como en la carta de $\rho$: la "cola" es la parte de la gráfica antes de entrar en el ciclo de la cola puede tener longitud cero, por supuesto), y la "cabeza" es la parte de la gráfica que componen el ciclo.

Mi pregunta es esta: ¿cuál es la duración esperada de la cola y la cabeza, en términos de $n$. Asintóticamente, la respuesta es conocido por ser $\sqrt{n\pi/8}$, pero no puedo encontrar una derivación.

Answer 1

Yo también estoy muy interesado en la respuesta a su pregunta, así que escribí una rápida simulación en Python para "experimentalmente" llegar a algunos de estos valores. La secuencia de comandos se ejecuta cada 100.000 simulaciones para $n=|D|\in\{1,\ldots,100\}$ y calcula el promedio de la longitud de la cola, longitud del bucle, y la longitud total, para cada una de las $n$. Aquí está el código:

from math import pi, sqrt
from texttable import Texttable
from random import randint

NUM_TRIALS = 100000
MAX_N = 100

def rand_map(n):
  return [randint(0, n - 1) for x in range(n)]

def iterate_map(m):
  k = m[0]
  seen = []
  while k not in seen:
    seen.append(k)
    k = m[k]
  tail = seen[0:seen.index(k)]
  loop = seen[seen.index(k):]
  return [tail, loop]

table = Texttable()
table.add_row(["n", "tail(n)", "loop(n)", "rho(n)", "sqrt(pi*n/2)"])
for n in range(1, MAX_N + 1):
  avg_tail = 0
  avg_loop = 0
  avg_rho  = 0
  for it in range(NUM_TRIALS):
    rho = iterate_map(rand_map(n))
    avg_tail = avg_tail + 1 + len(rho[0])
    avg_loop = avg_loop + len(rho[1])
    avg_rho  = avg_rho  + 1 + len(rho[0]) + len(rho[1])
  table.add_row([n,
      avg_tail/float(NUM_TRIALS),
      avg_loop/float(NUM_TRIALS),
      avg_rho/float(NUM_TRIALS),
      sqrt(pi * n / 2.0)])
  print "Done row %d" % n

print table.draw()

Y aquí está el resultado (I truncada un montón de filas en el medio para el bien de la brevedad; sólo se ejecuta a sí mismo si usted quiere decir todo):

+-----+---------+---------+----------+---------------+
| n   | tail(n) | loop(n) | rho(n)   | sqrt(pi*n/2)  |
+-----+---------+---------+----------+---------------+
| 1   | 1.0     | 1.0     | 2.0      | 1.25331413732 |
+-----+---------+---------+----------+---------------+
| 2   | 1.0     | 1.24856 | 2.24856  | 1.77245385091 |
+-----+---------+---------+----------+---------------+
| 3   | 1.0739  | 1.44635 | 2.52025  | 2.17080376367 |
+-----+---------+---------+----------+---------------+
| 4   | 1.16473 | 1.61136 | 2.77609  | 2.50662827463 |
+-----+---------+---------+----------+---------------+
| 5   | 1.25775 | 1.75732 | 3.01507  | 2.8024956082  |
+-----+---------+---------+----------+---------------+
| 6   | 1.34817 | 1.87995 | 3.22812  | 3.06998012384 |
+-----+---------+---------+----------+---------------+
| 7   | 1.44218 | 2.00315 | 3.44533  | 3.31595752198 |
+-----+---------+---------+----------+---------------+
| 8   | 1.52348 | 2.13125 | 3.65473  | 3.54490770181 |
+-----+---------+---------+----------+---------------+
| 9   | 1.61659 | 2.23206 | 3.84865  | 3.75994241195 |
+-----+---------+---------+----------+---------------+
| 10  | 1.70321 | 2.32671 | 4.02992  | 3.96332729761 |
+-----+---------+---------+----------+---------------+
|  .       .         .          .            .       |
|  .       .         .          .            .       |
|  .       .         .          .            .       |
+-----+---------+---------+----------+---------------+
| 90  | 5.40747 | 6.28115 | 11.68862 | 11.8899818928 |
+-----+---------+---------+----------+---------------+
| 91  | 5.41534 | 6.32827 | 11.74361 | 11.9558548728 |
+-----+---------+---------+----------+---------------+
| 92  | 5.46854 | 6.32997 | 11.79851 | 12.0213668967 |
+-----+---------+---------+----------+---------------+
| 93  | 5.5118  | 6.36461 | 11.87641 | 12.0865238341 |
+-----+---------+---------+----------+---------------+
| 94  | 5.52473 | 6.41426 | 11.93899 | 12.151331397  |
+-----+---------+---------+----------+---------------+
| 95  | 5.55828 | 6.46288 | 12.02116 | 12.2157951459 |
+-----+---------+---------+----------+---------------+
| 96  | 5.58111 | 6.49214 | 12.07325 | 12.2799204954 |
+-----+---------+---------+----------+---------------+
| 97  | 5.66136 | 6.50754 | 12.1689  | 12.3437127194 |
+-----+---------+---------+----------+---------------+
| 98  | 5.66465 | 6.54559 | 12.21024 | 12.4071769563 |
+-----+---------+---------+----------+---------------+
| 99  | 5.6971  | 6.58051 | 12.27761 | 12.4703182138 |
+-----+---------+---------+----------+---------------+
| 100 | 5.734   | 6.5971  | 12.3311  | 12.5331413732 |
+-----+---------+---------+----------+---------------+

Podemos ver que el $\sqrt{\frac{\pi n}{2}}$ aproximación es bastante buena. Yo no veo ninguna obvia relación entre el tamaño de la cola y el bucle; en el punto de $n=100$ difieren casi exactamente por 1, pero viendo su progresión, esto parece ser sólo una coincidencia; la cola crece ligeramente más lento que el bucle todo el tiempo.

Estos números son poco probable que sea una respuesta satisfactoria a su pregunta, pero podría ser un punto de partida útil para alguien que sabe más matemáticas de lo que tengo que hacer para obtener algunos intuición sobre el problema.

Answer 2

Bien, he pasado algún tiempo en esto y tengo (una especie de) lo tengo resuelto.

Esta pregunta tiene sus raíces en el "problema del cumpleaños" donde nos preguntamos cómo muchas personas a las que debemos tener en un grupo antes de que la probabilidad de que al menos dos comparten un cumpleaños supera $1/2$. La respuesta es de 23. (Esto suponiendo que los cumpleaños son uniformes, que no lo son. La falta de uniformidad en sólo reduce el número de personas necesarias.)

Con un poco de pensamiento, podemos ver que la longitud de la $\rho$, tal como solicitó anterior es equivalente a un cumpleaños-como pregunta: ¿cuántos puntos aleatorios hacer que necesitamos antes de repetir. Podemos preguntar esto en un par de diferentes formas: lo $t \in [1,n]$ ¿ que necesitamos antes de exceder la probabilidad de $p$, lo que se espera que el número de puntos necesarios para ver un choque, etc.

Vamos a centrarnos en la pregunta: la expectativa. La probabilidad de que no hay ninguna colisión después de $t$ ensayos es claramente $$\frac{n}{n} \frac{n-1}{n} \frac{n-2}{n} \cdots \frac{n-t+1}{n} $$

Ahora vamos a $X$ ser la R. V. para el número de ensayos hasta que repetir por primera vez. Entonces la probabilidad de arriba es $\Pr[X > t]$ $E[X]$ es $$ \sum_{t \geq 0} \frac{n}{n} \frac{n-1}{n} \frac{n-2}{n} \cdots \frac{n-t+1}{n} $$ (Estoy usando una formulación alternativa de la expectativa de aquí).

Esto es todo bien y bueno, excepto uno no consigue un muy buen sentido de la respuesta de la suma. Como se mencionó anteriormente, este es reclamado para ser acerca de $\sqrt{n\pi/2}$, pero ¿cómo?

Resulta que una suma similar a la anterior fue estudiado por Ramanujan hace casi 100 años; la llamó el Q-Función.

$$ Q(n) = \sum_{1 \leq t \leq n} \frac{n!}{(n-t)!n^t} $$

Puesto que el P-Función comienza en 1 y la suma se inicia en 0, nuestra suma es $1 + Q(n)$. Análisis asintótico muestra que

$$ Q(n) \sim \sqrt{\frac{n \pi}{2}} + \frac{2}{3} $$

La derivación he encontrado para esto es en "Análisis de Algoritmos", R. Sedgewick y P. Flajolet, Addison-Wesley, 1996. Es bastante complicado. Curiosamente, el $\sqrt{\frac{n \pi}{2}}$ término proviene de la evaluación de la famosa integral sobre $e^{-x^2/2}$.

Para responder a la pregunta final: ¿cuál es la longitud de la cola y la cabeza? Cuando en la repetición se produce, es uniformemente probabilidades de chocar con cualquier punto de que ya ha establecido. (Imaginar el agitar de manos ahora) por lo tanto, en promedio, se va a la tierra en el centro, poner la mitad de la $\sqrt{\frac{n \pi}{2}}$ elementos en la cola y la otra mitad en la cabeza. Por lo tanto, la duración esperada de la cabeza y la cola es $\sqrt{\frac{n \pi}{8}}.$