5
$\begingroup$

We are generating a strings of length $n$. The string consists of $n_1$ $1`s$ and $n_2$ $2`s$. Where $n_1+n_2=n $. All permutations of the string are equally likely.

What is the probability of the event $A({m}_{11},{m}_{12},{m}_{21},{m}_{22} ) = \{{v}_{11} = {m}_{11},{v}_{12} = {m}_{12},{v}_{21} = {m}_{21},{v}_{22} = {m}_{22}\}$?

What will be the probability space in the case? How can I build it?

${v}_{ij}$ - denotes the number of occurrences in the string when the j goes immediately after i.

For example, if we have the following string $122212212121$, then ${v}_{11} = 0, {v}_{12} = 4, {v}_{21} = 4, {v}_{22} = 3$.

I can not get how to build the probability space in the case.

I tried to compute the probability of $A$ by noting that there are $2^n$ strings we can get. Then I thought about using Markov chain to compute the number of strings which would be inappropriate for the event $A$ and subtracting them from $2^n$ and dividing the result by $2^n$ due to the classic definition of the probability.

I would like to get a better way to compute the probability of the event $A$ if it is possible and to get the idea behind building the probability space.

$\endgroup$
  • $\begingroup$ It is hard to tell what the question is here. Are you starting with fixed probabilities $\{{v}_{11}, {v}_{12} ,{v}_{21} ,{v}_{22} \} $ and trying to determine the probability of generating a string of length $n$? What do the ${m}_{ij}$ represent? Or are you deriving the ${v}_{ij}$ from observing a given string and trying to generate something from it? (Which is really the same as my 1st question unless the starting string is random, in which case we would need starting probabilities for it) Or are you asking a Bayesian question; trying to predict the starting probabilities? Or something else? $\endgroup$ – Stephen Meskin Dec 9 '17 at 16:25
  • $\begingroup$ @StephenMeskin, I updated the question. Hope that will clarify what you are asking. $\endgroup$ – trafalgarLaww Dec 9 '17 at 16:48
1
$\begingroup$

Let $O(m_{11},m_{12},m_{21},m_{22})$ denote the number of strings with $m_{11}$ occurences of $11$ etc ..., that end with $1$.

Similarly let $T(m_{11},m_{12},m_{21},m_{22})$ denote the number of strings with $m_{11}$ occurences of $11$ etc ..., that end with $2$.

These can be calculated by the following recurrence relations \begin{eqnarray*} O(m_{11},m_{12},m_{21},m_{22})= O(m_{11}-1,m_{12},m_{21},m_{22})+T(m_{11},m_{12},m_{21}-1,m_{22}) \\ T(m_{11},m_{12},m_{21},m_{22})= O(m_{11},m_{12}-1,m_{21},m_{22})+T(m_{11},m_{12},m_{21},m_{22}-1) \\ \end{eqnarray*} and your pr0babilities are given by $A(m_{11},m_{12},m_{21},m_{22})= (O(m_{11},m_{12},m_{21},m_{22})+T(m_{11},m_{12},m_{21},m_{22}))/2^{m_{11}+m_{12}+m_{21}+m_{22}+1} $

$\endgroup$
  • $\begingroup$ What will be the probability space in the case? $\endgroup$ – trafalgarLaww Dec 9 '17 at 16:56
  • $\begingroup$ The length of such a string is $m_{11}+m_{12}+m_{21}+m_{22}+1$ and the probability of getting a string of length $l$ is $1/2^{l}$. $\endgroup$ – Donald Splutterwit Dec 9 '17 at 16:56
  • $\begingroup$ @trafalgarLaww Based on the answer to your question you should probably edit the question to 1) eliminate the redundant ${v}_{ij}s$; 2) Indicate that you are randomly selecting strings of 1s and 2s of length $n$; 3) That an event consists of a selecting a string having a specific set of ${m}_{ij}s$; and 4) That you are looking for the probability of those events. $\endgroup$ – Stephen Meskin Dec 9 '17 at 20:08
  • $\begingroup$ There is no basis for the induction. And is it possible to tackle the recurrence relation so that I would be able to compute it in a constant time? $\endgroup$ – trafalgarLaww Dec 11 '17 at 10:26
  • $\begingroup$ $O(0, 0, 0, 0) = 1$ and $T(0, 0, 0, 0) = 1$. Am I right? $\endgroup$ – trafalgarLaww Dec 11 '17 at 10:27

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.