1
$\begingroup$

As a preface, this is related to a graph of $n+1$ nodes, which is generated through (equally likely) random attachments to existing nodes - this occurs in $n$ "stages" of attachment. Suppose that we have a set of $k= $ $n \choose 2$ discrete random variables $X_{i} \in \{1,...,n\}$ (for $1 \leq i \leq k$) that are identically distributed, but not independent, and for which we know the marginal distribution (presumably the frequency function, which we will call $f_{X}$, but you can use the moment generating function $M_{X}$ or the cumulative distribution function $F_{X}$ if absolutely necessary) for any given $X_{i}$ and the joint distribution (call its frequency $f$, the moment generating function $M$, and the cumulative distribution function $F$). We need to find the expected value of the maximum of this set. In other words, we should compute $$\mathbb{E}( \text{max}\{{X_{1},X_{2},...,X_{k}\}}).$$ An approximation for large $n$ would also be helpful. I believe that this should involve the distribution of order statistics coupled with the known distribution, but I'm not quite sure what approach to take here. The reason I am asking is because I am generally unfamiliar with order statistics, especially in regards to expectation, although I have seen some derivations of the distribution of these random variables with some independence assumptions and some proofs involving order statistics, specifically in the texts $\textit{A First Course in Probability}$ by Sheldon Ross (Chapter $6$) and $\textit{Mathematical Statistics and Data Analysis}$ by John Rice (Chapter $3, 4$). For instance, I have shown that the expectation of the $j$th-order statistic of a sample of $n$ independent random variables $(X_{1},X_{2},...,X_{n})$ uniform on $[0,1]$, which we denote $X_{(j)}$, is given by $$\mathbb{E}(X_{(j)})=\frac{j}{n+1},$$ where $X_{(1)} \leq X_{(2)} \leq \,... \leq X_{(n)}$. Indeed, the marginal distributions are of the Beta family, which is where the result comes from.

It might be useful to have the following fact, although it is not completely applicable here. Suppose $X_{1},X_{2},...,X_{n}$ are i.i.d. discrete random variables with CDF $F$ and PMF $f$. Consider the set of order statistics $\{X_{(i)} \,|\, X_{(i)}=X_{j} \,\,\text{for some}\,\, 1 \leq i,j \leq n, \,\, X_{(1)} \leq X_{(2)} \leq \,... \leq X_{(n)}\}$. The PMF of the $k$th-order statistic, $X_{(k)}$, is given by $$P(X_{(k)}=x)=\sum_{j=1}^{n-k} {n \choose j} (\,(1-F(x))^{j}(F(x))^{n-j}-(1-F(x)+f(x))^{j}(F(x)-f(x))^{n-j}\,)$$

If clarification is needed for the question at hand, I can add to this post and answer questions below. I am looking for a closed form general solution, if possible. In our case, with the above notation, we are trying to determine $$\mathbb{E}(X_{(k)}),$$ where it is implicit that $X_{(k)}=\text{max}\{X_{1},X_{2},...,X_{k}\}$ from the definition of these order statistics.

$\endgroup$
  • 1
    $\begingroup$ If they're not independent, is there a specific manner in which they're dependent? $\endgroup$ – jschnei Apr 25 '14 at 7:19
  • $\begingroup$ What does it mean to say that $X_5$, for instance, is the $max(X_0, X_1, ..., X_n)$ ? $\endgroup$ – BCLC Apr 25 '14 at 7:29
  • $\begingroup$ The complexities of their dependence is more than I want to disclose, so just assume a general dependence (in other words, include a covariance between $X_{i}$ and $X_{j}$ if necessary in the calculation, or whatever else is necessary to generalize the result). In regards to your question BCLC 8, it is the standard meaning of maximum, the largest value in the set...each of the random variables is assigned a number, for a given event, and the maximum is the largest of these numbers. You can assume that the input event to each of the random variables is the same. $\endgroup$ – afedder Apr 25 '14 at 15:39
  • $\begingroup$ To give you more insight that might help, the random variables return the length of path between two distinct nodes, which I have proved to be unique, in an undirected (and specific kind of) network of $n+1$ nodes. $\endgroup$ – afedder Apr 25 '14 at 16:38
  • $\begingroup$ I am afraid the bounty will not change the fact that, for lack of specificity, this is not a real question--but, true enough, it does prevent it from being closed. $\endgroup$ – Did Apr 27 '14 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.