Operator probability in a RPN string

Question

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.

Answer 1

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

Answer 2

(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$.

Answer 3

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]