Expected Number of Actions in Program

Question

Let's say I have a simple programming language that controls a robot's movement.

These are the rules of the language:

A program is represented by a string of letters and numbers.
F --> move forwards 1 meter
B --> move backward 1 meter
L --> turn left 90 degrees
R --> turn right 90 degrees

A command followed by a number makes a for-loop. This means that the command is repeated that number of times.
 
Examples: 
"F" moves the robot forwards once
"F3" moves the robot forwards 3 times
"F30" moves the robot forwards 30 times
"FL" moves the robot forwards once, and turn left once
"F3L3" moves the robot forwards 3 times, and turns it left 3 times.
"L40" turns the robot left 40 times   
"F0" moves the robot forwards 0 times, i.e. does nothing
"F0L3" turns the robot left 3 times.

Extra:
A program cannot start with a number.
"turning left" means the robot rotates 90 degrees counterclockwise. It does not move forwards after rotating
"moving forwards" strictly means moving 1 meter. 

My Question:

Let's say I have an unknown program that is n characters long. "Characters" means letters and digits. For the first black space representing a character, I randomly put either "F", "L", "R", or "B". For each black space after that, I randomly put either "F", "L", "R", "B" or one of the digits 0-9. This way, I get a program of n characters.

1. What is the expected number of commands(moving forwards/backwards 1 meter or turning left/right 90 degrees) the robot performs?
2. If the robot starts at the origin facing in the positive y-direction, what is the expected coordinate position of the robot?

I think geometric distribution might help, but I don't really know how. Thanks in advance.

Answer 1

Disclaimer

Not a full step-by-step solution, just an overview of how to solve the problem.

Probability Vector

Define the following probability vector:

$$ \mathbf{a}_{i}= \begin{Bmatrix} x_{1}^{[i]} \\ x_{2}^{[i]} \end{Bmatrix} $$

• $x_{1}^{[i]}$ denotes the probability that the program has action as the $i$-th digit
• $x_{2}^{[i]}$ denotes the probability that the program has repetition as the $i$-th digit.

Because the first digit has to be an action, we have:

$$ \mathbf{a}_{1} = \begin{Bmatrix} 1 \\ 0 \end{Bmatrix} $$

Recursive Relation

We have the following recursive relation:

$$ \mathbf{a}_{i+1}=\mathbf{M}\mathbf{a}_{i}= \begin{bmatrix} \alpha & 1 \\ 1- \alpha & 0 \end{bmatrix} \begin{Bmatrix} x_{1}^{[i]} \\ x_{2}^{[i]} \end{Bmatrix} $$

$\alpha$ is the probability that an action is followed by another action. Therefore the first column of $\mathbf{M}$ represents possible branching of the program, including the probability of each branch. The second column is the same, however, repetition must be followed by action (if I get your problem correctly), hence $1$ and $0$.

Expected Value

Define expected value vector as the following:

$$ \mathbf{E}^{[n]}= \begin{Bmatrix} E_{1}^{[n]} \\ E_{2}^{[n]} \end{Bmatrix}= \sum_{i=0}^{n-1} \mathbf{M}^{i}\mathbf{a}_{1} $$

• $E_{1}^{[n]}$ is the expected number of actions in a program of length $n$
• $E_{2}^{[n]}$ is the expected number of repetition numbers in a program of length $n$

You can compute the matrix geometric sum using eigenvalues & eigenvectors of $\mathbf{M}$. If you are not obliged to solve by hand, then it is very simple to compute the sum with programs like MATLAB.

Second Question

As mentioned in the comment, the available steps are symmetric, in the sense that each action has an action that cancels it. Consequently, for any program such as $F3L3$ there is a program such as $B3R3$ with equal probability, thus when averaged will result in the origin.