Wikipedia:Reference desk/Archives/Mathematics/2016 January 2

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 2

What is the probability of two photographs appearing simultaneously from a set of thirteen photos?

I have two computers. The first computer (Computer A) has a series of 13 photographs that it cycles through (one per minute) as my desktop background. The second computer (Computer B) has the same exact series of 13 photographs that it uses for the same purpose. Computer A cycles through each of the 13 photographs in sequential order. Computer B randomly selects one of the 13 photos to display for one minute; then it randomly selects another to display for a minute; and so on. Assume that both computers are timed in synchronicity (i.e., the minute "begins" at the same precise second for each computer). The question is: what is the probability that both computers will display the same photograph/desktop background at the same time? And a related question: in any given hour, how many minutes (of those 60 minutes) would be expected to have the same photo displayed on both computers? If you use probability formulas and such, please explain the steps involved. Thanks. Joseph A. Spadaro (talk) 07:42, 2 January 2016 (UTC)

Assuming that computer B randomly chooses from the 13 with equal probability each time (i.e. the same one may be chosen twice in a row), the probability is 1/13. Bubba73 ^{You talkin' to me?} 07:56, 2 January 2016 (UTC)

Are you sure? That doesn't seem right to me, intuitively. How do you get that? Thanks. Joseph A. Spadaro (talk) 08:43, 2 January 2016 (UTC)

The question can be rephrased as "if Computer A is showing photo X at time t, what is the probability that Computer B is also showing photo X at time t". Since the choice of photos on Computer B is random (and we assume that means random with a uniform distribution) then the answer is 1 in 13. You will get the same answer whenever either computer is selecting photos at random - the behaviour of the other computer is irrelevant. Computer A could always show the same photo, or could select one photo more often then others, or could show a random sequence too - the answer is still 1 in 13 in each case. Gandalf61 (talk) 09:33, 2 January 2016 (UTC)

@Gandalf61: You re-phrased the question. And that made me think that perhaps I phrased my question incorrectly in the first place. What I was trying to ask was this. (Which may -- or may not -- be the same question, being asked in different phrasing. I am not sure.) Let's say that Computer A goes through one full cycle of 13 photographs in sequential order. During that 13 minutes (1 photo per minute), how many duplicates would I expect? In other words, during that 13 minutes, how many times would I expect Computer B to be displaying the same photo as Computer A? Is the answer 1/13 for this question also? That is, for any one cycle of Computer A's 13 photos, I should expect to see a duplicate "match" only one time on Computer B. Am I understanding correctly? Thanks. Joseph A. Spadaro (talk) 21:46, 2 January 2016 (UTC)

And in answer to your related question, 60/13 minutes of each 60 would be expected to have the same picture showing, the actual duplication being anywhere between zero and 60 minutes with a Binomial distribution applying.→86.139.120.76 (talk) 13:24, 2 January 2016 (UTC)

What? I dd not understand a word of this. This is the math that I did. Did I do it correctly or incorrectly? The probability of 1/13 is equal to 7.69%. If I take 1/13 (or 7.69%) of 60 minutes, I get 4.6 minutes. So, in any given hour, I will expect 1/13 of that hour (or 4.6 minutes) to have duplicate photos displayed. Is my math correct? Thanks. Joseph A. Spadaro (talk) 21:50, 2 January 2016 (UTC)

This is correct. And to clarify earlier observations: In each minute, the chance they show the same photo is 1/13. In one cycle of 13 minutes (where A shows each photo once and B shows 13 random photos), on average there will be 1 minute in which the photos will be the same. Over x minutes, on average there will be $x/13$ minutes in which the photos are the same.

The other part of anon's answer tells you how the number of such identical photos is distributed - you can know more than just the average number, you can tell what is the probability that there will be no identical photos, that there will be 1, that there will be 2, etc. This is given by the binomial distribution, with $n=x,\ p=1/13$. -- Meni Rosenfeld (talk) 22:11, 2 January 2016 (UTC)

Change in scenario

OK. Thanks. So, I think I am understanding all of the above. Thank you. Now, what if we change the scenario? Computer A stays the same (it shows one photo per minute from 13 photos in sequential order). Computer B now acts differently. Computer B shows a random photo from the set of 13; but after a random photo is selected, it is removed from the "loop" for that 13-minute cycle. In other words, Computer B must cycle through each one of the 13 photos in a 13-minute cycle. It simply does so randomly. Thanks. Joseph A. Spadaro (talk) 22:22, 2 January 2016 (UTC)

:I know this is a stupid question but why don't you do a computer simulation of this? This problem is ripe for computer simulation. Just make sure you do 20,000 runs to get a proper value. 110.22.20.252 (talk) 23:49, 2 January 2016 (UTC)

Have no idea what you are talking about. And have no idea how to do a computer simulation. Hence, I have not done a computer simulation. Joseph A. Spadaro (talk) 00:26, 3 January 2016 (UTC)

Just exactly how old are you? Are you a teenager? Obama tells you to learn to code, so that you can do simulations to learn about the mathematical world around you.

“What is true is … that our lead will erode if we don’t make some good choices now,” the president said. “We’ve got to have our kids in math and science, and it can’t just be a handful of kids. It’s got to be everybody. Everybody’s got to learn how to code early.” - Obama 110.22.20.252 (talk) 01:57, 3 January 2016 (UTC)

Obama's vision is noble but we're very far off from fulfilling it. Also, there is research suggesting that some people are simply inherently unable to learn to successfully code.

It's unreasonable to expect every questioner here to be a proficient programmer fluent with the ways of Monte-Carlo simulations. It's just barely reasonable to expect that from every answerer here. -- Meni Rosenfeld (talk) 17:10, 3 January 2016 (UTC)

What's your question this time? Is it still the expected number of duplicates in 60 samples? —Tamfang (talk) 01:50, 3 January 2016 (UTC)

Well, let's start with the first cycle of 13 photographs. Within that one cycle (13 photographs), what is the percentage (probability) of them that would be expected to be duplicated on Computer A and Computer B? Thanks. Joseph A. Spadaro (talk) 01:57, 3 January 2016 (UTC)

Have you tried looking at derangement? Derangement A derangement is a permutation in which none of the objects appear in their "natural" (i.e., ordered) position. 110.22.20.252 (talk) 01:53, 3 January 2016 (UTC)

Are you sure that's relevant? You stated that none of the objects appear in their "natural" (i.e., ordered) position. But that's not necessarily the case here. Even though Computer B selects each photo at random, it is conceivable (though unlikely) that it will still happen to select them in order (by coincidence or randomness, not be design). No? Joseph A. Spadaro (talk) 01:59, 3 January 2016 (UTC)

Every piece of mathematics is relevant because it helps you expand your horizon. There is a probability that none of the pictures in computer B will appear in the same position as Computer A. You can calculate with derangement(13)/factorial(13) 110.22.20.252 (talk) 02:03, 3 January 2016 (UTC)

And if you are like me, partially deranged , you can also learn about partial derangement on this website. http://mathworld.wolfram.com/PartialDerangement.html So the probability of k matches with n items is PartialDerangement(n,k)/factorial(n) 110.22.20.252 (talk) 02:08, 3 January 2016 (UTC)

And this is where your ability to code comes in. After you work out the probability using derangement, partial derangement and factorial. You can check and double check your probabilities with the results from your computer simulation. 110.22.20.252 (talk) 02:12, 3 January 2016 (UTC)

My guess is chances are 1/13 for the first picture, 1/12 for the second picture, 1/11 for the third picture, etc, and for the last picture left the chance is 100% since the only picture left on computer B is the only picture that didn't show yet on computer A? Akseli9 (talk) 14:57, 3 January 2016 (UTC)

That seems to make sense. I will see if other mathematicians weigh in. Thanks. Joseph A. Spadaro (talk) 16:36, 3 January 2016 (UTC)

I assume that one has to multiply all of the 13 fractions, yes? If I multiply (1/13) * (1/12) * (1/11) ... (1/3) * (1/2) * (1/1), i get a decimal value of 0.00000000016059044, which is equal to 0.00000001605904384%. Infinitesimally small. Joseph A. Spadaro (talk) 16:41, 3 January 2016 (UTC)

I'm sorry, but I'm afraid what Akseli9 said makes no sense, and neither does your followup - unless you're both trying to solve a very different question from what was stated.

Let's start with the question that this does give the correct answer to - "What is the probability that all pictures displayed are the same?". In this case, yes - the chance that the 1st picture displayed is the same is 1/13. Given that the 1st picture is the same, the chance that the 2nd picture is the same is 1/12. Given that the first two are the same, the chance for the third is 1/11, and so on. To find the probability that all are the same, you multiply out all the probabilities. This is ${\frac {1}{13!}}$ (see factorial), which is indeed very small - it's unreasonable to expect that all photos will just happen to match. (In the first scenario it is even smaller - ${\frac {1}{13^{13}}}$).

Put another way, computer A shows the photos in a given sequence, and computer B shows them in a random permutation. There are 13! permutations of a sequence of 13 photos, so the chance they will both give the same one is 1/13!.

But you asked a different question - "what is the average number of identical photos?". The chance for each photo to be identical is 1/13, so over a sequence of 13 photos on average 1 will be identical.

This is very easy to realize if you understand a bit of probability theory. At each minute, taken on its own, the photo shown by computer B is a random one chosen uniformly from the 13. This much is in common between both scenarios - the scenarios differ in how the different minutes correlate, but the correlations are completely irrelevant for our purposes. Each minute is a random photo, so the chance that it will match the photo on computer A is 1/13 - it doesn't matter at all what computer A shows, if one photo is random the comparison is random. This means that for a given minute the expectation is 1/13. And expectation is additive - the total expectation is the sum of the expectation for each minute. That's why you end up with 13*(1/13) = 1. -- Meni Rosenfeld (talk) 17:00, 3 January 2016 (UTC)

@Meni Rosenfeld: Thanks. Your answer has a lot of information. So, I will need to read and digest it. There's a lot there. But, I have a comment and a question. Comment: Yes, I later realized (and agree) that the answer I suggested above (1/13 * 1/12 * 1/11 ... 1/3 * 1/2 * 1/1) is the probability that all thirteen photographs will match. So, yes, I follow that. And, yes, that does not answer the question that I had asked. Question: You are saying that the answer to my new "revised" question is 1/13? So there is absolutely no difference in my two scenarios? In scenario 1, Computer B randomly selects any of the 13 photos. So, any one photo can resurface multiple times, over and over again. In scenario 2 (revised scenario), Computer B randomly selects any of the 13 photos, but then must make its next random selection from the remaining 12, then the remaining 11, then the remaining 10, and so forth. You are saying that there is absolutely no difference whatsoever between the two scenarios? To me, the second scenario seems much more restrictive on the actions of Computer B. What am I missing? Thanks. Joseph A. Spadaro (talk) 17:26, 3 January 2016 (UTC)

@Meni Rosenfeld: Also, you stated above that: (In the first scenario it is even smaller - ${\frac {1}{13^{13}}}$). What does this mean? I thought the answer to the first scenario was a simple 1/13? Where is that new denominator coming from? The denominator that has 13 raised to the 13th power? Thanks. Joseph A. Spadaro (talk) 17:31, 3 January 2016 (UTC)

1/(13¹³) ≈ 3.30x10^-15 and 1/(13!) ≈ 1.61x10^-10 are the probabilities of matching all thirteen in a row for a given run for random selection with replacement (your first scenario) and random selection without replacement (your second scenario). (See Sampling (statistics)#Replacement of selected units.) So having a "prefect run" is nearly fifty thousand times more likely with the second scenario. -- ToE 17:52, 3 January 2016 (UTC)

[ec] Sounds like you managed to get yourself confused.

There are two scenarios: 1st scenario where B draws randomly with replacement, and 2nd scenario where B draws randomly without replacement.

And there are two questions: The original one, "what is the chance that in a given minute the photos will be the same". And the alternative one which was implicitly introduced with Akseli9's comment: "what is the chance that all photos will be the same in a sequence of 13 minutes".

The answers are:

• 1st scenario, original question: 1/13.
• 2nd scenario, original question: 1/13.
• 1st scenario, alternative question: 1/(13^13).
• 2nd scenario, alternative question: 1/(13!).

For the alternative question, the scenarios are different. For the original questions, they're not. The 2nd scenario is more restrictive for B, but B is just as restricted from showing a different photo as it is restricted from showing the same photo. It just can't show a photo it has already shown, regardless of whether it's the same photo as A or not. The probabilities don't change. -- Meni Rosenfeld (talk) 18:23, 3 January 2016 (UTC)

Thank you Meni Rosenfeld for the correction. There is still something I don't understand yet. The second scenario has no replacement. When a picture is shown on computer B, it cannot be shown again anymore. So how the calculation is not narrowed at each new set of pictures, when each new set of pictures is shorter than the previous by one picture? Thank you for you patience, no mathematician here. Akseli9 (talk) 18:15, 3 January 2016 (UTC)

The number of photos available for picking narrows down each time. By the time we get to the 13th, only one is left. But there is no guarantee that this single photo is the one shown by A! To do the calculation you did (1/13, 1/12, 1/11), you have to assume that not only there are $13-i+1$ photos remaining, but also that exactly 1 of them is shown by A, which we cannot assume. In the last step, one photo remains, and it either match A or not, with probability 1/13. The probability is 1/13 for all other steps too, of course.

The correct way to look at it is to consider the marginal distribution at each step. That is, we consider the photo that B is showing at minute i and ignoring all the rest. Since B is showing a random permutation, this photo is distributed uniformly randomly. Thus it has a chance of 1/13 of matching the specific photo shown at minute i by A. -- Meni Rosenfeld (talk) 18:30, 3 January 2016 (UTC)

Thanks. So, much of this conversation is going way over my head. I'd like one thing clarified, if possible. There is a big difference (I thought?) in my first scenario and my second. Namely, Computer B selects with or without replacement. This "important distinction" has absolutely no bearing on the final answer? The final answer is 1/13, regardless. So how can it be that such a "big difference" (change in scenario) is completely irrelevant to the final answer of 1/13? If one can explain it more intuitively as opposed to using all these abstract formulas that are hard to conceptualize. Thanks. Joseph A. Spadaro (talk) 18:46, 3 January 2016 (UTC)

Same here. From what I understand from the further explanations above, I think the chances are the same at the moment of planning the entire thing, right before starting the computers, at the first minute. At this moment, there is no more chance to get picture #3 matching picture #11 at the fifth minute, than to get picture #10 matching picture #4 at the ninth minute. What's difficult to understand, is that chances will be still the same as minutes pass. Akseli9 (talk) 19:03, 3 January 2016 (UTC)

I've only skimmed the above answers, but I hope this helps. Suppose you have in your hand all thirteen spades from a card deck, and you then randomly played all of them. Suppose there is a card on the table (a duplicate ace-of-spades from another deck) and it doesn't change during play, then there will have to be exactly one match after the thirteen plays from your hand and yet each time you played a card the probability of a match does not change. Given the random play you are just as likely to match on the last play as with your first play. --Modocc (talk) 19:25, 3 January 2016 (UTC)

In your example, there is a card on the table (a duplicate ace-of-spades from another deck) and it doesn't change during play. In my computer example, the photos are indeed changing (one by one). So I am missing the connection with your example. Joseph A. Spadaro (talk) 04:55, 5 January 2016 (UTC)

Suppose the ace is changed midway to a king. The number of possible matches is doubled, but then consider in what way might this change affect the probability of a match on the very last play. The number of possible cards that can be played on the last play remains the same, there are thirteen possible from your hand of which only one will end up being played. The number of possible cards per turn is constant for any duplicate that might be shown at any of the turns. -Modocc (talk) 18:14, 5 January 2016 (UTC)

Thanks. I will have to give this more thought. And give it time to "sink in". It's confusing. Thanks! Joseph A. Spadaro (talk) 20:08, 5 January 2016 (UTC)

Expressed mathematically, the general question you are asking is if there is an intuitive explanation for why the expected number of fixed points of a permutation is one, regardless of the size of the set being permuted. One answer is that it depends on how intuitive to you the linearity of expectation is. -- ToE 19:28, 3 January 2016 (UTC)

Thanks, all. Joseph A. Spadaro (talk) 04:53, 5 January 2016 (UTC)