Help in proper notations and mathematical formulation

Question

For a given series, $S = \{-1,0,-2,1,etc\}$. The number of elements in $S$ is $N = 100$. Each $s_i$ belongs to a alphabet from a finite alphabet set $\mathcal{A} = (a_1=0, a_2=1, a_3=2, a_4=3, a_5=-1, a_6=-2, a_7=-3, a_8=-4)$. The cardinality of $\mathcal{A}$ is $m = 8$. Each $a_i$ is associated with a probability $p_i$ and $\sum_{i=1}^m = 1$.

Part 1: I need help in the correct notations used to mathematically express the above example. This is what I have tried:

Let, $S =\{s_1,....,s_N\}$ be a random sequence / series represented as a succession of $N$ symbols from a finite alphabet set $\mathcal{A} = \{a_1, \ldots, a_m\}$, $|\mathcal{A}|= m$ where $a_i$ are real or complex numbers and $s_n \in \mathcal{A}$, $n=1,2,\ldots,N$.

Is the above formulation and notation correct? What is the proper way to express this for a general case and not just for $m=8$

UPDATE : Part 1 has been answered.

Part 2: For the given series which is representing the data (information), I need to estimate the probability of occurrence of each symbol using MLE formulation. I think it should be like this but unsure. LEt $c_i$ be the letter counts since the data sequence $S$ appears to follow multinomial distribution. Multinomial distribution is based on counts.

The likelihood is \begin{eqnarray*} l(p_1,\ldots,p_{m};s_1,\ldots,s_{N}) &:=& {P}(c_1=a_1,\ldots, c_{m}=a_{m}; p_1,\ldots,p_{m}) \end{eqnarray*}

How to find $\hat{p}_i$ using MLE?

Answer 1

You observe a sequence $(s_1,\ldots, s_N)$ where random variables $S_k$ are i.i.d. and are drawn from a set (alphabet) $\mathcal{A} = \{a_1,\ldots, a_m\}$ with letter probabilities $P(a_i)=p_i$ for $1\leq i \leq m$ and $\sum_{i=1}^m p_i = 1$.

The likelihood function can be written as:

\begin{eqnarray*} l( p_1,\ldots, p_m; s_1, \ldots, s_N ) &=& P( S_1 = s_1, \ldots, S_N = s_N ) \\ &=& \prod_{k=1}^N P(S_k = s_k) \\ &=& \prod_{k=1}^N \sum_{i=1}^m p_i \mathbf{1}\{s_k = a_i\} \end{eqnarray*} where $\mathbf{1}$ is the indicator function which evaluates to one when the condition is true, and zero otherwise.

In part 2 of your question, we need to change the random variable to letter counts instead of the sequence itself. Let $X_i$ be the number of times we observe letter $a_i$ for $1\leq i \leq m$ in our sequence of length $N$. Then $\{X_i\}_{i=1}^m$ has a multinomial distribution:

$$ P(X_1 = x_1,\ldots,X_m=x_m) = \frac{N!}{\prod_{i=1}^m x_i!} \prod_{i=1}^m p_i^{x_i}. $$

(Convince yourself this is in fact the right probability mass function for letter counts; the argument involves some combinatorics.)

The log-likelihood function can be written as:

\begin{eqnarray*} \log l(p_1,\ldots,p_m; x_1,\ldots, x_m) &=& \log P(X_1 = x_1, \ldots X_m = x_m) \\ &=& \log(N!) - \sum \log(x_i!) + \sum x_i \log p_i. \end{eqnarray*}

The MLE of $p_i$ can be found by maximizing the log-likelihood. However, note that we have a constrained maximization problem here because we require $\sum p_i = 1$.

To convert this to an unconstrained maximization problem, let's introduce a Lagrange multiplier $\eta$. So the MLE of $p_i$ can be expressed as:

$$ \hat{p}_i = \arg \max _{p_i} \log(N!) - \sum \log(x_i!) + \sum x_i \log p_i + \eta \left( 1-\sum p_i \right). $$

Setting the gradient of the objective function to zero gives:

$$ \frac{x_i}{p_i} - \eta = 0 \implies p_i = \frac{x_i}{\eta}. $$

However, note that in order to meet the constraint, we must set $\eta = N$ (because $\sum x_i = N$).

This finally gives us the MLE:

$$ \hat{p}_i = \frac{x_i}{N} $$

which can also be expressed as $$ \hat{p}_i = \frac{ \sum_{k=1}^N \mathbf{1}\{s_k = a_i\} } {N}. $$

This is intuitively pleasing! To get the ML estimate of $p_i$ count the number of times you see the letter $a_i$ in your original sequence and divide that by $N$.

Answer 2

I assume the elements in $S$ are independent from each other. Then, I would formulate it in the following way:

Let $\mathcal{A}=\{a_1, \ldots, a_M\}$ denote a finite alphabet with $a_m\in\mathbb{C}$ with associated probability of occurence $P(a_m)$ and $\sum_mP(a_m)=1$. Let $S=(s_1, \ldots, S_N)$ be a sequence of $N$ elements with $s_i\in\mathcal{A}$. Then, the likelihood for a given sequence $S$ equals

$$P(S)=\prod_np(s_n).$$

Does that fit what you wanted to express?