Hasil yang diharapkan dari peta endom

Question

Pernyataan pertanyaan yang tidak tepat

Anda diberi bilangan bulat positif yang sangat besar $n$ dan satu set $X$ dengan $n$elemen. Anda memilih peta secara acak$f:X\to X$, dan Anda mendapatkan $1/n$ dolar untuk setiap elemen $X$ Anda memukul dengan $f$ (yaitu, untuk setiap elemen $y\in X$ yang merupakan bentuk $f(x)$).

Berapa, kira-kira, hasil yang Anda harapkan?

Pernyataan pertanyaan yang tepat

Membiarkan $n$ menjadi bilangan bulat positif dan $X$ satu set dengan $n$elemen. Set$$ a_n:=n^{-n-1}\sum_{f:X\to X}|f(X)|, $$ di mana jumlahnya mengalir di semua peta $f:X\to X$, dan $|f(X)|$ adalah jumlah elemen pada gambar $f(X)$ dari $X$. Ini mendefinisikan urutan bilangan rasional dalam interval$(0,1)$.

Apakah batasnya $$\lim_{n\to+\infty}a_n$$ada? Jika ya, berapa nilainya?

Beberapa observasi

Pertanyaan tersebut dapat diekspresikan dalam bentuk bilangan Stirling jenis kedua sebagai berikut.

Biarkan lagi $X$ menjadi set kami dengan $n$ elemen, dan biarkan $k$ menjadi integer dengan $1\le k\le n$.

Untuk memilih peta $f:X\to X$ dengan $|f(X)|=k$, pertama-tama kami dapat memilih subset $f(X)$ ukuran $k$ dari $X$, lalu pilih perkiraan $X\to f(X)$, $x\mapsto f(x)$.

Ada $\binom{n}{k}$ pilihan untuk pilihan pertama, dan $k!\genfrac\{\}{0pt}{2}{n}{k}$ untuk yang kedua, dimana $\genfrac\{\}{0pt}{2}{n}{k}$ adalah nomor Stirling dari jenis kedua yang melekat pada pasangan $(n,k)$, agar ada $$ k!\ \binom nk\ \begin{Bmatrix}n\\ k\end{Bmatrix}=\frac{n!}{(n-k)!}\ \begin{Bmatrix}n\\ k\end{Bmatrix} $$ peta $f:X\to X$ dengan $|f(X)|=k$, dan kami mendapatkan $$ a_n:=\frac{n!}{n^{n+1}}\sum_{k=1}^n\ \frac k{(n-k)!}\ \begin{Bmatrix}n\\ k\end{Bmatrix}. $$ Angka-angka $a_2,a_3,\ldots,a_7$ kira-kira sama dengan $$ 0.75,\ 0.7037037037,\ 0.68359375,\ 0.67232,\ 0.66510202332,\ 0.660083. $$Saya menggunakan WolframAlpha untuk menghitungnya, seperti di tautan ini .

Tebakan yang jelas adalah yang kita miliki $a_n\ge\frac12$ untuk semua $n\ge1$, dan urutannya menurun. Ini akan menyiratkan adanya batasan. Tebakan yang sedikit kurang jelas adalah bahwa batasnya adalah$\frac12$.

Answer 1

Anda mencapai elemen tertentu di $X$ dengan kemungkinan $$a_n=1-\left(\frac{n-1}{n}\right)^n.$$ Dengan demikian, ukuran gambar yang diharapkan $na_n$ dan kemenangan yang diharapkan adalah $a_n$. Ini hanya linearitas dari ekspektasi.

Karena itu $$\lim_{n\to\infty}a_n=1-e^{-1}.$$

Kita bisa mendapatkan ekspansi asimtotik: $$n\ln\frac{n-1}n=-1-\frac1{2n}-\frac1{3n^2}+O(n^{-3})$$ yang seperti itu $$\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)$$ yang seperti itu $$a_n=1-e+\frac{e}{2n}+\frac{5e}{24n^2}+O(n^{-3}).$$