Normal approximation by finding the limit of a recursive formula with two parameters

50 Views Asked by At

I am trying to calculate the (asymptotic) expectation of a recursively-defined random variable $T(N)$, whose distribution is the same as that of the sum of 1 and two independentally distributed $T(N, K)$ with smaller $N$ and $K$. Please leave a comment in case any clarification is required. \begin{equation} \left\{ \begin{aligned} T(N) | \{K = k\} &\sim T(N, k), \\ K &\sim \text{Binomial}(N, \frac{1}{2}); \\ T(N, K) | \{J = j\} &\sim 1 + T(F(N), j) + T(N - F(N), K - j),\\ J &\sim \text{Hypergeometric}(N, K, F(N)); \\ T(N, 0) &= T(N, N) = 0. \end{aligned} \right. \end{equation}

If we write the expectation of $T(N)$ as $E(N)$ and that of $T(N, K)$ as E(N, K), it reduces to finding the limit of the following recursive formula. \begin{equation} \left\{ \begin{aligned} E(N) &= \sum_{k=0}^{N} \binom{N}{k} \frac{1}{2^N} E(N, k) \\ E(N, K) &= \sum_{j=\max\{0, F(N)+K-N\}}^{\min\{F(N), K\}} \frac{\binom{K}{j} \binom{N-K}{F(N)-j}}{\binom{N}{F(N)}} [1 + E(F(N), j) + E(N - F(N), K - j)] \\ E(N, 0) &= E(N, N) = 0. \end{aligned} \right. \end{equation}

By calculating the expectation of the first few $T(N)$, I can tell

$$ \lim_{N\to \infty} \frac{E(N)}{N} \approx 0.7177715 $$

How do I prove such a limit exists, and what exactly is that? I have no clue how to deal with such sequences with two indices.

(Note: my ultimate goal is to find the normal approximation of $T(N)$ as $N \to \infty$, which is why I additionally included variance, skewness, and kurtosis in the plot. Feel free to go for that directly if it is easier or leave a comment if you have advice for that. I mean "normal approximation" as in the same sense of the De Moivre–Laplace theorem.)

enter image description here