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.

Given $$ E_{n,k} = \begin{cases} 0 & \text{ if } n \leq k \\ n & \text{ if } k = 0 \\ \sum_{i=0}^{n-1} \dfrac{1}{n} \cdot E_{i,k-1} & \text{ otherwise } \end{cases} $$ I wonder is there a closed form for this recurrence that I'm not aware of?

share|improve this question
    
Where does this arise? Just curiosity... –  vonbrand Mar 6 '13 at 17:54
    
Seems to me like the calculation of an expected value involving two variables. There is a recurrence $$E_{n+1, k} = \frac{1}{n+1} (n E_{n,k} + E_{n,k-1})$$ which suggests a probability of two sub-events happening. –  muzzlator Mar 6 '13 at 18:01
    
Compare this to the identity $$C_{n+1, k} = C_{n,k} + C_{n, k-1}$$ –  muzzlator Mar 6 '13 at 18:14
    
$E_{n,k}$ has a generating function given by: $$\sum_{k=1}^{\infty} E_{n,k} z^{k-1} = \frac{n+1}{2-z} - \frac{1}{1-z} + \frac{(z)_n}{n!(2-z)(1-z)}$$ where $(z)_n = z(z+1)\cdots(z+n-1)$ is the $n^{th}$ Pochhammer polynomial. No idea how to simplify this further. –  achille hui Mar 6 '13 at 18:34
    
@vonbrand: The problem is actually finding the expectation of $N$ given that $$\text{for } i = 1 \text{ to } k \{ N = \text{random}(N) \} \text{ where random }(N) = \{0, \ldots N-1\}$$ I tried to solved this problem using Dynamic Programming in $O(N^3)$ but it was too slow, so I guess there must be a nicer form for computing this expectation. –  Chan Mar 6 '13 at 20:52
show 8 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.