Before revision:  When the arrangement is obtained from any fixed projective line arrangement of n lines by choosing a random cellto contain the south-pole, we prove an upper bound of O((k+1)^2) on the expected complexity of the k-level . As a byproduct we show that the complexity of any (\leq j)-zone in a d-dimensional simple arrangement of n hyperplanes is of order \Theta((j+1)n^{d-1 We also consider arrangements of great (d-1)-spheres on the sphere \mathbb{S}^d which are orthogonal to a set of random points on \mathbb{S}^d.
After revision:  When the arrangement is obtained from any fixed projective line arrangement of n lines by choosing a random cellto contain the south-pole, we prove an upper bound of O((k+1)^2) on the expected complexity of the k-level in great-circle arrangements if the south pole is chosen uniformly at random among all cells. We also consider arrangements of great (d-1)-spheres on the sphere \mathbb{S}^d which are orthogonal to a set of random points on \mathbb{S}^d.