Archive for combinatorics

almost reversed 2-lag Markov chain

Posted in Kids, R, Statistics with tags , , , , on July 7, 2021 by xi'an

Another simple riddle from the Riddler: take a binary sequence and associate to this sequence a score vector made of the numbers of consecutive ones from each position. If the sequence is ten step long and there are 3 ones located at random, what is the expected total score? (The original story is much more complex and involves as often strange sports!)

Adding two zeroes at time 11 and 12, this is quite simple to code, e.g.

f=0*(1:10) #frequencies
for(v in 1:1e6){
 r=0*f#reward
 s=sample(1:10,3)
 for(t in s)r[t]=1+((t+1)%in%s)*(1+((t+2)%in%s))
 f[sum(r)]=f[sum(r)]+1}
f=f/1e6

and the outcome recovers the feature that the only possible scores are 1+1+1=3 (all ones separated), 1+1+2=4 (two ones contiguous),  and 1+2+3=6 (all ones contiguous). With respective frequencies 56/120, 56/120, and 8/120. With 120 being the number of possible locations of the 3 ones.

Bernoulli factory in the Riddler

Posted in Books, Kids, R, Statistics with tags , , , , , , , , , , on December 1, 2020 by xi'an

“Mathematician John von Neumann is credited with figuring out how to take a p biased coin and “simulate” a fair coin. Simply flip the coin twice. If it comes up heads both times or tails both times, then flip it twice again. Eventually, you’ll get two different flips — either a heads and then a tails, or a tails and then a heads, with each of these two cases equally likely. Once you get two different flips, you can call the second of those flips the outcome of your “simulation.” For any value of p between zero and one, this procedure will always return heads half the time and tails half the time. This is pretty remarkable! But there’s a downside to von Neumann’s approach — you don’t know how long the simulation will last.” The Riddler

The associated riddle (first one of the post-T era!) is to figure out what are the values of p for which an algorithm can be derived for simulating a fair coin in at most three flips. In one single flip, p=½ sounds like the unique solution. For two flips, p²,(1-p)^2,2p(1-p)=½ work, but so do p+(1-p)p,(1-p)+p(1-p)=½, and the number of cases grows for three flips at most. However, since we can have 2³=8 different sequences, there are 2⁸ ways to aggregate these events and thus at most 2⁸ resulting probabilities (including 0 and 1). Running a quick R code and checking for proximity to ½ of any of these sums leads to

[1] 0.2062997 0.7937005 #p^3
[1] 0.2113249 0.7886753 #p^3+(1-p)^3
[1] 0.2281555 0.7718448 #p^3+p(1-p)^2
[1] 0.2372862 0.7627143 #p^3+(1-p)^3+p(1-p)^2
[1] 0.2653019 0.7346988 #p^3+2p(1-p)^2
[1] 0.2928933 0.7071078 #p^2
[1] 0.3154489 0.6845518 #p^3+2p^2(1-p)
[1] 0.352201  0.6477993 #p^3+p(1-p)^2+p^2(1-p)
[1] 0.4030316 0.5969686 #p^3+p(1-p)^2+3(1-p)p^2
[1] 0.5

which correspond to

1-p³=½, p³+(1-p)³=½,(1-p)³+(1-p)p²=½,p³+(1-p)³+p²(1-p),(1-p)³+2(1-p)p²=½,1-p²=½, p³+(1-p)³+p²(1-p)=½,(1-p)³+p(1-p)²+p²(1-p)=½,(1-p)³+p²(1-p)+3p(1-p)²=½,p³+p(1-p)²+3(p²(1-p)=½,p³+2p(1-p)²+3(1-p)p²=½,p=½,

(plus the symmetric ones), leading to 19 different values of p producing a “fair coin”. Missing any other combination?!

Another way to look at the problem is to find all roots of the 2^{2^n} equations

a_0p^n+a_1p^{n-1}(1-p)+\cdots+a_{n-1}p(1-p)^{n-1}+a_n(1-p)^n=1/2

where

0\le a_i\le{n \choose i}

(None of these solutions is rational, by the way, except p=½.) I also tried this route with a slightly longer R code, calling polyroot, and finding the same 19 roots for three flips, [at least] 271 for four, and [at least] 8641 for five (The Riddler says 8635!). With an imprecision in the exact number of roots due to rather poor numerical rounding by polyroot. (Since the coefficients of the above are not directly providing those of the polynomial, I went through an alternate representation as a polynomial in (1-p)/p, with a straightforward derivation of the coefficients.)

parking riddle

Posted in Books, Kids, pictures, R, Statistics, Travel with tags , , , , , , on October 23, 2020 by xi'an

The Riddler of this week had a quick riddle: if one does want to avoid parallel parking a car over a six spot street, either the first spot is available or two consecutive spots are free. What is the probability this happens with 4 other cars already parked (at random)?

While a derivation by combinatorics easily returns 9/15 as the probability to fail to park, a straightforward R code does as well

 l=0
  for(t in 1:1e6){
  k=sort(sample(0:5,4))
  l=l+1*(!!k[1]|3%in%diff(k)|!k[4]%%3)}

since

 
> round(choose(6,2)*F/1e6)
[1] 10

Le Monde puzzle [#1121]

Posted in Books, Kids with tags , , , , on December 17, 2019 by xi'an

A combinatoric puzzle as Le weekly Monde current mathematical puzzle:

A class of 75<n<100 students is divided at random into two groups of sizes a and b=n-a, respectively, such that the probability that two particular students Ji-ae and Jung-ah have a probability of exactly 1/2 to be in the same group. Find a and n.

(with an original wording mentioning an independent allocation to the group!). Since the probability to be in the same group (under a simple uniform partition distribution) is

\frac{a(1-1)}{n(n-1)}+\frac{b(b-1)}{n(n-1)}

it is sufficient to seek by exhaustion values of (a,b) such that this ratio is equal to ½. The only solution within the right range is then (36,45) (up to the symmetric pair). This can be also found by seeking integer solutions to the second degree polynomial equation, namely

b^\star=\left[ 1+2a\pm\sqrt{1+8a}\right]/2 \in \mathbb N

numbers of numbers with numbers of their numbers

Posted in Statistics with tags , , , on April 6, 2019 by xi'an

A funny riddle from The Riddler where the number of numbers that indicate the numbers of their numbers is requested. By which one means numbers like 22 (two 2’s) and 21322314 (two 1’s, three 2’s, two 3’s and one 4), the convention being that “numbers consist of alternating tallies and numerals”. And that numerals are “tallied in increasing order”. A reasoning based on the number of 1’s, from zero (where 22 seems to be the only possibility) to six (where 613223141516171819 is the only case) leads to a total of 59 cases (unless zero counts as an extra case) and a brute force R exploration returns the same figure:

for (t in 1:1e5){
  az=sample((0:6),9,rep=TRUE)
  count=rep(TRUE,9)
  for (i in 1:9) count[i]=(sum(az==i)+(az[i]>0))==az[i]
  nit=0
  while ((min(count)==0)&(nit<1e2)){      
    j=sample((1:9)[!count],1)      
    az[j]=(sum(az==j)+(az[j]>0))
    nit=nit+1}
  if (min(count)==1) solz=unique.matrix(rbind(solz,az),mar=1)}

The solution published on The Riddler differs because it also includes numbers with zeros. Which I find annoying to the extreme because if zeroes are allowed then every digit not in the original solution should appear as multiplied by 0, which is self-contradictory… For instance 22 should be 012203…09, except then there is one 1, one 3, and so on.