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 have an identity array $S$ of length 100. That is $S[1]=1, S[2]=2, \ldots, S[100]=100.$

Now I do the following experiment:

m=0

For x=1 to 100
       Take  two random integers y,z in [1,100]
       if(S[x]=x and y=10)
            m=1
            break
       S[y]=z

I want to find the probability of m=1. To calculate it, let $i$ be the value for which previous $y$ values do not touch $i$ th location of $S$ and when $x=i$, $y=10$. So probability should be $\sum_{i=1}^{100}(\frac{99}{100})^{i-1}\frac{1}{100} =0.62 $. But my simulation value is 0.48.

share|improve this question
add comment

1 Answer 1

A lot of your code seems redundant. For instance $x=S[x]$ is always true and $z$ never actually comes into play. All you're really doing is choosing a random integer between 1 and 100, 100 times and seeing if it's ever equal to 10. The probability of this will be one subtract the probability that $y$ is never 10 which equals $1-(\frac{99}{100})^{100}=0.634$. The simulation value could be a result of the "randomness" when choosing $y$ or the number of trials.

share|improve this answer
    
S[x]=x is not always true since I replace S[y]=z. For an example let when x=5, y=16, z=45. So when x=16, we have S[16]=45 if y not equal to 16 for 6<=x <=15 –  user12290 Jun 5 '13 at 2:19
    
ahh, yes, you are quite right. The problem is the probability of S[x]=x is quite complicated then- did the replacement S[y]=z affect future values or past values of x? Did it affect unique values or was the same value affected more than once? If so, did this value happen to return to the original? It will be a while before I have the time to consider this properly unfortunately, but there's some stuff for you to explore yourself. –  john Jun 5 '13 at 3:13
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.