A simple probability question!

[srikank]

Hi,

I am having difficulty with the following problem:

You can have a state of 256 different elements (0-255). An element between 0-255 appears only once in a state of 256 elements. I understand that there are N! possible states. Now I want to calculate the probability of a state that has some k elements (not necessarily consecutive) common with a state that I have picked. Any suggestions on how to approach this problem? I apologize for the ignorance if it is too simple.

Thank you!

[BeerMoney]

Could you be clearer in your description of your problem?

[AngusThermopyle]

[ QUOTE ]
Could you be clearer in your description of your problem?

[/ QUOTE ]
It seems he is asking:
Given 2 permutations of 256 distinct elements, what are the odds that they will agree on (exactly?) k elements?

( the N! seems to imply he is talking about permutations, as does the "only appears once" )

[srikank]

Hi,

My apologizes for the confusion. It is infact permutation of 256 elements (N! is nothing but 256! ways of arranging 256 unique elements = permutation).

Let me elaborate the question by first defining k-state: A k-state is a partially defined state that includes k elements (not necessarily consecutive). Now let 'A' be a k-state and let 'E' be the event that the current chosen state (one picked from 256! states) has the same k elements as 'A'. So what is P[E]?

If you need more information please let me know. Thanks for your effort in solving this for me.

Sincerely.

[AngusThermopyle]

To me, your question still makes no sense.

[BruceZ]

[ QUOTE ]
Hi,

My apologizes for the confusion. It is infact permutation of 256 elements (N! is nothing but 256! ways of arranging 256 unique elements = permutation).

Let me elaborate the question by first defining k-state: A k-state is a partially defined state that includes k elements (not necessarily consecutive). Now let 'A' be a k-state and let 'E' be the event that the current chosen state (one picked from 256! states) has the same k elements as 'A'. So what is P[E]?

If you need more information please let me know. Thanks for your effort in solving this for me.

Sincerely.

[/ QUOTE ]

If you mean that E must agree with A in k specific places (and it can agree in other places too), then the number of possibilities for A is (256-k)!, and P(E) = (256-k)!/256! = 1/[ k!*C(256,k) ] = 1/P(256,k).

Let me know if you wanted something different.

[srikank]

Hi BruceZ,

Thank you so much. Your answer is very convincing. Please note that A is only partially defined i.e only k elements are defined and not the rest. So E can agree with A on only k specific elements and not more. However that does not change the final answer.

Sincerely,