Wednesday, September 25, 2019

Shuffling an infinite deck of cards

Suppose I have an infinitely deep deck of cards, numbered with the positive integers. Can I shuffle it?

Given an infinite past, here is a procedure: n days ago, I perfectly fairly shuffle the top n cards in the deck.

When one reshuffles a portion of an already perfectly shuffled finite deck of cards, the full deck remains perfectly shuffled. So, the top n cards in the infinitely deep deck are perfectly shuffled for every finite n.

Can we argue that the thus-shuffled deck generates a countably infinite fair lottery, i.e., that if we pick cards off the top of the deck, all card numbers will be equally likely? At the moment I don’t know how to argue for that. But I can say that we get what I have called a countably infinite paradoxical lottery, i.e., one when any particular outcome has zero or infinitesimal probability.

For simplicity, let’s just consider picking the top card off the deck and consider a particular card number, say 100. For card 100 to be at the top of the deck, it had to be in the top n cards prior to the shuffling on day −n for each n. For instance, on day −1000, it had to to be in the top 1000 cards prior to the shuffling. The subsequent 1000 shufflings together perfectly shuffle the top 1000 cards. Thus, the probability that card 100 would end up at the top is 1/1000, given that it was in the top 1000 cards on day −1000. But it may not have been. So, all in all, the probability that card 100 would end up at the top is at most 1/1000. But the argument generalizes: for any n, the probability that card 100 would end up at the top is at most 1/n. Hence, the probability that card 100 would end up at the top is zero or infinitesimal.

If taking an infinite amount of time to shuffle is too boring, you can also do this with a supertask: one minute ago you shuffle the top card, 1.5 minutes ago you shuffle the top two cards, 1.75 minutes ago you shuffled the top three cards, and so on. Then you did the whole process in two minutes.

All the paradoxes of fair countably infinite lotteries reappear for any paradoxical countably infinite lottery. So, the above simple procedure is guaranteed to generate lots of fun paradoxes.

Here is a fun one. Carl shuffles the infinite deck. He now offers to pay Alice and Bob $20 each to play this game: they each take a card off the top of the deck, and the one with the smaller number has to pay $100 to the one with the bigger number. Alice and Bob happily agree to play the game. After all, they know the top two cards of the deck are perfectly shuffled, so they think it’s equally likely that each will win, and hence each calculates their expected payoff at 0.5×$100 − 0.5×$100 + $20 = $20. He puts them in separate rooms. As soon as each sees their own card (but not the other's), he now offers a new deal to them: if they each agree to pay him $80, he’ll broker a deal letting them swap their cards before determining who is the winner. Alice sees her card, and knows there are only finitely many cards with a smaller number, so she estimates her probability of being a winner at zero or infinitesimal. So she is nearly sure that if she doesn’t swap, she’ll be out $100, and hence it’s obviously worth swapping, even if it costs $80 to swap. Bob reasons the same way. So they each pay Carl $80 to swap. As a result, Carl makes $80+$80−$20−$20=$120 in each round of the game.

Causal Finitism, of course, says that you can’t have an infinite causal history, so you can’t have done the infinite number of shufflings.

26 comments:

Alexander R Pruss said...

As set up above, Alice and Bob don't get Dutch Booked: one of them still makes some money.

But let's suppose Carl is greedier. Alice and Bob should each be willing to pay Carl any amount short of $200 to broker the swap, since that's the difference between winning and losing. So, he can get $199 in swap fees from each. Presumably, he only needs to pay $1 to motivate them to play the game in the first place. So, he can rake in a total of $396 per round.

How do Alice and Carl come out on this? Well, they each get $1 from Carl. They each pay Carl $199 for the swap. One of them loses $100 to the other and the other gains it. So, one of them ends up being $298 out and the other is $98 out.

Atno said...

If we have a series of caused objects, by causal finitism there must be a first uncaused cause. This would be a way out of the "regress problem" of cosmological arguments. The theist will want to argue that the first cause is necessary, perhaps by appealing to a modest PSR that requires a cause for contingent objects. For now, let's say the First Cause is contingent. Let's call it C.
But could a B theorist then hold the (very strange, in my opinion) view that C is caused by an earlier version of itself, or an earlier part? In this case, C would not have an external cause; there would be no infinite series of distinct causes. But C would be caused by its earlier parts from infinity past. Would causal finitism also rule this out?

Majesty of Reason said...

This is fascinating. I am curious: How would we get an explicit contradiction out of this?

Could we reason as follows?

Let this infinite shuffling game be called G.

1. If causal infinitism is true, then it would be possible for G to be implemented.
2. If it were possible for G to be implemented, then one rationally ought to play G and one rationally ought not to play G.
3. But it cannot be the case that one is both rational and not rational in playing a game.
4. Therefore, causal infinitism is false.
5. Therefore, causal finitism is true.

Does this capture the thrust of the paradox? If not, then what contradiction are we trying to get at here? Thanks in advance. You are a wonderful philosopher.

IanS said...

The setup combines a standard Prisoners’ Dilemma with a probabilistic paradox. The Prisoners’ Dilemma can arise even in unparadoxical finite cases. Suppose there are 1000 cards, Alice gets ‘1’ and Bob gets ‘2’. Then it would seem to each that they should swap, but between them in total, they would do better to stick.

I take it that your interest is in probability theory, not Prisoners’ Dilemma. You may prefer a one-person version. Alice is offered $1 to play. The first and second cards will be placed is separate sealed envelopes. Alice will be given the first envelope. If her number is smaller than the other one, she will lose $100, otherwise she will win $100. She is allowed to look at her number and reseal the envelope. For $199 she will have the option to swap envelopes. If she accepts, her memory of the first number will be erased, she will be allowed to look at her new number, and, for a further $199, she will have the option to swap back.

It seems that Alice will accept the offer to play then accept both swaps, thereby losing for sure.

I would give Alice my usual advice in such cases: don’t conditionalize. Make a plan in advance and stick to it. Never swap is a reasonable plan. It guarantees her $1. Swap only on ‘1’, and never swap back is slightly better. Another reasonable plan is to pick a large number N, swap if the first number is N or less, then swap back only if the second number is less than N/200 (if I’m thinking straight). Note that in all such plans, Alice will reject the first swap with probability 1 and her expected gain will be $1.

Alexander R Pruss said...

Ian:
In the standard classical setup, Carl has no guarantee of making money. Alice and Bob won't want to swap if their numbers are high.

Alexander R Pruss said...

I don't really see the Prisoner's Dilemma here. Can you explain?

Philip Rand said...

Can we argue that the thus-shuffled deck generates a countably infinite fair lottery, i.e., that if we pick cards off the top of the deck, all card numbers will be equally likely?

No. I have chi-square tested the hypothesis. It is not possible to generate a fair lottery.

IanS said...

Alex:

In the classical setup, it’s true that Carl loses money if Alice and Bob decline the swap, as they will if their numbers are high. But if Alice and Bob agree in advance to cooperate and have the winner pay the $100 back to the loser after the event, they can always decline the swap and always end up with $1 each. The same applies to the infinite version.

Alexander R Pruss said...

I hadn't thought of that. But we can just stipulate that they can't do that. Perhaps the prizes are not monetary but pleasures and pains administered by Carl.

Philip Rand said...

Pruss

Mixed phenomena makes no difference to the result of the hypothesis.

IanS said...

Alex:

I’m not sure that making Carl the only source of utility changes things. Suppose the setup will be repeated. Then for, both Alice and Bob, the steady $1 (or equivalent utility) per round would be expected to eventually swamp the sum of the random $100 (or equivalent) wins and losses.

Here is another way to look at it. Think about the classical version. Assume no cooperation. Alice might reason that if her number is suitably low, the odds are right to offer the swap. But then she realizes that Bob, reasoning similarly, will accept only if his number is also low. Now the odds don’t look so good. So you need game theory, not just decision theory narrowly defined. My one-person version avoids such issues.

But here is what interests me. Think about my infinite one-person version. The obvious plan is never swap. I gave some plans that give an infinitesimal improvement on this. Amazingly, there seems to be a plan that that gives a genuine improvement, provided Alice has access to the other cards. She takes the next (say) 10,000 cards. She sorts them and her card into ascending order. If her card is in the first 50 (= 10,000/200), she accepts the first swap. This plan gives her an expected extra gain of about $ 0.50 /200 = $ 0.0025 (if I’m thinking straight, which I’m not at all sure of). This is small, but not zero.

Alexander R Pruss said...

One difference between the finite and infinite cases is that in the finite case the other player's willingness to swap carries information. But in the infinite case, it doesn't.

Philip Rand said...

Nope... you are wrong... your mistake is in your notion of what is conitinuous and what is discrete....

Alexander R Pruss said...

Mr Rand: I am afraid that too many of your comments are enigmatic and unargued-for. Please include more in the way of serious arguments in the future.

Philip Rand said...

I have given you plenty of info, i.e. chi-squared test.

Your concern technically is called degrees of freedom of the hypothesis. This can be handled in the chi-squared test, i.e. finite or infinite.

Nothing enigmatic about it.

Majesty of Reason said...

Shouldn't Alice have just reasoned beforehand that, for any card number n, there are a finite number of cards labeled that have a value below n, whereas there are an infinite number of cards labeled that have a value above n, in which case for any card n she could potentially pick, there is an infinitesimal (else: zero) probability that she would win? But if so, then isn't it false that she should have taken the bet to begin with and that she purportedly had a 50% chance of winning to begin with?

I hope you can help me see the paradox here.

I am also hoping you can help explain why such situations involving Dutch books actually entail contradictions as opposed to showing perhaps inherent difficulties in the concept of rationality (like one cannot be perfectly rational). Could we derive a contradiction from infinite Dutch book cases by means of arguing that they entail a conjunction of the form A and ~A, where A is "one rationally ought to play the gambling game" and ~A is "it is false that one rationally ought to play the gambling game"?

Philip Rand said...

Majesty of Reason

You highlight the interesting conclusion of the thought experiment.

This insight of yours is especially good:

Could we derive a contradiction from infinite Dutch book cases by means of arguing that they entail a conjunction of the form A and ~A, where A is "one rationally ought to play the gambling game" and ~A is "it is false that one rationally ought to play the gambling game"?

What you are saying is that the "game" for the observer is zero-sum...it is not a contradiction...that insight has far reaching consequences...

IanS said...

Alex:

No strategy played by both Alice and Bob can do better than never swap. Why? Because swapping carries a penalty and if Alice and Bob play the same strategy, the expected penalty must be split equally between them.

Note that this reasoning depends only on the symmetry. It applies equally to the finite and infinite cases. It does not depend in any way on the probabilities of the cards (as long as they are symmetric, of course). This makes the two-person setup unsuitable for testing intuitions about the probabilities of the cards. The one-person version avoids this problem.

Philip Rand said...

Majesty of Reason

Type this search: "A053169 OEIS"

And you have a logical demonstration of your conclusion.

Interestingly, it is also a logical demonstration that the Thomist First Principle of Non-Contradiction is false.

Dominik Kowalski said...

There is no specific "Thomist First Principle of Non-Contradiction". There is only the general Law of Non-Contradiction

IanS said...

Majesty of Reason (if you are still following this thread):

Alice was right to take the bet. She knew that the first two cards had been shuffled, so she had probability 1/2 of getting the higher one. As long as she resists the temptation to take the swap, her expected gain will be $1.

Alice is also right to think that with probability 1, Bob’s number is greater than any given number (granting for the sake of argument that the infinite series of shuffles is possible and has happened). But she would be wrong to conclude that with probability 1, Bob’s number is greater than her number, and she would be wrong to accept the swap based on this conclusion.

The subtle distinction is that Alice’s number is not a given number – it resulted from the same random process that produced Bob’s, and it could not have been given in advance. (Another example: with probability 1, Bob’s number is greater than any given number, but it is certainly less than Bob’s number + 1. The catch is that Bob’s number + 1 is not a number that could have been given in advance.) The paradox (if indeed it is a paradox) is precisely that this distinction matters.

What to make of this? One view (mine) is that there is no paradox. Alice is simply wrong to conditionalize on her number as if it were a number given in advance. Another view the fact that the distinction matters (note, usually it doesn’t, which is why tend to ignore it) shows that there is something wrong with the setup, or with the reasoning leading to the probabilities. In this case, Alex has pointed to the infinite causal chain. The infinite number of cards, each able to display arbitrarily large numbers, and the infinite number of arbitrarily deep shuffles also seem suspect.

N.B. I’m strictly an amateur. Don’t take my word. There is literature on these issues, some by Alex himself. Keywords: nonconglomerable, finite additivity.

David Duffy said...

I found this setup rather baffling. My first thought was to apply the non-standard analysis that
Edward Nelson uses in Radically Elementary Probability Theory (1987), where he provides proofs for ordinal and cardinal Borel-Cantelli Theorems. I see Wenmackers (2011) uses the same apparatus to get hyperrational probabilities for an infinite lottery.

If I understand Nelson correctly, the cardinal version can hold for the infinite lottery, but the ordinal version does not. Since the actual bet here relies on ordinality and tail probabilities of a nonconverging sequence I have a feeling that the conditioning cannot be legal because one is mixing internal (ie finite or "limited") and external (unlimited) notions (the difference between two draws may or may not have an expectation of 0, but does have an infinite variance). It is clear that if Alice has drawn 1, she can have sure knowledge she has lost, even though the prior probability of this ever happening is infinitesimal. If the labelling (Wenmackers) of the tickets was over the (negative and positive) integers, we would find it more "intuitive", even though it is the same size probability space.

In passing, the shuffling of the deck is extremely well known as the group S_N, and is uncountable. I did wonder if there was a result about this setup in the guise of the length of increasing subsequences of a random walk (ie a permutation).

Philip Rand said...

David Duffy

Your concern of legal conditioning is ill founded.

Simply, refer to the last paragraph on page 15 of Radical Elementary Probability Theory.

Alexander R Pruss said...

Mr Duffy:

It's hard to make sense of generating a "random element" of S_N. For one, S_N is not an amenable group (it has F2 as a subgroup).

It is hard to make mathematical sense of my setup. It's an infinite process without meaningful initial conditions. BUT it intuitively seems that IF an infinite past is possible, this process could have taken place.

David Duffy said...

Dear Philip Rand.

Nelson frequently mentions "illegal set formation", where one may not form subsets corresponding to external properties - this is how overspill can be used.

Hi Professor Pruss.

There seems to a TCS literature on the computational complexity of S_N - I have glanced at http://adsabs.harvard.edu/abs/2015arXiv150306188A

Philip Rand said...

David Duffy

Now, read the first paragraph of the appendix in Nelson's book on page 80... especially note the last sentence of the paragraph.

The S-N complexity space is discrete; it is not applicable.