Let X1,X2,X3... be an endless sequence of random variables, uniformly distributed on the set {1,2,3....10}. Index i will be called "King" if X_i is greater than all of the numbers before it in the sequence. Calculate the expected value of the number of indices that are to be crowned Kings.
please help.
On
A term whose index is what you call a "king" is ordinarily called a record, so you are asking for the expected number of records in an iid sequence of Uniform$\{1,...,m\}$ random variables, e.g. with $m=10$. (This assumes the terms are mutually independent.)
The probability that the $k$th distinct term is a record is ${1\over k},$ and the number of records in the infinite sequence can be written as the sum of indicators $$\begin{align}\sum_{k=1}^m \mathbb{1}_{\text{$k$th distinct term is a record}} \end{align}$$
so the expected number of records in the infinite sequence is
$$\begin{align} E\left(\sum_{k=1}^m \mathbb{1}_{\text{$k$th distinct term is a record}} \right)&=\sum_{i=1}^m E(\mathbb{1}_{\text{$k$th distinct term is a record}})\\[2ex] &=\sum_{k=1}^m{1\over k}\\[2ex] &=H_m \end{align}$$
where $H_m=\sum_{k=1}^m{1\over k}$ is the $m$th harmonic number. (E.g., $H_{10}={7381\over 2520}$.)
The probability that the $i$th term is a record is $$\begin{align}P_i&=\sum_{k=1}^mP((X_i=k)\cap(X_{j}< k \text{ for all }j<i)) \\[2ex] &=\sum_{k=1}^m{1\over m}\left({k-1\over m}\right)^{i-1} \end{align}$$ and the number of records in the infinite sequence can be written as the sum of indicators $$\begin{align}\sum_{i=1}^\infty \mathbb{1}_{\text{$X_i$ is a record}} \end{align}$$
so the expected number of records in the infinite sequence is
$$\begin{align} E\left(\sum_{i=1}^\infty 1_{\text{$X_i$ is a record}}\right)&=\sum_{i=1}^\infty E(1_{\text{$X_i$ is a record}})\\[2ex] &=\sum_{i=1}^\infty P_i\\[2ex] &=\sum_{i=1}^\infty\sum_{k=1}^m{1\over m}\left({k-1\over m}\right)^{i-1}\\[2ex] &= {1\over m}\sum_{i=1}^\infty\sum_{k=1}^m\left({k-1\over m}\right)^{i-1}\\[2ex] &={1\over m}\sum_{k=1}^m\sum_{i=1}^\infty\left({k-1\over m}\right)^{i-1}\\[2ex] &={1\over m}\sum_{k=1}^m{m\over m-k+1}\\[2ex] &={1\over m}(m\cdot \sum_{j=1}^m{1\over j})\\[2ex] &=H_m. \end{align}$$
On
Given an infinite sequence of uniform draws from {1,...,10}, since we are only counting records, there is nothing changed by deleting any draw that is equal to a previous draw -- the number of records will be the same.
The edited sequence is finite, and with probability 1, is a linear ordering of {1,...,10} (since the probability is $0$ that any value is omitted in the original infinite sequence). By iid uniform, all $10!$ such orderings are equally likely .
Looking at a random ordering of {1,...10}, the expected number of (left-to-right) records in location $j$ is $1/j$, since among the first $j$ entries, each one of them is equally likely to be the maximum among them.
Using linearity of expectation the expected number of records in the original sequence will be $1 + 1/2 + 1/3 + .... + 1/10$.
This problem can be modeled using an absorbing Markov chain. Let $\{Y_n:n\geqslant 1\}$ be defined by $Y_1$ uniformly distributed over $\{1,\ldots,10\}$ and for $n\geqslant 1$: $$ \mathbb P(Y_{n+1}=j\mid Y_n=i)=\begin{cases} \frac1{10-i},& i<j\leqslant 10\\ 1,& i=j=10. \end{cases} $$ Let $P$ be the transition matrix of this Markov chain, then $$P=\pmatrix{Q&R\\0&I} $$ where $Q$ is the substochastic matrix corresponding to transitions between transient states, $R$ that corresponding to transitions from a transient state to an absorbing state, and $I$ that corresponding to transitions between absorbing states. (Here we have only one absorbing state.) For pair of transient states $i,j$ the probability of transitioning from $i$ to $j$ in exactly $k$ steps is the $(i,j)$ entry of $Q^k$. Summing for all $k$ yields the fundamental matrix $$ N = \sum_{k=0}Q^k. $$ Since the rows of $Q$ sum to strictly less than one, the Neumann series converges and we have $N=(I-Q)^{-1}$, with $I$ the identity matrix. The expected number of transitions until being absorbed starting in transient state $i$ is the $i^{\mathsf{th}}$ entry of the vector $t=N\cdot\mathbf 1$, where $\mathbf 1$ is a column vector whose entries are all one. Here $$ t=\left( \begin{array}{c} \frac{9649}{2520} \\ \frac{1041}{280} \\ \frac{503}{140} \\ \frac{69}{20} \\ \frac{197}{60} \\ \frac{37}{12} \\ \frac{17}{6} \\ \frac{5}{2} \\ 2 \\ \end{array} \right), $$ and since the initial distribution was uniform over $\{1,\ldots,10\}$, we weight each of these entries, along with $1$ (for the case when $X_1=10$), by $\frac1{10}$ and sum to obtain $$\frac{7381}{2520}. $$