scores of individuals and evaluation

Question

Suppose we have a fixed (ordered) set of $2000$ integers $p_m$ drawn from a discrete uniform distribution on $\{1,2,...,100\}$ arranged in a terrain. Let this terrain be denoted $\mathcal{T} = \{p_1,p_2,...,p_{2000}\}$. We also have $N = {\ell \choose k}k!$ agents, where each agent $i$ has a unique heuristic set $H_i = \{h_{i1},h_{i2},h_{i3},...,h_{ik}\}$ for some $k, \ell \in \mathbb{N}$.

First, note that the process about to be outlined "loops," i.e. if a step is a movement from one value on the terrain to the next, then, for example, $10$ steps to the right of the value at $1995$ is the value at $5$. Also, the heuristics and the terrain are cycled through. Now, each agent $i$ does the following:

$1$) For each $m \in \{1,2,...,2000\}$, the agent begins at $m$ which is associated with some value $p_m$ and checks whether the value $h_{i1}$ steps to the right of $m$ is larger than $p_m$. If it is, the agent moves to this marker. If it is not, he stays at the starting marker. Then he checks whether the value $h_{i2}$ steps to the right of this marker is larger than this value. If it is, he moves there, and if it is not, he remains where he was. Then he evaluates with $h_{i3}$, and so on. This process continues (the agent loops through his heuristics, evaluating all the points on the terrain that he can with his set) until the agents reaches the maximum point value he can attain given $H_i$ and $\mathcal{T}$. We denote this maximum value $X_i^m$ for each starting marker $m$ and each agent $i$.

$2$) The agent then scores himself by determining $S_i = \min\{X_i^{1},X_i^{2},...,X_i^{2000}\}$ and $S_i^{\text{avg}} = \frac{1}{2000}\sum_{j=1}^{2000} X_{i}^{j}$.

We want the distribution of $X_i^{m}$, the distribution of $S_i$, and the distribution of $S_{i}^{\text{avg}}$ for each individual $i$ and each starting point $m$ (does $X_i^m$ actually depend on $m$ or $h_i$?). Any relevant contribution or even hints in the right direction would be very much appreciated.

Answer 1

(a) Distribution of $X_i^m$.

Let $I=\{1,2,\ldots,100\}$. For any $x\in I$,

\begin{eqnarray*} P(X_i^m=x) &=& P \left(\left[(p_m=x) \cap (p_m^{'} \leq x)\right] \cup \left[(p_m\leq x) \cap (p_m^{'} = x)\right]\right) \\ && \\ &=& P((p_m=x) \cap (p_m^{'} \leq x)) + P((p_m\leq x) \cap (p_m^{'} = x)) - P((p_m=x) \cap (p_m^{'} = x)) \\ && \\ &=& 2\left(\dfrac{1}{100} \dfrac{x}{100}\right) - \left(\dfrac{1}{100}\right)^2 \\ && \\ &=& \dfrac{2x-1}{10000}. \end{eqnarray*} $\\$

(b) Distribution of $S_i$.

$S_i = \max\limits_{1\leq j \leq 2000}\{X_i^j\} = \max\limits_{1\leq m \leq 2000}\{p_m\}$.

Therefore, for any $x\in I$,

\begin{eqnarray*} P(S_i = x) &=& P\left[\left(\bigcap_{m=1}^{2000}{(p_m\leq x)}\right) \bigg\backslash \left(\bigcap_{m=1}^{2000}{(p_m\leq x - 1)}\right)\right] \\ && \\ &=& P\left[\bigcap_{m=1}^{2000}{(p_m\leq x)}\right] - P\left[\bigcap_{m=1}^{2000}{(p_m\leq x - 1)}\right] \\ && \\ &=& \left(\dfrac{x}{100}\right)^{2000} - \left(\dfrac{x-1}{100}\right)^{2000}. \end{eqnarray*}

$\\$

(c) Calculating the distribution of $S_i^{avg}$ looks hard. I don't have an answer for that.

---

NOTE (25/12/2014): Above is the original answer: no longer valid for the question as it is now.

(a) Distribution of $X_i^m$.

This depends largely on the number of values from $\mathcal{T}$ the agent $i$ gets to compare for the given starting point $m$. So let $M_i^m$ be this number of $p_m$ values that are compared by agent $i$ starting at position $m$. The longer the heuristic runs, the higher is $M_i^m$, and the higher is the expected value of $X_i^m$.

My approach is to calculate the expected value of $M_i^m$ then use the method in (b) above to calculate the probability $P(X_i^m = x)$.

I'll make some assumptions here to simplify the problem:

1. There is no "wrapping around" in $\mathcal{T}$ so that the same values are encountered because we've moved to the right over $2000$ places. Except for large $k$, I think this is reasonable.
2. I'll ignore the fact that in each step of the heuristic, as we move to the right, one or more of the $m + h_{i_j}$ values could be the same as a $m + h_{i_j}$ in a previous step, which would mean we're re-comparing the same number.

At a given step in the heuristic, the current "marker" (i.e. the highest $p_m$ value so far) is more likely to remain the higher number in future comparisons in proportion to the number of previous $p_m$ values that have been compared. I'll call this number of previous $p_m$ values $c$. This $c$ starts at $0$ when we begin the process at the first marker $m$.

When we have established a new marker in the process, in the next step of using our $k$ heuristics, we are essentially finding the highest of $k+1$ $p_m$ values: $p_m,p_{m+h_{i_1}},\ldots,p_{m+h_{i_k}}$.

Example: Say $k=2, m=5, h_{i_1}=4, h_{i_2}=6$. Then at the next step we are finding the biggest value of $p_5, p_9, p_{11}$. If that is $p_5$ we are "stuck" and the process terminates. If instead it is $p_9$, then we move to the next step with $m=9$ (and $c$ increasing by $2$ accounting for the fact we've already compared $p_5$ and $p_{11}$) where we repeat this process.

We'll calculate the expected value of $M_i^m$ recursively. To this end, define the function $f(k,c)$ as the expected value of $M_i^m$ given that $c$ other $p_m$ values have already been compared (and are therefore less than the $p_m$ value at current marker $m$). Then,

\begin{eqnarray*} f(k,c) &=& P(\text{Stuck on current $m$})(k+1) + \sum_{n=1}^k{P(h_{i_n} \text{ heuristic "works"}) \left(n + f(k,c+n)\right)} \\ &=& \dfrac{(c+k)! (k+1)}{(c+k+1)!/(c+1)} + \sum_{n=1}^k{\dfrac{(c+1)(n + f(k,c+n))}{(c+n)(c+n+1)}} \\ &=& \dfrac{(c+1)(k+1)}{c+k+1} + \sum_{n=1}^k{\dfrac{(c+1)(n + f(k,c+n))}{(c+n)(c+n+1)}}. \end{eqnarray*}

Reasoning for that second line:

$P(\text{Stuck on current $m$})$: The denominator $(c+k+1)!/(c+1)$ : there are $(c+k+1)!$ arrangements of $c+k+1$ numbers, of which $1/(c+1)$ of them have the marker as larger than the other $c$ numbers. The numerator $(c+k)!$ : there are $(c+k)!$ arrangements of $c+k+1$ numbers with the marker larger than the other $c+k$ numbers.

$P(h_{i_n} \text{ heuristic "works"})$: The denominator $(c+n+1)!/(c+1)$ : there are $(c+n+1)!$ arrangements of $c+n+1$ numbers, of which $1/(c+1)$ of them have the marker as larger than the other $c$ numbers. The numerator $(c+n-1)!$ : there are $(c+n-1)!$ arrangements of $c+n+1$ numbers with $p_{m+h_{i_n}}$ the largest and the marker the second largest.

There's no easy way of solving this recurrence relation. The best thing is to write a program to calculate its value for given $k$ and with $c=0$. I did this and some approximate values are:

\begin{eqnarray*} f(1,0) &=& 2.718 \\ f(2,0) &=& 4.482 \\ f(3,0) &=& 6.255 \\ \end{eqnarray*}

With this we use the working in (b) above to say that for any $x\in I$:

\begin{eqnarray*} P(X_i^m = x) &=& \left(\dfrac{x}{100}\right)^{f(k,0)} - \left(\dfrac{x-1}{100}\right)^{f(k,0)}. \end{eqnarray*}