Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let (m,n) be an ordered pair of positive integers. While m>0 and n>0, let k_1 be a random positive integer between 1 and m and k_2 a random positive integer between 1 and n. Output (k_1,k_2). Let m=m-k_1 and n=n-k_2. What is the expected number of outputs?

Note that in the one-dimensional version of the problem, starting with a single integer n, the expected number of outputs is the nth harmonic number 1+1/2+1/3+...+1/n.

share|improve this question
4  
People on MO typically like to see some background or motivation for questions, an explanation as to why you're interested in the answer. All the questions you've asked recently are somewhat lacking in this regard. –  Keenan Kidwell Jun 26 '10 at 13:03
11  
They all seem to be from here: www2.truman.edu/~erickson/openproblems.html –  j.c. Jun 26 '10 at 14:03
    
Thank you for your kind responses. I had noticed that the one-dimensional case is answered very simply (the formula is given by the nth harmonic number), and wondered whether one could solve the two-dimensional version of the problem. We can derive a recurrence relation. Let e(m,n) be the expected number of outputs. Then e(m,n)=1+(1/(mn))Sum[e(m,n),{j,1,m-1},{k,1,n-1}], for m,n>1, and e(m,1)=1, e(1,n)=1. I wonder whether there is an explicit formula for e(m,n). –  Martin Erickson Jun 28 '10 at 16:28

1 Answer 1

Dear Prof. Erickson, Please look at this link: http://tea.mathoverflow.net/discussion/474/

I will post this and then check whether the link really works.

William C. Jagy

share|improve this answer

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.