Expected value of random expressions I'm trying to solve this math puzzle: write numbers $1$ to $N$ in a row. Randomly insert $+$ or $\times$ between two adjacent numbers with equal probability. What is the expected value of the expression if the expression is evaluated as an ordinary arithmetic expression? For instance, $1 + 2 \times 3$ will be evaluated as $1 + (2\times3)$.
Initially I thought that it was a simple recursion, but then I realized that $\times$ would change the precedence of the entire expression and then got stuck. It's easy to find a solution for a small enough $N$ with code, but I'm curious how one can solve it with math.
Thanks,
 A: I'm pretty sure this is incorrect actually. I assumed that the precedence rules would play nicely with RPN, but forgot that you might need to shuffle the input numbers as well. However, I'm going to leave this up since 1) it answers a similar question and 2) might be fixable with some slightly more careful arguments.

Every expression $1 \square_1 2 \square_2 3 \cdots \square_{n-1} N$ where $\square_i \in \{+,\times\}$ with equal probability can be rewritten unambiguously as $N, \ldots, 1, 2, \diamond_1, \diamond_2, \ldots, \diamond_{n-1}$ with $\diamond_i \in \{+,\times\}$ using Reverse Polish Notation. This should help us with the thorny issue of precedence that you raise. Now, it should be a relatively simple recursion argument.
Let $S_i$ be the random variable corresponding to value from the game played with $N = i$. Apologies in advance for mixing RPN and "standard" notation. Then $E(S_1) = 1, E(S_2) = \frac{3 + 2}{2} = \frac{5}{2}$. Then $S_3 = 3, (2 \cdot S_2), \diamond$, and so we have
\begin{align}
E(S_3) & = E[\frac{1}{2}(3, (2 \cdot S_2), +) + \frac{1}{2}(3, (2 \cdot S_2), \times)] \\
& = \frac{1}{2} ([3, 5, +] + [3,5,\times]) \\
& = \frac{1}{2} (8 + 15) \\
& = \frac{23}{2}.
\end{align}
Generally, then, we have the recursive formula
\begin{align}
E(S_N) & = E[\frac{1}{2}( (N,((N-1) \cdot S_{N-1}),+) + (N,((N-1) \cdot S_{N-1}),\times) )] \\
& = \frac{1}{2}\left[ (N, \left[ (N - 1) \cdot E(S_{N-1})\right], +) + (N, \left[ (N - 1) \cdot E(S_{N-1})\right], \times) \right]
\end{align}
with initial condition $E(S_1) = 1$.
Now, does this have a closed form solution? I'm not sure, and it's late here so I'll leave it at that for now. If you know the first few values of the sequence you could always try oies.org
