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.

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 ?

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
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. –  Hardy Sep 26 '12 at 19:51
1  
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. –  Hardy Sep 26 '12 at 20:08
add comment

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.

share|improve this answer
    
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. –  Hardy Sep 26 '12 at 19:41
add comment

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.