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?


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$.

  • $\begingroup$ Ok, so the observed data is letter counts, not the sequence itself. And you want the ML estimate of $p_i$'s. Please update your question accordingly. $\endgroup$ – Atul Ingle Feb 19 '17 at 14:45
  • $\begingroup$ @RiaGeorge please see updated answer. I introduce new random variables $X_i$ to denote letter counts in the original seqence $S_k$. However, if you want you can express $X_i = \sum_{k=1}^N \mathbf{1}\{ S_k = a_k \}$. $\endgroup$ – Atul Ingle Feb 19 '17 at 22:20

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


Does that fit what you wanted to express?

  • $\begingroup$ That is the probability for a given sequence $S$. The likelihood should be a function of the parameters $p_1,...p_M$. $\endgroup$ – Atul Ingle Feb 18 '17 at 15:04
  • $\begingroup$ @Maimilian Matthe: I agree with Atul Ingle that the likelihood should be the function of the probabilities as I have tried to express. I cannot follow how to write the probability that $s_1$ can be a symbol $a_1$ or can be $s_1$ can be $a_2$ etc when expressing the likelihood, $\endgroup$ – Ria George Feb 18 '17 at 19:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.