Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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()$?

share|improve this question
1  
don't you mean $(1+\max(E_f,E_f))$ instead of just $\max(E_f,E_f)$ in the end ? –  Denis Aug 8 '13 at 14:47
    
@dkuper: Yes, thanks –  BlueRaja - Danny Pflughoeft Aug 8 '13 at 15:06

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
"Thus, the expected return value is infinite while the return value is finite" - ...whoa, I didn't even know that was possible. –  BlueRaja - Danny Pflughoeft Aug 8 '13 at 15:16
1  
Reminds me of en.wikipedia.org/wiki/St._Petersburg_paradox –  raylu Aug 8 '13 at 17:54
    
@raylu The comparison is quite on-topic. –  Did Aug 8 '13 at 20:23

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.