엔도 맵의 예상 수익

Aug 20 2020

질문에 대한 부정확 한 설명

매우 큰 양의 정수가 제공됩니다. $n$ 그리고 세트 $X$$n$집단. 무작위로지도를 선택합니다.$f:X\to X$, 그리고 당신은 $1/n$ 각 요소에 대한 달러 $X$ 당신은 $f$ (즉, 각 요소에 대해 $y\in X$ 형태의 $f(x)$).

대략적인 예상 수익은 얼마입니까?

질문에 대한 정확한 설명

허락하다 $n$ 양의 정수이고 $X$ 세트 $n$집단. 세트$$ a_n:=n^{-n-1}\sum_{f:X\to X}|f(X)|, $$ 합계가 모든지도에 걸쳐있는 곳 $f:X\to X$, 및 $|f(X)|$ 이미지의 요소 수입니다. $f(X)$$X$. 이것은 간격에서 일련의 유리수를 정의합니다.$(0,1)$.

한계를 $$\lim_{n\to+\infty}a_n$$있다? 그렇다면 그 가치는 무엇입니까?

일부 관찰

질문은 다음과 같이 두 번째 종류의 스털링 수로 표현할 수 있습니다.

다시 보자 $X$ 우리 세트가 되십시오 $n$ 요소, 그리고하자 $k$ 정수이다 $1\le k\le n$.

지도를 선택하려면 $f:X\to X$$|f(X)|=k$, 먼저 하위 집합을 선택할 수 있습니다. $f(X)$ 크기 $k$$X$을 선택한 다음 추측을 선택하십시오. $X\to f(X)$, $x\mapsto f(x)$.

있습니다 $\binom{n}{k}$ 첫 번째 선택에 대한 옵션 및 $k!\genfrac\{\}{0pt}{2}{n}{k}$ 두 번째로, 여기서 $\genfrac\{\}{0pt}{2}{n}{k}$ 부부에게 붙은 두 번째 종류의 스털링 번호입니다 $(n,k)$, 그래서 $$ k!\ \binom nk\ \begin{Bmatrix}n\\ k\end{Bmatrix}=\frac{n!}{(n-k)!}\ \begin{Bmatrix}n\\ k\end{Bmatrix} $$ 지도 $f:X\to X$$|f(X)|=k$, 그리고 우리는 $$ a_n:=\frac{n!}{n^{n+1}}\sum_{k=1}^n\ \frac k{(n-k)!}\ \begin{Bmatrix}n\\ k\end{Bmatrix}. $$ 숫자들 $a_2,a_3,\ldots,a_7$ 거의 같다 $$ 0.75,\ 0.7037037037,\ 0.68359375,\ 0.67232,\ 0.66510202332,\ 0.660083. $$이 링크 에서와 같이 WolframAlpha를 사용하여 계산했습니다 .

명백한 추측은 우리가 $a_n\ge\frac12$ 모든 $n\ge1$, 시퀀스가 ​​감소합니다. 이것은 한계가 있음을 의미합니다. 조금 덜 분명한 추측은 한계가$\frac12$.

답변

1 AnginaSeng Aug 20 2020 at 20:22

주어진 요소를 $X$ 확률로 $$a_n=1-\left(\frac{n-1}{n}\right)^n.$$ 따라서 이미지의 예상 크기는 $na_n$ 예상되는 승리는 $a_n$. 이것은 기대의 선형성 일뿐입니다.

따라서 $$\lim_{n\to\infty}a_n=1-e^{-1}.$$

점근 확장을 얻을 수 있습니다. $$n\ln\frac{n-1}n=-1-\frac1{2n}-\frac1{3n^2}+O(n^{-3})$$ 그래서 $$\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)$$ 그래서 $$a_n=1-e+\frac{e}{2n}+\frac{5e}{24n^2}+O(n^{-3}).$$