6

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.

afedder
  • 2,102

1 Answers1

2

(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*}

Mick A
  • 10,208
  • I don't think your answer is correct for the distribution of $S_i$. Indeed, not every agent $i$ can evaluate themselves at every point on the terrain, so the second equality that you have is incorrect. They each have different heuristics $h_i$ and can only evaluate themselves on points that are their heuristic steps away from each starting point $m$, or am I missing something? – afedder Dec 17 '14 at 02:27
  • Or will they eventually evaluate at every point on the terrain? This is unclear to me. – afedder Dec 17 '14 at 02:29
  • I think the equality I have is OK. Let's say the max of the $p_m$ occurs when $m=a$. That is, for some $1 \leq a\leq 2000,; p_a=\max\limits_{1\leq m \leq 2000}{p_m}$. Then for all $i,; X_i^a= max{p_a,p_a^{'}}=p_a$. So $X_i^a$ is the maximum of all the $X_i^m,$ for $1\leq m\leq 1000$, and we have $S_i=X_i^a=p_a$ which means $S_i=\max\limits_{1\leq j \leq 2000}{X_i^j}=\max\limits_{1\leq m \leq 2000}{p_m}$. The question of "every pt on the terrain?"... $S_i$ takes the maximum $X_i^m$ over all $1\leq m\leq 2000$ so that in effect means we consider all values $p_m$ on the terrain. – Mick A Dec 17 '14 at 09:36
  • But $X_i^m$ is different for every individual $i$ because each individual has a different heuristic, so that $p_m'$ is different for every individual when they start at $p_m$. – afedder Dec 17 '14 at 18:59
  • Actually I guess what you said makes sense, but it just seems too simple for me to accept. I'm lost as to why the heuristic doesn't matter here. – afedder Dec 17 '14 at 19:01
  • This would mean that every individual has the same score ($S_i$ is the same for each agent $i$) since the terrain and hence the maximum $p_m$ on the terrain is fixed. This doesn't make sense. – afedder Dec 17 '14 at 19:57
  • Perhaps something wrong in the definition of $S_i$? Because you're right, every $S_i$ is the same. Can you try an actual numerical example with smaller numbers? Maybe 6 or 8 instead of 2000, and max integer 10 instead of 100? Choose a "random" set of 8 numbers, then show what $S_1, S_2, S_3, \ldots$ are. Then we can see what's supposed to happen. – Mick A Dec 17 '14 at 23:11
  • Now that I think about it, the $S_i$ are all the same in the case of one heuristic I have presented. This is not what I was aiming for - I was simplifying the general problem, where each individual has $k$ heuristics (say $3$) and they cycle through them to find the maximum point that they can reach starting from each marker on the terrain. – afedder Dec 18 '14 at 00:01
  • So suppose an agent $i$ has heuristics $h_{i1},h_{i2},h_{i3}$. Then they begin at a marker $m$ and evaluate if the marker $h_{i1}$ steps to the right of $m$ is greater than the point value at $m$. If it is, they move to that marker and evaluate again using the second heuristic $h_{i2}$. If it is not, they stay at that marker and evaluate with the second heuristic $h_{i2}$. And so on. They do this until they find the maximum possible point value that they can attain with their heuristic set. This is $S_i$. – afedder Dec 18 '14 at 00:12
  • Oh Ok. With that situation, $S_i$ is the maximum of $k$ values from the set of $p_m$s. Depending on the result of each heuristic in turn, it will be a different set of $k$ numbers, but since the distribution of each $p_m$ is the same, it doesn't affect our calculation. So the calculation of $P(S_i=x)$ now is the same as I have above but replacing $2000$ with $k$. One question: is it the same $k$ for all $i$ or can it be that, for example, $S_1$ has $k=3$ heuristics, $S_2$ has $k=5$ heuristics, $S_3$ has $k=2$ heuristics, etc? – Mick A Dec 18 '14 at 09:21
  • No, each agent has the same number of heuristics $k$. But they all have a distinct heuristic set. It is the same calculation even if the terrain is fixed? The specific heuristic set should affect the score of agent $i$. Not all scores would be the same. – afedder Dec 18 '14 at 11:23
  • Yes, not all scores would be the same, so it's making more sense now. But all $S_i$ have the same distribution unless agent $i$ has a heuristic making it possible for it to wrap around and compare the same $p_m$ as an earlier heuristic for that agent. E.g. if $k=2$ and $h_{i1}=1500, h_{i2}=500$ and we began with $m=5$, we'd possibly compare $p_5, p_{1505}$ and $p_5$ again. It'd be nice if that was impossible. Then we can say $P(S_i = x) = \left(\dfrac{x}{100}\right)^{k} - \left(\dfrac{x-1}{100}\right)^{k}$ for all $i$. – Mick A Dec 18 '14 at 11:50
  • It does wrap back around. In fact, it continues cycling through the heuristics and the terrain until it reaches the maximum value that it can possibly attain with the given heuristics. I feel like this should complicate things, but maybe I'm thinking about it too much. – afedder Dec 18 '14 at 23:32
  • See if I understand: Say $k=2$ and $h_1=4,h_2=5$. We have $8$ instead of $2000$ integers with max $10$, not $100$. Ex.1 $\mathcal{T_1}={3,7,1,8,9,2,5,4}$. Start with $m=2$. So we compare in turn: 7,2 --> 7 then 7,5 --> 7 then back to 7,2 --> 7. That's repeating so $S_1=7$. Ex.2 Same set of 8 numbers and heuristics. But start this time with $m=3$. So we compare in turn: 1,5 --> 5 then 5,8 --> 8 then 8,4 --> 8 then 8,3 --> 8. Here we're repeating so $S_2=8$. Is this right? If not can you add correct examples? Thanks... – Mick A Dec 19 '14 at 09:03
  • This is completely correct @MickA – afedder Dec 22 '14 at 07:57
  • Could you update your answer for that? – afedder Dec 22 '14 at 07:58
  • I have updated the question, by the way. – afedder Dec 22 '14 at 08:09
  • Would you mind reviewing the question again? ... $X_i^m$ is no longer defined. Also check that the definition of $S_i$ is what you mean. – Mick A Dec 22 '14 at 11:54
  • Done @MickA. What you have given as an example above for $S_i$ is correct and also I added $X_i^m$, although this is clear, right? $X_i^m$ is just the maximum value that can be attained with each starting point $m$ and heuristic set for an agent $i$, $H_i$. – afedder Dec 23 '14 at 08:42
  • Thanks @afedder. I'll think more about dist'n of $X_i^m$. But part (b) is OK as is, given the defn of $S_i$. $S_i$ will always be the maximum value of the $p_m's$. Because say the max $p_m$ is when $m=b$. Then $X_i^b = p_b$ so $S_i = p_b$. But from your previous comments, this is not your intention, because then $S_i$ is not doing its job as a measure/score of agent $i$. Should it be more along the lines of: $S_i$ is the number of $m$ values for which $X_i^m = p_b$? This measures the ability of the agent to locate the maximum $p_m$ value using all $2000$ starting points. ... just a thought. – Mick A Dec 23 '14 at 14:39
  • Using your example, this was not the case, though. @MickA The maximum of $\mathcal{T}_1$ was $9$, but $S_1 = 7$ and $S_2 = 8$. I'm pretty sure my definition of $S_i$ reflects this example, but please inform me if it does not. You said that $S_i$ would be different for each agent $i$, but now you say it wouldn't be different (the maximum of the point values on the terrain). – afedder Dec 23 '14 at 19:58
  • Sorry, it looks like my example was wrong. I'll try again. Say $k=2$ and $h_{1_1}=4,h_{1_2}=5$. $T={3,7,1,8,9,2,5,4}$. Ex.1 Start with $m=2$. We compare in turn: 7,2 --> 7 then 7,5 --> 7 then back to 7,2 --> 7. That's repeating so $X_1^2=7$. Ex.2 Now start with $m=3$. We compare in turn: 1,5 --> 5 then 5,8 --> 8 then 8,4 --> 8 then 8,3 --> 8. So $X_1^3=8$. Now we'll also have $X_1^5=9$ obviously. This means $S_1=\max{X_1^1,X_1^2,X_1^3,X_1^4,X_1^5,X_1^6,X_1^7,X_1^8}=9$. That's what I meant in my last comment. – Mick A Dec 23 '14 at 21:34
  • Yes and $\max{p_m \in \mathcal{T}} = 9$ as well. But is this always true? - what if we take a larger terrain, say $\mathcal{T}'$ with $m \in {1,2,...,2000}$ with each agent $i$, $H_i = {h_{i1}, h_{i2}, ..., h_{ik}}$ for some $k \in \mathbb{N}$. – afedder Dec 24 '14 at 06:47
  • You still have $S_i = \max{X_i^{1},X_i^{2},...,X_i^{2000}}$. It's maximising $X_i^m$ over EVERY $m$. So it is always true. – Mick A Dec 24 '14 at 07:05
  • You're right, that's not what I looking for, let me edit that – afedder Dec 24 '14 at 10:33