Usually such average cases must be seen w.r.t. some underlying distribution. That is, we say "assuming that the inputs are distributed according to xxx", wherein xxx can be uniform distribution or something else.

What is the purpose of this analysis? That will tell us which distribution to take.

The following is a link to an earlier randomized kd-tree (1998). 

http://link.springer.com/chapter/10.1007/3-540-49381-6_22#page-1

Also, page-21of the attached file might be useful.

Hope this helps.