1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ 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. $\endgroup$
    – Keenan Kidwell
    Commented Jun 26, 2010 at 13:03
  • 11
    $\begingroup$ They all seem to be from here: www2.truman.edu/~erickson/openproblems.html $\endgroup$
    – j.c.
    Commented Jun 26, 2010 at 14:03
  • $\begingroup$ 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). $\endgroup$
    – Martin Erickson
    Commented Jun 28, 2010 at 16:28

1 Answer 1

Reset to default
1
$\begingroup$

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

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

William C. Jagy

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .