I have a problem that maps to estimating the discrete distance to a goal.
The sample space is n discrete positions on a circle labeled sequentially; n is known. A target position is randomly selected, then random positions on the circle are independently selected by k persons. All positions are selected uniform distribution. What is the expected distance from the target to the closest position selected preceding the target?
Because both the target and the sample points are random, I'm thinking we can just fix the target at n, and estimate the maximum position selected.
This seems like, k balls numbered 1 thru n; n is known. Sample with replacement k balls. For a given k, what is the expected largest ball number?
I've done this in simulation and get n-(k/n) as the max, (k/n) as the distance, but I'm having a problem relating this to probability principles to justify.
Any thoughts?
Mika
Suppose the points are the vertices of a regular $n$-gon with side $1$. Let $T$ be a particular fixed vertex. If $V$ is any vertex, we let $d(V)$ be the distance from $V$ to $T$, if we are constrained to travel counterclockwise around the $n$-gon.
Let random variable $X$ be the minimum value of $d(V)$ among the vertices chosen by the $k$ people. We will find the distribution of $X$, with a view to computing $E(X)$.
One could write down $\Pr(X=0)$, but since it will play no role in the expectation calculation, there is no need to do so.
The probability that a randomly chosen $V$ is distance $\ge 1$ from $T$ is $\frac{n-1}{n}$. So the probability all $k$ are at distance $\ge 1$ from $T$ is $\frac{(n-1)^k}{n^k}$. It follows that the probability $\Pr(X=1)$ that the minimum distance of the $k$ chosen points from $T$ is exactly $1$ is given by $$\Pr(X=1)=\frac{(n-1)^k}{n^k}-\frac{(n-2)^k}{n^k}.$$ By similar reasoning, $$\Pr(X=2)=\frac{(n-2)^k}{n^k}-\frac{(n-3)^k}{n^k},$$ and so on, until finally $$\Pr(X=n-1)=\frac{1^k}{n^k}.$$ We now calculate the expectation of $X$. It is $$\small 1\cdot\left(\frac{(n-1)^k}{n^k}-\frac{(n-2)^k}{n^k} \right) + 2\cdot\left(\frac{(n-2)^k}{n^k}-\frac{(n-3)^k}{n^k} \right) + 3\cdot\left(\frac{(n-3)^k}{n^k}-\frac{(n-4)^k}{n^k} \right) + \cdots+(n-2)\cdot\left(\frac{2^k}{n^k}-\frac{1^k}{n^k} \right) +(n-1)\cdot \frac{1}{n^k}.$$ The above sum simplifies greatly, to $$E(X)=\frac{1}{n^k}\left((n-1)^k+(n-2)^k+(n-3)^k +\cdots +2^k+1^k\right).$$
For large $n$, the above expression is approximately equal to $\frac{1}{k+1}$.
Remark: We calculated the expected minimum distance to target, since that seemed to be the motivating problem. A similar calculation can be made for the largest expected ball number.