Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 2 down vote accepted

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). $$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.