Oczekiwany powrót endomapy

Question

Nieprecyzyjne sformułowanie pytania

Otrzymujesz bardzo dużą dodatnią liczbę całkowitą $n$ i zestaw $X$ z $n$elementy. Wybierasz losowo mapę$f:X\to X$i otrzymujesz $1/n$ dolara za każdy element $X$ uderzasz $f$ (to znaczy dla każdego elementu $y\in X$ który ma postać $f(x)$).

Jaki jest w przybliżeniu Twój oczekiwany zwrot?

Precyzyjne sformułowanie pytania

Pozwolić $n$ być dodatnią liczbą całkowitą i $X$ zestaw z $n$elementy. Zestaw$$ a_n:=n^{-n-1}\sum_{f:X\to X}|f(X)|, $$ gdzie suma obejmuje wszystkie mapy $f:X\to X$, i $|f(X)|$ to liczba elementów obrazu $f(X)$ z $X$. Definiuje sekwencję liczb wymiernych w przedziale$(0,1)$.

Czy limit $$\lim_{n\to+\infty}a_n$$istnieć? Jeśli tak, jaka jest jego wartość?

Kilka uwag

Pytanie to można wyrazić za pomocą liczb Stirlinga drugiego rodzaju w następujący sposób.

Niech znowu $X$ być naszym zestawem z $n$ elementy i niech $k$ być liczbą całkowitą z $1\le k\le n$.

Aby wybrać mapę $f:X\to X$ z $|f(X)|=k$, możemy najpierw wybrać podzbiór $f(X)$ wielkościowy $k$ z $X$, a następnie wybierz surjection $X\to f(X)$, $x\mapsto f(x)$.

Tam są $\binom{n}{k}$ opcje pierwszego wyboru i $k!\genfrac\{\}{0pt}{2}{n}{k}$ po drugie, gdzie $\genfrac\{\}{0pt}{2}{n}{k}$ to numery Stirlinga drugiego rodzaju przypisane parze $(n,k)$, więc są $$ k!\ \binom nk\ \begin{Bmatrix}n\\ k\end{Bmatrix}=\frac{n!}{(n-k)!}\ \begin{Bmatrix}n\\ k\end{Bmatrix} $$ mapy $f:X\to X$ z $|f(X)|=k$i otrzymujemy $$ a_n:=\frac{n!}{n^{n+1}}\sum_{k=1}^n\ \frac k{(n-k)!}\ \begin{Bmatrix}n\\ k\end{Bmatrix}. $$ Liczby $a_2,a_3,\ldots,a_7$ są w przybliżeniu równe $$ 0.75,\ 0.7037037037,\ 0.68359375,\ 0.67232,\ 0.66510202332,\ 0.660083. $$Użyłem WolframAlpha do ich obliczenia, jak w tym linku .

Oczywistym przypuszczeniem jest, że mamy $a_n\ge\frac12$ dla wszystkich $n\ge1$i że sekwencja maleje. Oznaczałoby to istnienie granicy. Nieco mniej oczywistym przypuszczeniem jest, że limit jest$\frac12$.

Answer 1

Uderzasz w dany element $X$ z prawdopodobieństwem $$a_n=1-\left(\frac{n-1}{n}\right)^n.$$ Oczekiwany rozmiar obrazu wynosi zatem $na_n$ a oczekiwana wygrana to $a_n$. To po prostu liniowość oczekiwań.

W związku z tym $$\lim_{n\to\infty}a_n=1-e^{-1}.$$

Możemy uzyskać asymptotyczną ekspansję: $$n\ln\frac{n-1}n=-1-\frac1{2n}-\frac1{3n^2}+O(n^{-3})$$ po to aby $$\left(\frac{n-1}n\right)^n=e\exp\left(-\frac1{2n}-\frac1{3n^2}+O(n^{-3})\right) =e\left(1-\frac1{2n}-\frac{5}{24n^2}+O(n^{-3})\right)$$ po to aby $$a_n=1-e+\frac{e}{2n}+\frac{5e}{24n^2}+O(n^{-3}).$$