6

In this question asked on Stackoverflow, the asker gives a Java function similar to this:

public int f(){
    if(Math.random() >= 0.5){
        return 1;
    }
    else{
        return 1 + Math.max(f(), f());
    }
}

In math-speak, that would be written something like this:

$$f = \left\{ \begin{array}{ll} 50\%\ chance : & 1 \\ 50\%\ chance : & 1 + max(f, f) \end{array} \right.$$

So basically, $f()$ is a probabilistic function that calls itself twice with 50% probability, and returns the maximum depth of its calls.

If you draw the call-tree and label the first case "tails" and the second case "heads," you can see that the question "What is the probability that this function eventually returns" is the same as the question "What is the probability of eventually getting more heads than tails.". Thus, this function terminates with probability 1. This also allows you to calculate the expected number of total times that $f()$ is called.

However, the one question I haven't been able to answer is, what is the expected return value of $f()$?

My first thought was that the expected value $E_f$ should be $$E_f = 0.5 * 1 + 0.5 * (1 + max(E_f, E_f))$$ However, that is clearly wrong; that would mean that, no matter how many calls $f()$ makes to itself in the second case, $E_f = 2$ !

So, does anyone know how to calculate the expected return value of $f()$?

Community
  • 1
BlueRaja - Danny Pflughoeft
  • 8,434

1 Answers1

4

The result of the procedure is a random positive integer $X$ such that $$ X=1+B\cdot\max(X_1,X_2), $$ where $X_1$ and $X_2$ are two independent copies of $X$ and $B$ is a Bernoulli random variable with $P[B=1]=P[B=0]=\frac12$.

To describe the distribution of $X$, let $R_n=P[X\geqslant n]$ for every positive integer $n$. The stochastic identity above translates into $$ P[X\geqslant n+1]=P[B=1]\cdot P[X_1\geqslant n\ \text{or}\ X_2\geqslant n], $$ that is, $$ R_{n+1}=R_n-\tfrac12R_n^2. $$ Since $R_1=1$, this recursion characterizes the distribution of $X$.

Unfortunately, iterating quadratic functions is notoriously difficult. Fortunately, estimating $R_n$ is rather straightforward, leading to $R_n\sim\frac2n$. Thus, the "expected return value" $E[X]=\sum\limits_{n\geqslant1}R_n$ is infinite while the return value $X$ is almost surely finite.

Did
  • 279,727