Uncertainty of conditional probability evaluated from sample

Question

I'm doing some some analysis of an arbitrary string of text, modelling it as a Markov chain where the state is simply the value of the previous character. Call the current character c and the previous character p; then it is trivial to calculate P(c | p) for the given sample text. However, if there are not many cases of a certain (p, c) pair, or in general not many samples used. I know qualitatively that the fewer the samples, the higher the uncertainty/error in this conditional probability is. However, how can I quantify this?

Answer 1

You can use the Hoeffding inequality:

$$ P(|\hat{p}_n-p|\geq t)\leq 2e^{-2nt^2}$$

($\hat{p}_n$ is your estimated probability). For small $n$, Markov ineqality may be more efficient:

$$P(|\hat{p}_n-p|\geq t)\leq \frac{p(1-p)}{nt^2} $$.

For example, with the second inequality, if $n=50$ the probability that the difference between your estimated probability and the truth is greater than $0.25$ is lower than $\frac{1}{4*50*0.25^2}=0.08$ ($p(1-p)<1/4$ but it can be much smaller...). Is 8% chance to have difference larger than $0.25$ small enough for you ?

Answer 2

To me, it sounds more like you want a conditional frequency, as a conditional probability has no "error" so to speak. The only error from a probability is from either from a mathematical approximation, or a mathematical error in the calculation. Once you make this conceptual distinction, I think finding the exact measure of error is easy. @robin's answer is a very conservative number - and represents the worst case error.

Anyways, I assume that your data is a $K\times K$ frequency table. The first way (row) is the letter previous $p_j\;(j=1,..,K)$, and the second way is the current letter $c_i\;(i=1,..,K)$ (column). Let the counts in each cell be denoted by $n_{ij}$. So $n_{11}$ is the number of times the character $p_1$ preceded the character $c_1$. Expressing your problem this way also allows a straight-forward generalisation to a more general model - just add extra ways into the frequency table to give your process more "memory" (although the notation becomes a bit cumbersome, for you have quantities such as $f_{i|(j_1,j_2,...,j_L)}$ for a Lth order auto-regressive process).

Now we need to write down the model. Because you have a markov model, this means that the frequencies are given by $0\leq f_{i|j}\leq 1$. This means that the frequency is a function of $p_j$ (i.e. we are modeling each row of the frequency table separately). They are constrained to sum to 1 over the rows $\sum_{i=1}^{K}f_{i|j}=1\;(j=1,\dots,K)$ The simplest model is to assume that each frequency is unconnected with any other. In this case you have a N-dimensional multinomial distribution for each row

$$p(n_{1j},n_{2j},\dots,n_{Kj}|f_{1|j},f_{2|j},\dots,f_{K|j},I)\propto f_{1|j}^{n_{1j}},f_{2|j}^{n_{2j}},\dots,f_{K|j}^{n_{Kj}} $$

Now you need a prior distribution for the $f_{i|j}$ values, which expresses what you know about them, prior to seeing the data. If you know that each letter is possible prior to seeing the data, then the uniform prior is the appropriate one. This is the one I will use. This gives a dirichlet posterior distribution for the $f_{i|j}$ (same form as above, because of the uniform prior). This has a mode (most likely value) where $f_{i|j}=n_{ij}$ as you would expect. Now, this means that each of the marginal posterior distributions have a Beta distribution

$$(f_{i|j}|D,I)\sim Beta(n_{ij}+1,\sum_{m\neq i}n_{mj}+K-1)$$

With a simple form for its mean and variance:

$$E(f_{i|j}|D,I)=\frac{n_{ij}+1}{\sum_{m}n_{mj}+K}$$ $$Var(f_{i|j}|D,I)=\frac{E(f_{i|j}|D)\left[1-E(f_{i|j}|D)\right]}{\sum_{m}n_{mj}+K+1}$$

Also, you can use the dirichlet distribution to get the correlation between two of the frequencies:

$$Corr(f_{i|j},f_{l|j}|D)=-\sqrt{\frac{E(f_{i|j}|D)} {1-E(f_{i|j}|D)} \frac{E(f_{l|j}|D)} {1-E(f_{l|j}|D)} }$$

I think this approach gives you a far better idea of the accuracy in your data, which shows the value in making a distinction between probability and frequency. probability can never be observed, only calculated or assigned. and frequencies can never be calculated or assigned, it can only be observed and predicted.