4
$\begingroup$

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

Improve this question
$\endgroup$
9
  • $\begingroup$ In my understanding, probability looks more intuitive and realistic when the experiment has been performed multiple times (in theory, infinite times). It is only then that essence of probability could be reached at. $\endgroup$ – Upendra01 Nov 5 '17 at 15:08
  • $\begingroup$ In the ideal world we would perform the experiment infinite times but this is what we cannot afford in the real life. Let say we have 1000 different "symbols" and we have managed to use the "symbols generator" only 100 times. So, at leas 900 symbols have not been seen at all. Many symbols were seen exactly one time and only few symbols have been seen more than once. This is the only "data" that we have. Based on that we need to estimate the probabilities for all the symbols. $\endgroup$ – Roman Nov 5 '17 at 15:12
  • $\begingroup$ Now there are symbols that have been observed fairly less number of times (sometimes even zero times); this is an indicative of the fact that the data available is far too less. As a consequence, the probability model derived from this data would be incorrect/erroneous. One way of estimating the probabilities could be to model the event by some distribution, estimate the parameters of this distribution and then compute the probability of an event using this distribution. For this, you need to have fairly large number of symbols already generated to estimate the parameters correctly $\endgroup$ – Upendra01 Nov 5 '17 at 15:15
  • $\begingroup$ For the symbols that have never been observed during the course of experiment, it makes some sense to assign to them a certain small non-zero probability instead of zero value (as computed by your probability formula). Such a strategy works in certain machine learning applications as well. $\endgroup$ – Upendra01 Nov 5 '17 at 15:17
  • $\begingroup$ What about splitting the data set (observations) into equal parts? We can use the first data set for counting symbols and then, after having the counts, we can use the second data set to answer the following question: How probable for a symbol to bee seen N times in the second data set under the condition that it has been seen K times in the first data set? It looks to me that in this way we can estimate the probability of a symbol to be observed even if it has never been observed before. In the same way we can also "adjust" the probabilities for those symbols that have been seen once. $\endgroup$ – Roman Nov 5 '17 at 15:21
1
$\begingroup$

Confidence intervals

Your estimate is the maximum likelihood of the binomial (/multinomial) distribution. You may be interested to also calculate confidence intervals (otherwise I suggest that you do get interested in this).

In the case of the binomial distribution (which I believe you could use to simplify your case with a multinomial distribution), there are many ways to estimate these intervals, but the estimates do often not work well for low rates (due to the normal approximation you get negative values, or zero size intevrals).

Clopper Pearson intervals

One interval that works well and is easy to understand is the Clopper-Pearson interval, which sets the limits $p_{upper}$ and $p_{lower}$, given an observation $k$ in $n$ trials, such that, for confidence $\alpha$, the CFD at value k is $\alpha/2$ for the binomial distribution $B(n,p_{upper})$ and $1-\alpha/2$ for the binomial distribution $B(n,p_{lower})$.

This means for a given true value of $p$ (and the assumption that we can apply the model of a binomial distribution) then the limits will be correct at least $\alpha$ percent of the time. Since $\alpha/2$ of the time we draw a value from the portion of the CFD lower than $\alpha/2$ (making our p_{upper} estimate wrong), and $\alpha/2$ of the time we draw a value from the portion of the CFD higher than $1-\alpha/2$ (making our p_{lower} estimate wrong).

Graphical view and explanation

I reproduce the figure 3 from the referenced article by Clopper and Pearson for your case of 100 trials and a confidence interval of 95%, as well as a comparison with 1000 trials.

From the below image you should see how the Clopper-Pearson intervals work. By calculating the intervals based on hypothetical p-values, you assure that for any hypothetical p-value you never make more mistakes than $100-\alpha$% of the time. graphical explanation of Clopper-Pearson intervals

A comparison between n=100 and n=1000, since your problem has very bad limits. comparison confidence intervals n=100 and n=1000

Change of concept

The above explanation is nice and all, and you could expand it a bit by using different confidence interval estimators or using improvements with prior probabilities.

Yet in your case of low number of observations it will not matter so much. Your problem has very bad limits. Differences between a few more or less occurrences do not really make a large difference. And also differences between p's won't be observed. Your 95% intervals are for the first ten k: $$\begin{array}\\ k & p_{lower} & p_{MLE} & p_{upper} \\ 0 & 0.0000 & 0.0100 & 0.0362 \\ 1 & 0.0003 & 0.0200 & 0.0545 \\ 2 & 0.0024 & 0.0300 & 0.0704 \\ 3 & 0.0062 & 0.0400 & 0.0852 \\ 4 & 0.0110 & 0.0500 & 0.0993 \\ 5 & 0.0164 & 0.0600 & 0.1128 \\ 6 & 0.0223 & 0.0700 & 0.1260 \\ 7 & 0.0286 & 0.0800 & 0.1289 \\ 8 & 0.0352 & 0.0900 & 0.1516 \\ 9 & 0.0420 & 0.1000 & 0.1640 \end{array}$$

Say, differences of p<0.01 won't be noticeable at all, and for p>0.01 the precision is still very bad. So, only if you expect a few of your symbols to have very high probability of occurrence p>>0.01, only then your 100 observations might be able to help you with detecting and quantifying those. --- In that case you should note that the binomial case is different from the multinomial case. A multinomial with thousand p=0.001 will more likely give you, for some symbol, a k>1 compared to a binomial, with a single p=0.001. (in fact the probability for none of the symbols turning up a two or more times in 100 draws is very small 0.999 x 0.998 x ... x 0.902 x 0.901 ~ 0.6%)

So. I'd say that puzzling whether you can improve your estimate is not very useful and you should figure out how you can improve your experiment, or maybe whether you can be satisfied with testing different concepts (e.g. occurrence of groups/categories of symbols), rather than analyzing thousand badly estimated $\hat{p}_i$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This is a well written answer.....but I think you are being presumptuous about what's important to the OP. Instead of giving an answer to the question (which is just hard imo), you've decided to change the question to one about binomial models (which has a clearer answer). $\endgroup$ – probabilityislogic Nov 11 '17 at 12:15
  • $\begingroup$ The question "Is there a better way to estimate the probabilities $p_i$?", in the context of insufficient observations for an accurate estimate, is asking for a presumptuous answer. But, certainly, taking into account the error margins of estimates, presented in this answer as confidence intervals, is a better way, not? I see the assumption of a binomial model not as a big problem. The value is, it presents an idea of accuracy. Yes you have multiple (related) comparisons and should correct for that. Some do this explicitly, but I don't think that is always necessary (eg exploratory stats). $\endgroup$ – Sextus Empiricus Nov 11 '17 at 12:56
1
$\begingroup$

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!

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ MLE has a "small sample bias" in this context though - giving zero probability to categories not observed until enough sample is obtained $\endgroup$ – probabilityislogic Nov 11 '17 at 12:00
  • $\begingroup$ I think 'bias' is more considered as a frequentist concept here, as in: the expected value of the estimate is not biased. $\endgroup$ – Sextus Empiricus Nov 13 '17 at 23:15
0
$\begingroup$

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.

Improve this answer
$\endgroup$

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.