Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider the set $S_n$ of all strings of length $n$ ($n$ integer, $n \geq 3$) representing an expression in RPN
( http://en.wikipedia.org/wiki/Reverse_Polish_notation. )

Assumptions (to simplify):

  • A string represents always a "valid" expression, where, by "valid", here it is merely meant that when evaluated it will not give an error due to missing operands (the expression is allowed to "have undefined operations" such as division by 0, etc. )

  • Each character in a string can be only either an operand or an operator

  • All operators have arity equal to 2

Question:

  1. What is the probability that one random character picked from a string is an operator ?
  2. What is the probability that the $i$-th character of the string is an operator ?

Edit:
"valid" is to be interpreted as "well-formed" as Andreas Blass rightly noted.

share|improve this question
add comment

3 Answers

up vote 2 down vote accepted

I'm going to assume that "valid" expressions are well-formed in the usual sense. This means that not only are there (as you required) no operators lacking operands but also you do not end up with two or more operands on the stack and no operation to combine them. Such an expression necessarily has $n$ operators and $n+1$ operands for some $n$ (in particular, its length is odd). So the probability of a randomly chosen term in a valid string of length $2n+1$ being an operator is $n/(2n+1)$. (I'll think about question 2 after I emerge from jet lag; at the moment, my brain is 9 hours out of phase with reality.)

share|improve this answer
add comment

(I decided to add a second answer to address Question 2, because it didn't seem right to modify an already accepted answer.) I should have mentioned earlier that, for the probabilities in the question, we can assume there's just one binary operator and one operand; if there are more of either, that just introduces the same factor into the numerator and denominator of the relevant ratios, so the probabilities are unchanged.

Let me write $C_n$ for the $n$-th Catalan number, the number of well-formed terms of length $2n+1$ (hence containing $n$ occurrences of the binary operator and $n+1$ occurrences of the operand). Also, let me write $D_{n,q}$ for the number of such terms that have the operator symbol in position $2n+1-q$, i.e., in a position that is followed by exactly $q$ symbols. (The reason for this curious parametrization will become clear in a moment.) Notice that we must always have $0\leq q\leq 2n-2$ (because the earliest place for an operator is the third symbol in a term). Consider any of the terms $t$ counted by $D_{n,q}$ and consider the operator symbol at position $2n+1-q$. It is the end of a unique subterm $t'$; let $l$ be the number of operator symbols in $t'$. We have $1\leq l\leq n-(q/2)$. (The upper bound is because $t'$ has length $2l+1$ and this has to be at most $2n+1-q$.) Now $t'$ can be any of the $C_l$ terms of the right length. $t$ can be obtained by substituting $t'$ for one occurrence of an operand in a term $t''$ with $n-l$ operators, provided $t''$ has an operand (not an operator) at the right location, $q$ symbols from the end. That gives the following recursion for $D_{n,q}$: $$ D_{n,q}=\sum_{l=1}^{n-(q/2)}C_l\cdot(C_{n-l}-D_{n-l,q}). $$ The first factor here counts the possibilities for $t'$; the second counts possibilities for $t''$. This recursion explains the choice of $q$ as parameter; the recursion proceeds for each $q$ independently. It also explains why each odd $q$ gives the same results as $q+1$.

share|improve this answer
    
Thank you Andreas! It will take me some time to really digest your development ;-) Intuitively, in case of various operators, one would expect that the probabilities would be affected by the operator precedence. –  Luna Jul 24 '11 at 18:48
    
@Luna: One of the great things about RPN is that you don't need (parentheses or) conventions about operator precedence. The order in which operations are to be applied is unambiguously indicated in the term itself. For example, if % and @ are two operations (the weird symbols are to avoid any prejudice about preference) then the two possible interpretations of x%y@z given by two precedence conventions, namely (x%y)@z and x%(y@z), have different RPN notations xy%z@ and xyz@%. –  Andreas Blass Jul 26 '11 at 16:39
1  
I can't believe I actually wrote "RPN notations" after all the times I've complained about "AC current", "ICBM missiles", "PIN numbers", and "ATM machines". –  Andreas Blass Jul 26 '11 at 16:41
add comment

I wrote a PARI program to compute the number of RPN strings of each length, and the probabilities of an operator at each position. I assumed that there are only two characters, one of which is an operator. If instead we use j operator characters and k other characters, this multiplies the numbers of strings of length $2n-1$ by $k^nj^{n-1}$ but doesn't change the probabilities.

The number of strings of each length turns out to be the Catalan numbers (see http://oeis.org/A000108.)

Here's my code, and the first few lines of its output:

LIMIT = 100;

count = vector(LIMIT); \count[i] = number of reverse polish strings of length 2i - 1

ops = vector(LIMIT); \ops[i] is a vector v of length 2i - 1 such that v[j] gives the number of strings with an operator in the jth position count[1] = 1;

ops[1] = [0];

{

for (i = 2, LIMIT,

ops[i] = vector(2*i - 1);

\\A string of length 2i - 1 is (arg1)(arg2)op. Let 2k-1 be the length of arg1

for (k = 1, i - 1, 

    \\Number of strings of length 2i-1 in which arg1 has length 2k-1 is 

count[k]*count[i - k]

    c = count[k]*count[i - k];

    count[i] += c;

    for (j = 1, 2*k - 1, 

        ops[i][j] += ops[k][j]*count[i - k]

    );

    for (j = 2*k, 2*i - 2,

        ops[i][j] += ops[i - k][j - (2*k - 1)]*count[k]

    )
);

ops[i][2*i - 1] = count[i];

write("rpn.txt", "n = ", 2*i - 1, " number of strings = ", count[i], " prob of operator = ", ops[i]/count[i])

);

}

n = 3 number of strings = 1 prob of operator = [0, 0, 1]

n = 5 number of strings = 2 prob of operator = [0, 0, 1/2, 1/2, 1]

n = 7 number of strings = 5 prob of operator = [0, 0, 2/5, 2/5, 3/5, 3/5, 1]

n = 9 number of strings = 14 prob of operator = [0, 0, 5/14, 5/14, 1/2, 1/2, 9/14, 9/14, 1]

n = 11 number of strings = 42 prob of operator = [0, 0, 1/3, 1/3, 19/42, 19/42, 23/42, 23/42, 2/3, 2/3, 1]

n = 13 number of strings = 132 prob of operator = [0, 0, 7/22, 7/22, 14/33, 14/33, 1/2, 1/2, 19/33, 19/33, 15/22, 15/22, 1]

share|improve this answer
    
oeis.org/A028364 appears to give the number of strings of length 2n-1 with operators in each position. –  David Wasserman Jul 18 '11 at 20:22
    
@David Wasserman, @Andreas Blass That's extremely interesting. Thanks! I did not know PARI, and it is very good to learn about it. It's very interesting that "The number of strings of each length turns out to be the Catalan numbers". Is that a well known result or just your discovery? [Probably a consequence of above Andreas Blass' result ?] –  Luna Jul 19 '11 at 0:55
    
It is well known that the number of well-formed terms of a given length is a Catalan number. This is usually stated in terms of parenthesizations of products of $n+1$ factors, but parenthesized and RPN notation are equivalent under well-known translations. –  Andreas Blass Jul 19 '11 at 7:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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