# Finding the probability of a client getting the same token in two consecutive interactions.

I am trying to find the probability in the following real-world inspired scenario.

If I have a finite set of whole numbers from 0 to 4 billion which I call tokens and $n$ clients. Each time a client interacts with me I give him a number from my set of tokens. So for example when the first client interacts with me I give him 0, second guy 1, third guy gets 2 and so on and so forth. When I run out of tokens I restart from 0 again. What is the probability that a client gets the same token value in two consecutive interactions.

My first thought was it should be just 1/4 billion, but I think that this may not be the case. I hope the description of the problem is not ambiguous. If so please let me know and I'll try improve it further.

Any help would be much appreciated. Thanks in advance.

PS Edit : What about $n_{C_{1}}$ times 1 out of 4 billion ?

-

If there are many clients visiting very often and in unpredictable manner, then the next token of a client can be viewed as random, thus producing a 1 in 4 billion chance.

However, if the total number $n$ of clients is much smaller than 4 billion and their visiting proportions are about about equal, then a double token is much less likely: It is dominated by the probability of about $N=$ 4 billion "drawings" out of the $n$ clients avoid the given client, which is $(1-\frac1n)^N\approx e^{-\frac Nn}$. For this to be "better" than $\frac 1N$, it is sufficient to have $n$ less than about 180 millions (assuming that billion = $10^9$).

-
firstly thank you for your answer. My apologies as the question i am about to ask is probably quite elementary. Why are we interested in $\left( 1-\dfrac {1} {n }\right)$ If you could pls shed some light on the reasoning behind this that would very much appreciated. – Comic Book Guy Sep 26 '12 at 19:51
Assume $X$ gets token $0$. For $X$ to get $0$ next time as well, the next $N-1$ visits must be by one of the other $n-1$ clients. At each step, the probability that the next client is not $X$ is $\frac{n-1}n=1-\frac1n$. – Hagen von Eitzen Sep 26 '12 at 20:05
Thank you very much, i really appreciate your help. – Comic Book Guy Sep 26 '12 at 20:08

If you select a token at random, the chance is 1 in 4 billion as you say. If you give them in order it can be different. If somebody doesn't wait long enough for you to go around, the probability is zero. If somebody is aware of the interaction rate and comes at just the right moment, it can be 1.

-
Firstly thank you for your reply. Since i am giving them order and lets presume the clients have no knowledge of my interactions with others. Is it possible to improve upon this probability calculation. Please also see my edit above. – Comic Book Guy Sep 26 '12 at 19:41