Number of Power-Constrained Ternary Sequences

At the outset, it looks like a difficult combinatorial problem. However, I'll show how probabilistic methods can be used to solve this problem (or even more general versions of it) very easily.

Consider a random sequence $\textbf{W}$ of length $n$ , each of whose elements $W_i$ are chosen i.i.d. with uniform probability, i.e. for each $j=0,1,2$ and for all $i=1,2,\ldots, n$ $\mathbb{P}(W_i=j)=\frac{1}{3}$ Thus probability of each sequence in $\{0,1,2\}^n$ is uniformly $3^{-n}$ .

We are interested in the probability that a randomly chosen sequence is eligible for transmission, i.e. $\mathbb{P}\big( \frac{1}{n} \sum_{i=1}^{n}W_i \leq \frac{1}{2}\big)$ By definition, the number of sequences $N(n)$ of length $n$ which are eligible for transmission, is simply $N(n)=3^n\mathbb{P} \big( \frac{1}{n} \sum_{i=1}^{n}W_i \leq \frac{1}{2}\big)$ Thus, the required limit is $l = \lim_{n\to \infty} \frac{1}{n} \ln N(n) = \ln(3) + \lim_{n\to \infty} \frac{1}{n} \ln \bigg(\mathbb{P} \big( \frac{1}{n} \sum_{i=1}^{n}W_i \leq \frac{1}{2}\big)\bigg)$ Thus, all we have to do is to evaluate the limit on the right hand side. Now, note that the random variables $W_i$ are chosen i.i.d. with uniform probability. Hence, we can simply use standard Large Deviation Theory for evaluating this limit. The Moment Generating Function of the i.i.d. random variables $W_i$ is $M(\theta) = \mathbb{E}(\exp(\theta W_i)) = \frac{1}{3} \big( 1 + \exp(\theta) + \exp(2 \theta)\big)$ Hence, using the Large Deviation Theory, we have $\lim_{n\to \infty} \frac{1}{n} \ln \bigg(\mathbb{P} \big( \frac{1}{n} \sum_{i=1}^{n}W_i \leq \frac{1}{2}\big)\bigg) = -\sup_{\theta > 0} \big(-\frac{\theta}{2}- \ln M(-\theta)\big) \stackrel{(*)}{\approx} - 0.197378,$ where (*) follows from simple calculus. Hence, it follows that $\lfloor 10^4 l \rfloor= 9012$ .

Remark 1: The above method is very general and can be used to find such limits when we have a constraint of the form $\frac{1}{n} \sum_{i=1}^{n} f(w_i) \leq \alpha$ for virtually any function $f$ .

Remark 2: Things usually behave nicely in the limit. That is why we have so many nice limit theorems in probability (Central Limit Theorem (CLT), Laws of Large Numbers (LLN), Law of Iterated Logarithms (LIL) and so on). It is a good exercise to use these limit theorems to get a first order approximation to many combinatorial problems, which might look daunting in their finite incarnations.