How to estimate a probability of an event to occur based on its count? I have a generator of random symbols (single act of generation produces exactly one symbol). I know all the symbols that could be generated and for each symbols I would like to estimate the probability of it to be generated (at single act of generation).
The number of observations (acts of generation) is significantly smaller than the total number of possible symbols. As a consequence the most of the symbols have never been observed / generated in our experiment. A large number of observed symbols were observed only once.
The simplest and straightforward way to estimate the probabilities of each symbol to appear is to use this formula: $p_i = n_i/\sum_j n_j$, where $n_i$ are counts of the symbol $i$.
Is there a better way to estimate the probabilities $p_i$?
 A: This sounds like a good case for using a Bayes approach. For this to work well, you need some prior information. A convenient prior to use is a dirichlet. From the perspective of estimation, this amounts to adding "pseudo observations" to the observed counts. A simple way is to add $\frac {1}{C} $ counts to each category ($C $ is # categories), giving $p_i=\frac {n_i+C^{-1}}{1+\sum_jn_j}$. This is adding 1 data point worth of information, so wouldn't be dragging your estimate too far away from the observed data. It has the advantage of giving a non-zero estimate for each category, unlike the mle.
If an even distribution is more what you expect, then you should increase the pseudo observation count. This means you have $p_i=\frac {n_i+C^{-1}m}{m+\sum_jn_j}$ where $m $ is the weight applied to the even distribution. $m=C$ is the "uniform" prior (also rule of succession), and $m=\frac {C}{2} $ is the jeffreys prior. These are standard non-informative priors, but they have problems in large dimensions.
A better approach would be to add some hierarchy and structure to your model. All you have at present is a multinomial random variable with a large number of categories. You will need to think about the context of your problem more to decide which categories are similar in terms of how the symbols are generated.
Hope this helps!
A: The distribution corresponding the generating act or trial is the multinomial distribution.
The parameter estimation method you have written is its maximum likelihood estimation. If you think (before seeing the result of trials), that every parameter setting could generate the sample equally likely, then the maximum likelihood estimation shows the "most likely" parameter setting. (You can see the derivation at this notes (pdf, at page 9.))
It has fairly nice properties, and it is unbiased in this case, so one can call it "the best".
A: Assuming that your random symbol generator actually works properly, the probabilities are all equal. If you are in doubt, then a mathematical analysis of the random generator would be in order.  If it is a random generator that you have obtained from a reputable source, there would probably be published literature that could help.  I think that, to prove that a random generator works properly by experimental means would require such a vast sample size as to be virtually impossible.
