Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Say first we have N distinct numbers in a line, like 1,2,3,...,N, in each round, we choose a random one from the last N numbers, and put it in the end.

Asking the expected number of rounds to make the last N numbers the same.

e.g. for N = 2, first we have

1, 2

and if we chose 1, we got

1, 2, 1

and the status stays the same, since the last N numbers still all distinct. and if we chose 2, we got

1, 2, 2

and the game ends.

Suppose the expected number is S, we can write

S = 1/2 * (S + 1) + 1/2 * (1)

and we get S = 2

Things become very complicated when N > 2, so I turn for help.

UPDATE:

this occurs to me when doing a project, see this if you are interested in.

and i just wanna know whether it can be solved in a graceful way, or in a hard way but get the answer finally, so i don't need a numeric answer.

share|improve this question
    
There probably isn't a clean way to do this. Have you considered trying a computer simulation? What do you need this for? –  Potato Aug 21 '12 at 2:21
    
@Potato see updates –  Topro Aug 21 '12 at 2:33
    
Hard question. (Plus removed the tag infinity) –  FrenzY DT. Aug 21 '12 at 2:42
    
@FrenzYDT.i thought the state transition is infinite, maybe misunderstanding of the word. –  Topro Aug 21 '12 at 2:50
2  
From a simulation of $1000000$ trials for each value of $N$, the first few values (starting from $N=2$) are $1.999$, $4.751$, $8.419$, $13.08$, $18.73$, $25.41$, $33.06$ (where the errors are in the last digit). The dominant behavior seems to be $\langle T \rangle \sim N^2/2$. –  mjqxxxx Aug 21 '12 at 5:17

3 Answers 3

up vote 5 down vote accepted

This is not a solution, but it might be helpful, and it is too long for a comment.

Your $N^N$ equations can be simplified, because you can exploit symmetry in the structure of the problem. Say that $L(S)$ is the expected number of rounds for the game to end after reaching state $S$, where $S$ is some string of length $N$. Then:

$$ \begin{eqnarray} L(AA)=L(BB)&=&0\\ L(AB)& =& 1+\frac12(L(BB)+L(BA)) \\ L(BA)& =& 1+\frac12(L(AA)+L(AB)) \\ \end{eqnarray} $$

Notice that the equations for $L(AB)$ and $L(BA)$ are identical, except that $A$ and $B$ have exchanged places. So by symmetry, $L(AB)=L(BA)$, and we get:

$$L(AB)=1+\frac12L(AB)$$

So $L(AB) = L(BA) = 2$. This tells us that the game ends in 2 steps (on average) from both these states.


Now we can consider the $N=3$ case.

$$ \begin{eqnarray} L(AAA)=L(BBB)=L(CCC)&=&0\\ L(ABC)&=&1+\frac13(L(BCA)+L(BCB)+L(BCC))\\ L(AAB)&=&1+\frac13(L(ABA)+L(ABA)+L(ABB)) \\ L(ABA)&=&1+\frac13(L(BAA)+L(BAB)+L(BAA))\\ L(ABB)&=&1+\frac13(L(BBA)+L(BBB)+L(BBB)) \\ &\vdots& \end{eqnarray} $$

This looks awful, but remember we can simplify. There aren't 27 variables here; there are only five:

$$ \begin{eqnarray} L(AAA)&=&L(BBB)=L(CCC)\\ L(ABC)&=&L(ACB)=L(BAC)=\cdots=L(CBA)\\ L(ABA)&=&L(ACA)=L(BAB)=\cdots=L(CBC)\\ L(AAB)&=&L(AAC)=L(BBA)=\cdots=L(CCB)\\ L(ABB)&=&L(ACC)=L(BAA)=\cdots=L(CBB) \end{eqnarray} $$

This allows us to reduce the original set of 27 equations in 27 variables to five equations in five variables:

$$ \begin{eqnarray} L(AAA)&=&0\\ L(ABC)&=&1+\frac13(L(ABC)+L(ABA)+L(ABB))\\ L(AAB)&=&1+\frac13(L(ABA)+L(ABA)+L(ABB)) \\ L(ABA)&=&1+\frac13(L(ABB)+L(ABA)+L(ABB))\\ L(ABB)&=&1+\frac13(L(AAB)\hphantom{+L(AAA)+L(AAA)}) \end{eqnarray} $$

I tried solving these with pen and paper and got $L(ABC)=\frac{27}{4} = 6\frac34$. I might have made a mistake, of course; it is after midnight. But as a proof of concept I think it was a success.

Anyway, I think the technique is reasonable, and it will reduce your unmanageable 10,000,000,000 equations to a much smaller set, maybe only a few dozen.

Addendum: Sadly, this only reduces the $N=10$ case from $10^{10}$ equations to 115,975. It brings it into the realm of the feasible, but not nearly as much as I had hoped.

share|improve this answer
    
Indeed, this strategy will reduce the number of states from $N^N$ to the $N$th Bell number (there is a very natural correspondence with partitions of an $N$-element set), which is still superexponential in $N$. –  Rahul Aug 21 '12 at 5:43
    
@Rahul: Yes, thanks. I meant to include a link to the OEIS page, but it was late, and I forgot. –  MJD Aug 21 '12 at 11:42

I can improve a little on MJD's method. This was based on computing for each state $S$ (the last $N$ values) the expected remaining number of steps $L(S)$ until a final state (last $N$ values equal) is reached.

Let me change the notation slightly. Let $T_S$ be the number of steps from state $S$ until a final state is reached, and assume that this final state consists of $N$ copies of the value $F_S$. Both $T_S$ and $F_S$ are random variables, and $L(S)=\text{E}[T_S]$.

We can then write $$ \text{E}[T_S] =\sum_{u\in\mathcal{A}} \text{E}[T_S|F_S=u]\cdot\Pr[F_S=u] =\sum_{u\in\mathcal{A}}\sum_{t=0}^\infty \Pr[T_S=t, F_S=u]\cdot t $$ where $u$ runs through the values of $\mathcal{A}=\{1,\ldots,N\}$. The probability $\Pr[T_S=t, F_S=u]$ is that of reaching a final state with the final $N$ values all equal to $u$ after $t$ steps.

Instead of computing the expected remaining steps for of all combinations $\mathcal{A}^N$ (modulo permutations on $\mathcal{A}$), all we need are values $$ L_u(S)=\text{E}[T_S|F_S=u]\cdot\Pr[F_S=u] $$ which only depends on which elements of $S$ are equal to $u$. Thus, it suffices to compute $L_1(S)$ for $S\in\{1,0\}^N$ where $1$ indicates the value $u$ and $0$ a value other than $u$.

This reduces the computational burden to having $2^N$ different $L_1(S)$ to compute.

Update: Here are the equations required for solving $L_1(S)$. As noted by MJD in the comment, these are slightly different.

For ease of notation, let's restrict ourselves to the case where $S\in\{0,1\}^N$. Then we can write $$ L_1(S)=\text{E}[T_S|F_S=1]\cdot\Pr[F_S=1]=\text{E}[T_S F_S]. $$ We can then express $L_1(S)$ for non-final states $S$ (i.e. not all 0s or 1s) in terms of $L_1(S')$ where $S'$ are the possible next states as $$ \begin{split} L_1(S)&=\text{E}[T_S F_S]=\Pr[F_S=1]+\text{E}[(T_S-1) F_S]\\ &=\Pr[F_S=1]+\sum_{S'} \Pr[S\rightarrow S']\cdot\text{E}[T_{S'} F_{S'}]\\ &=\Pr[F_S=1]+\sum_{S'} \Pr[S\rightarrow S']\cdot L_1(S') \end{split} $$ where $\Pr[S\rightarrow S']$ denotes the transition probability from $S$ to the next state $S'$: i.e. if $S=(s_1,\ldots,s_N)$ the next state will be $S'=(s_2,\ldots,s_N,1)$ with likelihood $\frac{1}{N}\sum_{i=1}^N s_i$, and $S'=(s_2,\ldots,s_N,0)$ with likelihood $1-\frac{1}{N}\sum_{i=1}^N s_i$.

Note that we could not have done this on the conditional $\text{E}[T_S|F_S=1]$, although it looks tempting, as $\text{E}[T_{S'}|F_{S'}=1]$ are conditional on $F_{S'}=1$ not $F_S=1$. However, we do have $$ \Pr[F_S=1]=\sum_{S'}\Pr[S\rightarrow S']\cdot\Pr[F_{S'}=1]. $$

We now need to compute $\Pr[F_s=1]$ for all $S$.

To do this, let's go back to the original $S=(1,\ldots,N)$ and let $q_k=\Pr[F_S=k]$. The next state $S'=(2,\ldots,N,s')$ for $s'=1,\ldots,N$, each with likelihood $1/N$. This gives us, writing $q_0=0$ for convenience, $$ q_k=q_{k-1}+\frac{q_N}{N} \implies q_k=\frac{2k}{N(N+1)} $$ which is just the above expression for $\Pr[F_S=k]$ in terms of the sum over $S'$.

For $S\in\{0,1\}^N$ we then get $$\Pr[F_S=1]=\sum_{k=1}^N s_kq_k=\frac{2}{N(N+1)}\sum_{k=1}^N s_k.$$

Example: Let's do $N=2$.

For ease of notation, I'll write $f_S=\Pr[F_S=1]$ and $l_S=L_1(S)$ for $S\in\{0,1\}^N$.

First $f_{00}=0$, $f_{10}=1/3$, $f_{01}=2/3$ and $f_{11}=1$.

For the final states, we have $l_{00}=l_{11}=0$. Then, we have $$ \begin{split} l_{10}&=f_{10}+\frac{1}{2}(l_{00}+l_{01})=\frac{1}{3}+\frac{1}{2}l_{01}\\ l_{01}&=f_{01}+\frac{1}{2}(l_{10}+l_{11})=\frac{2}{3}+\frac{1}{2}l_{10}\\ \end{split} $$ which solves to $l_{01}=10/9$ and $l_{10}=8/9$.

Going back to the original problem, $S\in\{1,\ldots,N\}$, we compute $$ L(12)=\sum_u L_u(12)=l_{10}+l_{01}=2 $$ where the two $l$ terms correspond to picking $u=1$ and $u=2$.

The notation could perhaps been less confusing if I'd used values true and false instead of 1 and 0, intruduced the indicator map $\chi_u(S)$ which maps $u$ to true and the other values to false, and consistenty written $S\in\mathcal{A}^N$ while using $\chi_u(S)\in\{\textit{false},\textit{true}\}^N$. However, I hope it was still clear enough.


I did the computations (using Maple to solve the linear equations). If $L_N=L(12\ldots N)$, I found: $$ \begin{split} L_2&=2\\ L_3&=\frac{19}{4}=4.75\\ L_4&=\frac{1179}{140}=8.4214\ldots\\ L_5&=\frac{12226997}{934830}=13.079\ldots\\ L_6&=\frac{633096670030808}{33784478422065}=18.739\ldots\\ &\text{etc.}\\ \end{split} $$ which are not numbers that factor nicely.

share|improve this answer
    
I tried doing this, but I got stuck, because I could not think of how to express the relation between the various $L_1(S)$ values. Formerly I had $L(01) = 1 + \frac12(L(10)+L(11))$, but the analogous relation, $L_1(01) = 1 + \frac12(L_1(10)+L_1(11))$ does not hold: the extra "$1+$" at the beginning is wrong because not every step will eventually lead to the target state of $11$. So I was not able to complete the calculation, even in this simple case. I think we need $L_1(01) = \Pr[F_s=1] + \frac12(L_1(10)+L_1(11))$, but $\Pr[F_s=1]$ is hard to find. Could you please work through an example? –  MJD Aug 21 '12 at 19:36
    
You're right! The expression for $L_u(S)$ should contain $\Pr[F_S=1]$ instead of 1. Fortunately, $\Pr[F_S=1]$ is easy to compute. I'll edit the answer accordingly. –  Einar Rødland Aug 22 '12 at 4:59

the only way i've thought by far

let f('1,2,3', 3) be the answer for N = 3, and it equals

f('1,2,3', 3) = 1/3 * (f('2,3,1', 3) + 1) +
                1/3 * (f('2,3,2', 3) + 1) +
                1/3 * (f('2,3,3', 3) + 1)

see all the f('', N) as unknown numbers, and for a certain N, we have N^N unknown numbers(if consider f('1,2,2', 3) and f('2,3,3', 3) as different status). And for each of them, we can write an equation with some of the other f()

N^N unknown numbers with N^N equations, we can solve it with Gaussian Elimination

It can get the accurate answer in fraction form, However still can not get the analytic result for any given N.

share|improve this answer

Your Answer

 
discard

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.