# Expected Number of Jumps

I have a problem in solving a problem by probabilistic methods

The problems is the following.

There are $n$ vertices $x_1..x_n$ connected by a circle. Every vertex $x_i$ has unique identifier $u_i$. Simultaneously, each vertex $x_i$ send a token $t_i$ with $u_i$ as the content of the token in clockwise direction. When a token $t_i$ arrives to vertex $x_j$ it compares $u_i$ and $u_j$, and if $u_j > u_i$, $x_j$ captures $t_i$, if $u_i > u_j$, token $t_i$ keeps traveling. It's obvious that at the end only one token $t_w$ encloses the circle at it's initial position $x_w$, all others are captured. All $\{u_1..u_n\}$ is just random permutation.

The question is what is expected value of number of jumps of all tokens (jump is when the token passes the vertex, so $u$ of token is bigger that $u$ of vertex).

$X$ - number of jumps of all tokens.

$X_i$ - number of jumps of token $t_i$,

$E(X) = \sum_{i=1}^{n} E(X_i)$

$E(X_i) = \sum_{j=1}^{n} j*$Pr($t_i$ makes j jumps)

The problem is I cannot derive $E(X_i)$.

Following is my wrong version of $E(X_i)$:

$E(X_i) = \sum_{j=1}^{n} j*$Pr($t_i$ makes $j$ jumps) = $1*\frac{1}{2} + 2*\frac{1}{4}+..$

What is the probability that the token will make two jumps and more?

Will appreciate for any help!

-
Which uniform distribution do the $u_i$ have? – Mike Spivey Feb 2 '13 at 21:35
@MikeSpivey, sorry my mistake, all $u$ is just random permutation – fog Feb 3 '13 at 4:36

Assume that the distribution of $(u_i)_{1\leqslant i\leqslant n}$ is exchangeable with no ties, for example because $(u_i)_{1\leqslant i\leqslant n}$ is i.i.d. with a continuous distribution.
For every $1\leqslant k\leqslant n-1$ and every vertex $x$, the token initially at $x$ crosses $x+k$ iff it is maximal amongst the tokens in the integer interval $\{x,x+1,\ldots,x+k\}$ counted clockwise. By exchangeability, this happens with probability $\frac1{k+1}$. There are $n$ such couples of vertices at distance $k$. Hence the mean total number of jumps is $$\mathbb E(X)=n\sum_{k=2}^n\frac1k.$$ Sanity checks: If $n=2$, one token crosses $1$ site and the other token crosses no site hence $$\mathbb E(X)=1+0=1=2\cdot\frac12.$$ If $n=3$ and the tokens are $u\lt v\lt w$, then $w$ crosses $2$ sites, $u$ crosses $0$ site, and $v$ crosses either $1$ or $0$ site, with equal probabilities, hence $$\mathbb E(X)=2+0+\frac12(0+1)=\frac52=3\left(\frac12+\frac13\right).$$
Thank you very much, but I still have a few questions. $\mathbb{E}(X_i)=\sum_{k=2}^{n} \frac{1}{k}$, and I tried to express it in the form $\mathbb{E}(X_i)=\sum_{k=1}^{n} k*Pr$(token i makes k steps), still how can express $\mathbb{E}(X_i)$ in the classic form, like I started? What is exchangeability, and how it can be applied here? Explanation from wikipedia didn't help. – fog Feb 5 '13 at 11:11
The point of the method is precisely to avoid computing each $E(X_i)$. // Exchangeability means that the distribution of $(u_{\sigma(i)})_{1\leqslant i\leqslant n}$ is equal to the distribution of $(u_i)_{1\leqslant i\leqslant n}$, for every permutation $\sigma$ of $\{1,2,\ldots,n\}$. For simplicity, one can stick to the condition of being i.i.d. – Did Feb 5 '13 at 15:23