Interesting Probability Problem

drop a card, 51 remain, odds next 4 are same color are 25/51*24/50*23/50*22/50, if one is red you break and repeat the algorithm with the other color.

>i've got a really interesting problem for you.
Nothing interesting about discrete probability desu. The answer is out there, just computationally infeasible to find in a simple way.

>Nothing interesting about discrete probability desu.
>The answer is out there, just computationally infeasible to find in a simple way.

Wrong on both counts

arxiv.org/pdf/1306.6232.pdf

I know jack shit about combinatorics.
What I'm doing is calculating the number of decks that have four or less consecutive black or white cards.
At first we can ignore the numbers and pictures on the cards. Then an example deck would look like "3 black, 2 red, 1 black, 4 red, 2 black, 3 red...". We can now look at the sequence of the black runs ("3, 1, 2, ..."). Since there are 26 black cards, the total of this sequence must also be 26.
The second line of code works out the amount of sequences of length n that add up to 26 and only use numbers up to four, [math]a_n[/math].
The length of the sequence is important because, assuming the deck starts with black, every n-element sequence of blacks can only be combined with an n- or an (n-1)-element sequence of reds (because black and red runs have to alternate).
After we have the [math]a_n[/math], we can can combine all possible sequences of blacks and reds, [eqn]d = 2 \sum_n \left( a_n^2 + a_n a_{n-1} \right)[/eqn] (the 2 is there because the deck can also start with red).

The total amount of unrestricted actual decks (where cards have numbers) is [math]52![/math], and every one of the decks we just talked about corresponds to [math](26!)^2[/math] actual decks (because the black and red cards can appear in [math]26![/math] orders each). Then the probability for a deck to have at least 5 black or red cards in sequence is [eqn]1 - d \frac{(26!)^2}{52!}[/eqn].

I stand corrected.

>Using a simulation to solve a well defined problem about probability

Found the Engineer.

Don't lump me in with OP. I only used a simulation because my exact solution didn't match what OP said so I had to double-check.

number of permutations with at least five consecutive same-color cards / total number of permutations.

>using math to solve a problem that is perfectly suited for a monte carlo simulation
and now you know why computer scientists are in demand and not mathematicians

if you look at a 52-digit binary number with leading zeros, isn't this the same as counting those that have five or more '1' digits?

i feel like this should have an easy solution

* out of those numbers that have an equal number of 1 and 0 digits

It's ~79,5%
The .5% fluctuates alot around 100k iterations, but stays pretty stable after 1M iterations.

So
and
are wrong.

made a program that simulates shuffling an actual deck of cards and then checks for a run of 5 of the same color
looks like this user had it right

can someone run a simulation just counting the permutations that only have consecutive runs of exactly length five?

>only have consecutive runs of exactly length five
ok, here I count a run as any deck that has a run of 5, and contains no runs greater than 5, and may or may not contain additional runs less than 5

roughly 30% chance

if you're wondering
here are the odds for a deck to contain run(s) of at least but no greater than:
3 -> .02
4 -> .20
5 -> .30
6 -> .23
7 -> .12
8 -> .06
9 -> .02
10->.01

Weird, I get around 34%

been thinking on and off about this for a while. it's harder than it looks. is it a tough problem or am i a brainlet?

it doesn't break down in any especially obvious way.

Weirder still, I got about 43%. Whereas my simulation for the original question agreed with this guy's ~77.3%.

looks like at least two of us are wrong
that is, unless one of us believes in alternative facts

I say we force math courses to teach the controversy.

Is not tough, it's just unlikely you'll find an expression for the series you get.

so it's just a recursive definition? i was trying to tackle it with basic counting tools.

I'm trying to find the relation between the two picks you can choose from (black or red; 1 or 0; ..) and the amount of combinations you can do given n amounts of either pick.
So, for instance
n=2; 4 (cards) gives 6 combinations (or 3x2 if we look at symmetry)
n=9; 18 (cards) gives 48100 combinations (or 24050x2 with symmetry)

I'm trying to do this because I want to see howmany unique combinations you can make (regarding or disregarding symmetry) with n=26 without bruteforcing it (might be alot of combinations) so I know howmany unique variations I can put into a set to test for the 5 same colour sequences.
Hope this kind of makes sense.
Also, I have no math background, so forigve me if I'm approaching this like a retard lol

i think i get it.

if you know the number for n-2 then you can add the extra red and black element however you want, since you'll only increase the number of consecutive elements.

*taking care not to disrupt your contiguous blocks when adding elements.

*block

The n=9 is wrong, I'm bruteforcing at the moment to find unique combo's, so I was a bit too hasty and naive in thinking I had enough iterations.
It is around 48,6k I think though

n=7 has 924 unique combo's
n=8 has 12870 unique combo's.

I've already established there's a 2x(2n-1) relation, but the other factor that's left is... hard to take into account.

It's 18 choose 9 = 48620.
You are correct that the OP question is very prickly to represent.

Yeah I just found that right after I posted it.. I don't know what the fucking relation is though..

I'm not really understanding what you're asking here It's not very coherent

I'm not even sure what you're asking now - what relation are you talking about?

You have n cards of black and n cards of red
Howmany (unique) combinations can I make with these n cards?
What is the relation between n and the amount of combinations?
I already found that if I take symmetry into account there's only half as many combinations possible.
Do it for 4 cards (n = 2; 2 red, 2 black) for example: you can make 6 combinations, but only 3 unique one's because of symmetry (because 1100 = 0011 in a sense; especially when regarding sequences)
Sorry if it's not coherent, I had difficulty expressing it. Hope this is more clear.

WAIT DONT TELL ME I THINK I GOT IT

In that case, you've picked a problem that's considerably more complex than what you should be starting with if you don't have familiarity with the underlying concepts.

>I already found that if I take symmetry into account there's only half as many combinations possible.
Even given the parameters you've decided on (order doesn't matter, elements of the same color are indistinguishable), this is wrong. But you're correct that it makes for fewer possible subsets.

You should start by becoming familiar with choose and permutations, which I assume you're not considering one of your previous comments.

Here are a couple of things related to your question that you could look at after gaining a basic understanding:
math.stackexchange.com/questions/2068996/choosing-objects-from-multiple-sets-of-indistinguishable-objects-without-replac
math.stackexchange.com/questions/1018399/combination-and-permutation-of-indistinguishable-objects

It seems like relation is primes... but how to predict the combination of primes is like ... idk man.
For instance: n=6 (12 cards); 924 combinations. We have 2(2n-1) as a constant to factor out, which is 22 (2x11); which leaves us with 42.
42 is equal to 6x7 or 2x3x7.
But then we have n=7 (14 cards); 3432 combo's. We factor 2(2n-1) out, which is 26; which leaves us with 132. This is then 11x12 or 2x2x3x11. How does this make sense?

This also assumes you understand factorials and why they're used to express possible configurations of sets such as a deck of cards

You want to use Burnside Lemma (en.wikipedia.org/wiki/Group_action#Orbit-stabilizer_theorem_and_Burnside.27s_lemma)

For n cards, n even, there are [math]n \choose n/2[/math].possible distribution.
Now, given one distribution shift the cards or just mirror the distribution
For instance, 110100 is equivalent to 001011 by mirror and to 011010, 001101, 100110, 010011 and 101001 by shift and too 100101, 110010, 011001, 101100 and 010110 by shift and then mirror (or mirror and then shift).
So there's a bunch of equivalent distributions, even for n = 6.
Moreover, the number of equivalent distributions doesn't only depend of the number of transformations we allow.

If we look at 101010 now, we have mirror : 010101 which does the same thing as shift.
There are only two equivalent distributions for this class.

And what we need to count the number of different classes of equivalent distributions.

And burnside formula is a way of computing that if we know for a given transformation how many distributions it does not affect, which is easier to compute since there are less possible tranformations (that is, 104) than there are possible distributions (that is, around 500 000 000 000 000).

Is there a way to find [math] a_n [/math] without using code? Is it simple but tedious, or is it more complicated? I'm also curious how you got the equation for d. You explained why the 2 was there, but I'm lost on the rest of it.

It doesn't matter for the problem at hand.
Let's say you set a specific order to the generated sequence (start from left and evaluate to right for example).
Let's say we use binary to make our sequence.
For every combination that start with 1, there's a mirror (or negative) that's exactly the same, but starts with 0. So in a sense it's unique, but it's not really.

Damn I hadn't even considered the shifts. Thanks for this! That is really interesting.

I do not know any formula for the [math]a_n[/math]. I could very much optimize my code to calculate them but that would not lead to a formula either so I can't be bothered. Someone knowledeable about combinatorics could probably shed some light on that issue.
The two terms in the sum for [math]d[/math] come from two different possibilities: if the deck starts with black and we know that there are n runs of black cards, the deck can be either "black, red, black, ..., black, red", which means that there must also be n runs of red cards (since black and red alternate). We then have [math]a_n[/math] possibilities for the blacks and the reds each, resulting in [math]a_n^2[/math] in total.
On the other hand, the deck could also have black at the end, "black, red, black, ..., red, black". Then there is one less run of red cards (n-1) and we multiply [math]a_n[/math] possibilities for the blacks with [math]a_(n-1)[/math] possibilities for the blacks, [math]a_n a_{n-1}[/math].

I also considered color swaps but I found that for n=6 it is always equivalent to some other already equivalent transformation of the distribution.
I suspect it is true for higher values of n as well.

And about shift, there's a problem.
If you reveal your cards on the table is a line and look for sequences of 5 cards of the same color, shifts can break those sequences, which affects wether the distribution is a solution of the problem.
It would work if you put the cards in a circle though.

And it's not enough to get a solution, because since the group of transformations is of order 104, you'd only divide the number of solutions by less than 104, leaving it still higher than 100 000 000 000.

So I guess Burnside's Lemma will only get you this far and you'd need to get more into the detail of how distributions of cards work.

I think you should check out permutations.(en.wikipedia.org/wiki/Permutation)

wait, no i don't. tell me the answer. i've found it hard to avoid counting duplicate cases.

you might be able to count it recursively, building up from a five element block and keeping track of how many red/black elements you have left while counting the number of ways to choose them from the remaining set of elements.

Problem is, the process can overlap with that of another block of five.

Say, your distribution of cards has two different blocks of five cards of the same color.
If you take one block of five and build recursively your distributions for each possible block, you'll count that one twite.

that's kind of what i thought. i'd love to see the solution to this.

and if you try to subtract out the number of different ways the duplicates can be constructed, you end up with the same problem.

answer time please.

had to look it up. so you do have to use those laguerre polynomials. tough stuff for Veeky Forums i think.

this is why god invented computer science, user
monte carlo

no, i'm glad i looked up the real answer. seems like a useful thing to know. would not have known how to answer this seemingly easy question otherwise. good reading material for another day.

>I do not know any formula for the [math]a_n[/math]

Let S(n) = number of ways to count to n in steps of 1,2,3 or 4
By manual inspection S(1)=1, S(2)=2, S(3)=4, S(4)=8
And for n>4 we have S(n) = S(1)*S(n-1)+S(2)*S(n-2)+S(3)*S(n-3)+S(4)*S(n-4) = S(n-1)+2S(n-2)+4S(n-3)+8S(n-4) since the RHS is the number of ways to take a penultimate step, multiplied by the number of ways to get to that step
So let [math]x_n = (S(n+3),S(n+2),S(n+1),S(n))[/math] and we have a system of linear equations [math]x_{n+1}=Tx_n[/math] where T is the matrix
[eqn] \begin{pmatrix} 1 & 2 & 4 & 8 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}[/eqn]
which you can diagonalize and calculate the matrix exponential T^(26) quickly.

I came up with 0.5^5 * (52/5), it doesn't account for probabilities being higher when one of the two colors has been depleted. But shouldn't that cancel out in a perfectly shuffled deck? I haven't had any mathematical training, just interested in it. If anyone can explain this to me that would be awesome.

>But shouldn't that cancel out in a perfectly shuffled deck?
Obviously not, by your formula the probability of having one sequence of at least 2 cards the same color (i.e., not alternating perfectly) would be 0.5^2 * (52/2) = 6.5, but this is absurd because probabilities cannot exceed 1.

The actual formula is the simpler [math]S(n) = S(n-1)+S(n-2)+S(n-3)+S(n-4)[/math] (oeis.org/A000078). What you are doing is incorrect because you are counting sequences multiple times: if you start with a sequence that is part of S(n) and you want to get to get to S(n+4), you can only do this by directly appending a 4, because otherwise the previous parts of the sequence would already be part of the S(n+1...3). For example, if you wanted to get to 5 starting from [math](1) \in S(1)[/math], you cannot do this by appending [math](1,2,1)[/math] because [math](1,1,2) \in S(4)[/math].

After thinking about what the other user said I have found the following recursive relation for [math]S_m (n,k)[/math], the amount of ways to count to [math]n[/math] using exactly [math]k[/math] elements using numbers up to [math]m[/math]:
[eqn]S_m (n,k)=

\begin{cases}
0 & n\leq 0 \\
1 & k=n\lor (k=1\land n\leq m) \\
\sum _{i=1}^m S(n-i,m,k-1) & \text{else} \\
\end{cases}[/eqn]

The probability [math]P(x,y)[/math] to get at least one run of at least [math]y[/math] cards of the same colour in a deck of [math]x[/math] cards is then
[eqn]P(x,y) =1 - \frac{2}{\binom{x}{\frac{x}{2}}} \sum _{i=1}^{\frac{x}{2}} S_{y-1}\left(\frac{x}{2},i\right)
\left(S_{y-1}\left(\frac{x}{2},i\right)+S_{y-1}\left(\frac{x}{2},i-1\right)\right) [/eqn].

That [math]S(n-i,m,k-1)[/math] should read [math]S_m(n-i,k-1)[/math], of course.

Why is k = 4? Shouldn't it be 5?

What's the formula to determine the exact answer?

>0.5^2 * (52/2)
he wrote 0.5^5 * (52/5)
which = 0.325
which is close to the results of

I get 0.7734 after 10 million simulations

Same as

100 million sorry

If you do it with three decks, and someone takes one take away, it improves to 66%

Using software to solve math problem
Can anyone explain me how its done?
DO you write question and software gives you answer?Or are u using calculator software

Im actually getting interested in probability, and have to study it for my pre-college
(I Know it must be shit for you) but do you know where I could find the theory and exercises?

you should play poker user, with such math skills

post the code

holy shit i lold

Okay, this is scary.
I've written another script that does the exact same thing, but from a different approach, and now it's around 76%... This is starting to scare me.