There exists a collection c where c = {1, 2, 3} and a randomization of c, d where d = {1, 3, 2}. d was obtained by a function f where f is an undefined randomization function.

Can c be obtained again (i.e. d = c) by randomizing

  1. d or
  2. d initially and then each randomized collection resulting from d

using f? If so, can it be proven?

  • 4
    $\begingroup$ By "randomization", do you mean "permutation"? Otherwise, I'm not really sure what you're asking. (And, if you do mean permutation, can you explain why you feel that this is a computer science question, rather than pure mathematics?) $\endgroup$ – David Richerby Dec 13 '16 at 17:17
  • 2
    $\begingroup$ 1. Is f deterministic (will it give you the same answer every time, if you feed it the same input repeatedly)? Or is it non-deterministic/randomized? 2. When you say "by randomizing", do you mean "by applying f"? 3. What have you tried? Where did you get stuck? Did you try working through some small examples to see what seems to happen for them; look for a small counterexample; try to look for a pattern and form a conjecture and see if you can prove it? $\endgroup$ – D.W. Dec 13 '16 at 17:55
  • 1
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Dec 13 '16 at 19:43

If f is a random permutation, then you can apply it to d and eventually get the ordering of C.

| cite | improve this answer | |
  • 2
    $\begingroup$ This is rather lacking in detail -- we're almost always looking for answers that are more than one sentence. For example, even repeatedly applying any fixed permutation enough times will return to the original ordering. $\endgroup$ – David Richerby Dec 13 '16 at 20:17
  • $\begingroup$ @DavidRicherby Make into an answer? $\endgroup$ – Yuval Filmus Dec 13 '16 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.