off by 1 lottery probability

Question

A lottery, where 6 balls out of 50 are drawn randomly without replacement, allows players of the lottery to be off by at most 1 for each number on their lottery ticket. Additional rules of the lottery are as follows:

• The balls are numbered 1 thru 50 and are all equally likely to be drawn.

• Both the winning numbers drawn and the players tickets contain random numbers (from 1 to 50). That is, the player does not pick/choose their own numbers, it is done randomly for them via computer.

• Both the winning numbers and the numbers on lottery tickets are sorted in ascending order and winning tickets must match/map in that order. For example, if the winning numbers drawn are (sorted) 5, 10, 15, 16, 20, and 30 and the ticketholder has 5, 10, 16, 17, 20, and 30 (also sorted), the 16s will not map together. The matching numbers are (5:5), (10:10), (15:16), (16:17), (20:20), and (30:30). That is a winning ticket.

So the question is how much more likely is a single lottery ticket expected to be a winner using the off by 1 rule verses a similar but much stricter lottery (also 6 out of 50 balls) but which disallows the off by 1 rule (numbers must match exactly)?

Work done so far:

The strict lottery chances of winning on a single ticket are 1 in about 15.9 million which is 1 / (50 choose 6).

The off by 1 lottery was simulated on computer and I am seeing a 503 increase in probability (about 1 in 31,600 chance of winning).

I would like to know if this type of problem can be done mathematically or if it is too difficult. Also, I was hoping someone could do a simulation also to help verify my finding of 503x increase in chances of winning.

Additional info that may be helpful for analysis... The worst case boost in expected win probability is 7x if (for example), the drawn balls are 1,2,3,4,5,6. This would match the following tickets: (1,2,3,4,5,6), (1,2,3,4,5,7), (1,2,3,4,6,7), (1,2,3,5,6,7), (1,2,4,5,6,7), (1,3,4,5,6,7), and (2,3,4,5,6,7). Best case boost is 729x where the drawn balls are something like 5, 10, 15, 20, 23, 30. The 3 most frequent boost scenarios (from simulation results) are 486x, 648x, and 729x. These are 3 out of 137 scenarios I am seeing in simulation of 100,000,000 decisions. I am not yet sure if there more.

If something is unclear, please ask before attempting to answer the question and I will clarify.

Answer 1

Here's a quick derivation which gives the same solution as that provided by gar, although a slightly different recursion.

A winning $k$ ball combination consists of integer sequences $0<x_1<\cdots<x_k$ and $0<y_1<\cdots<y_k$ so that $|x_i-y_i|\le1$.

Let $A_k(n)$ be the number of ways to pick winning $k$ ball combinations so that $x_k,y_k\le n$. This is the same as $T(n+1,k)$ defined by gar.

Similarly, let $B_k(n)$ be the number of ways to pick $k$ ball combinations so that $x_k\le n$ and $y_k\le n+1$. We'd get the same number of instead we require $x_k\le n+1$ and $y_k\le n$ due to symmetry.

Obviously, $A_k(n)=B_k(n)=0$ for $n<k$. Otherwise, $A_0(n)=B_0(n)=1$.

Let's first consider $A_k(n)$. If $(x_k,y_k)=(n,n)$, what remains is picking the remaining $k-1$ balls with $x_{k-1},y_{k-1}\le n-1$, which can be done in $A_{k-1}(n-1)$ ways. If $(x_k,y_k)=(n,n-1)$, the remaining $k-1$ balls should have $x_{k-1}\le n-1$ and $y_{k-1}\le n-2$, which can be done in $B_{k-1}(n-2)$ ways; the same applies to $(x_k,y_k)=(n-1,n)$. Otherwise, $x_k,y_k\le n-1$, which leaves $A_k(n-1)$ alternatives. Thus, $$ A_k(n)=A_{k-1}(n-1)+2B_{k-1}(n-2)+A_k(n-1). $$

We derive a recursion for $B_k(n)$ in a similar way. If $(x_k,y_k)=(n,n+1)$, the remaining $k-1$ balls require $x_{k-1}\le n-1$, $y_{k-1}\le n$, leaving $B_{k-1}(n-1)$ alternatives. Otherwise, $x_k,y_k\le n$, leaving $A_k(n)$ alternatives. Thus, $$ B_k(n)=B_{k-1}(n-1)+A_k(n). $$

Plugging in $k=6$, $n=50$ gives $A_6(50)=8000567708$. Since each of the two integer sequences are drawn randomly with probability $1/\binom{n}{k}$, this gives the probability of winning $$ \frac{A_6(50)}{\binom{50}{6}^2} =\frac{8000567708}{15890700^2}\approx 0.00003168361647. $$

Answer 2

The results of the "exhaustive" simulation are in. I simulated every possible (sorted) 6 ball drawn outcome (there are 50 choose 6 = 15,890,700 of them). In total, I got 8,000,567,708 (slightly over 8 billion) winning tickets which means there is a 503.48x boost in chances of winning using the off by 1 rule. I had my simulation program print out (to the screen) how many iterations and it did indeed show the correct 15,890,700. Note that even with a very small percentage of randomly simulated 6 ball draws, I was already getting 503x so this exhaustive simulation was not really necessary but it is reassuring. Also the 137 different buckets was confirmed here, meaning there are 137 different boost factors contributing to the final result of 503.48x boost in win probability (vs. the must match exactly lottery).

I welcome other analysis, simulations, and comments about these results and my simulation. If you do your own simulation, please include code and some output for a chance to win bounty of 100 points.

Update:

I have the results of the 137 buckets/categories of winning tickets (from all possible 6 balls combinations). Format of tuples is bucket #, boost amount, frequency (out of $50 \choose 6$ = 15,890,700), [sample 6 balls fitting this category (lowest # balls)], % this category occurs out of the $50 \choose 6$:

1 486 3882669 [1,4,7,10,13,16 ] 24.4335932%
2 729 2760681 [2,5,8,11,14,17 ] 17.3729351%
3 648 2509710 [2,4,7,10,13,16 ] 15.7935774%
4 432 1578938 [1,4,6,9,12,15 ] 9.9362394%
5 324 1280163 [1,4,5,8,11,14 ] 8.0560517%
6 405 805638 [1,3,6,9,12,15 ] 5.0698711%
7 270 665494 [1,3,6,7,10,13 ] 4.1879464%
8 576 442890 [2,4,7,9,12,15 ] 2.7871019%
9 567 295260 [2,4,6,9,12,15 ] 1.8580679%
10 216 219037 [1,2,5,7,10,13 ] 1.3783974%
11 243 212420 [1,2,5,8,11,14 ] 1.3367567%
12 288 167656 [1,4,5,8,10,13 ] 1.0550574%
13 360 160284 [1,3,6,8,11,14 ] 1.0086654%
14 180 136968 [1,3,6,7,10,11 ] 0.8619381%
15 378 105450 [1,4,6,8,11,14 ] 0.6635957%
16 162 88482 [1,2,4,6,9,12 ] 0.5568163%
17 384 78033 [1,4,6,9,11,14 ] 0.4910608%
18 351 71706 [1,3,5,8,11,14 ] 0.4512451%
19 240 70984 [1,3,6,7,10,12 ] 0.4467015%
20 504 50616 [2,4,6,9,11,14 ] 0.3185259%
21 135 40020 [1,2,5,6,8,11 ] 0.2518454%
22 333 27417 [2,4,5,7,10,13 ] 0.1725349%
23 108 26358 [1,2,3,6,9,12 ] 0.1658706%
24 495 25308 [2,4,6,8,11,14 ] 0.1592630%
25 189 21438 [1,2,4,7,10,13 ] 0.1349091%
26 144 16778 [1,2,4,6,9,11 ] 0.1055838%
27 234 13418 [1,3,5,8,9,12 ] 0.0844393%
28 225 9751 [1,3,6,7,9,12 ] 0.0613629%
29 126 9522 [1,2,4,7,8,11 ] 0.0599218%
30 90 8690 [1,2,4,6,48,50 ] 0.0546861%
31 512 8436 [2,4,7,9,12,14 ] 0.0530877%
32 120 6720 [1,2,5,7,48,50 ] 0.0422889%
33 150 6595 [1,3,6,7,8,11 ] 0.0415023%
34 192 6318 [1,2,5,7,10,12 ] 0.0397591%
35 312 5776 [1,3,5,8,10,13 ] 0.0363483%
36 315 5776 [1,3,6,8,10,13 ] 0.0363483%
37 72 5288 [1,2,3,5,8,10 ] 0.0332773%
38 198 4602 [1,3,4,6,9,12 ] 0.0289603%
39 222 4524 [1,4,6,7,9,12 ] 0.0284695%
40 252 4370 [1,4,5,8,10,12 ] 0.0275004%
41 306 4370 [1,3,5,7,10,13 ] 0.0275004%
42 330 4294 [1,4,6,8,10,13 ] 0.0270221%
43 105 3522 [1,2,4,7,8,10 ] 0.0221639%
44 96 3280 [1,2,3,6,8,11 ] 0.0206410%
45 160 3120 [1,4,5,6,9,11 ] 0.0196341%
46 186 3120 [2,3,4,6,8,11 ] 0.0196341%
47 168 2964 [1,2,4,7,9,12 ] 0.0186524%
48 336 2812 [1,4,6,8,11,13 ] 0.0176959%
49 81 2546 [1,2,3,5,8,11 ] 0.0160219%
50 45 1808 [1,2,3,4,7,10 ] 0.0113777%
51 63 1804 [1,2,4,7,49,50 ] 0.0113526%
52 171 1718 [1,3,4,6,8,11 ] 0.0108114%
53 210 1636 [1,3,6,8,10,50 ] 0.0102953%
54 296 1482 [2,4,5,7,10,12 ] 0.0093262%
55 320 1406 [1,3,6,8,11,13 ] 0.0088479%
56 440 1406 [2,4,6,8,11,13 ] 0.0088479%
57 100 943 [1,3,5,7,8,9 ] 0.0059343%
58 256 703 [1,4,6,9,11,50 ] 0.0044240%
59 441 703 [2,4,6,9,11,13 ] 0.0044240%
60 60 539 [1,2,3,5,7,9 ] 0.0033919%
61 84 486 [1,2,3,6,8,10 ] 0.0030584%
62 195 388 [1,3,5,8,9,11 ] 0.0024417%
63 117 361 [1,2,5,6,8,10 ] 0.0022718%
64 132 318 [1,3,4,6,9,10 ] 0.0020012%
65 204 310 [1,3,5,7,10,11 ] 0.0019508%
66 54 287 [1,2,3,5,8,9 ] 0.0018061%
67 70 248 [1,2,4,7,8,9 ] 0.0015607%
68 114 244 [1,3,4,6,8,50 ] 0.0015355%
69 99 242 [1,2,4,6,7,10 ] 0.0015229%
70 30 168 [1,2,3,4,7,8 ] 0.0010572%
71 40 168 [1,2,3,4,7,9 ] 0.0010572%
72 48 166 [1,2,3,6,7,50 ] 0.0010446%
73 124 160 [1,4,5,6,8,10 ] 0.0010069%
74 112 158 [1,2,4,7,9,50 ] 0.0009943%
75 147 158 [1,2,4,7,9,11 ] 0.0009943%
76 177 158 [1,3,5,6,8,11 ] 0.0009943%
77 156 156 [1,3,5,8,9,50 ] 0.0009817%
78 267 154 [1,3,5,7,9,12 ] 0.0009691%
79 64 122 [1,2,3,6,8,50 ] 0.0007677%
80 36 90 [1,2,3,5,6,8 ] 0.0005664%
81 42 90 [1,2,3,5,7,8 ] 0.0005664%
82 18 86 [1,2,3,4,5,8 ] 0.0005412%
83 75 84 [1,2,4,5,7,9 ] 0.0005286%
84 102 84 [1,2,44,46,48,50 ] 0.0005286%
85 33 82 [1,2,3,4,6,9 ] 0.0005160%
86 87 82 [1,2,4,5,7,10 ] 0.0005160%
87 69 80 [1,2,3,5,7,10 ] 0.0005034%
88 111 80 [1,2,5,7,8,10 ] 0.0005034%
89 130 80 [1,3,5,8,9,10 ] 0.0005034%
90 165 80 [1,2,5,7,9,11 ] 0.0005034%
91 141 78 [1,2,4,6,8,11 ] 0.0004909%
92 176 78 [1,3,4,6,9,11 ] 0.0004909%
93 185 78 [1,3,6,8,9,11 ] 0.0004909%
94 251 78 [2,4,5,7,9,11 ] 0.0004909%
95 208 76 [1,3,5,8,10,50 ] 0.0004783%
96 272 76 [1,3,5,7,10,12 ] 0.0004783%
97 273 76 [1,3,5,8,10,12 ] 0.0004783%
98 275 76 [1,3,6,8,10,12 ] 0.0004783%
99 28 47 [1,2,3,4,6,8 ] 0.0002958%
100 161 40 [2,4,5,7,8,10 ] 0.0002517%
101 148 39 [1,4,6,7,9,50 ] 0.0002454%
102 249 39 [2,4,6,7,9,11 ] 0.0002454%
103 200 38 [1,3,6,8,48,50 ] 0.0002391%
104 220 38 [1,4,6,8,10,50 ] 0.0002391%
105 377 38 [2,4,6,8,10,12 ] 0.0002391%
106 66 6 [1,2,4,6,7,50 ] 0.0000378%
107 22 4 [1,2,3,4,6,50 ] 0.0000252%
108 25 4 [1,2,3,4,48,50 ] 0.0000252%
109 27 4 [1,2,3,5,49,50 ] 0.0000252%
110 46 4 [1,2,3,5,7,50 ] 0.0000252%
111 52 4 [1,2,3,46,48,50 ] 0.0000252%
112 7 2 [1,2,3,4,5,6 ] 0.0000126%
113 12 2 [1,2,3,4,5,50 ] 0.0000126%
114 13 2 [1,2,3,4,5,7 ] 0.0000126%
115 15 2 [1,2,3,4,49,50 ] 0.0000126%
116 51 2 [1,2,4,5,7,8 ] 0.0000126%
117 55 2 [1,3,5,6,7,8 ] 0.0000126%
118 57 2 [1,3,4,5,7,8 ] 0.0000126%
119 58 2 [1,2,4,5,7,50 ] 0.0000126%
120 76 2 [1,3,5,6,7,50 ] 0.0000126%
121 78 2 [1,3,4,6,7,50 ] 0.0000126%
122 85 2 [1,3,4,5,7,9 ] 0.0000126%
123 91 2 [1,2,4,46,48,50 ] 0.0000126%
124 94 2 [1,2,4,6,8,50 ] 0.0000126%
125 95 2 [1,3,4,6,7,9 ] 0.0000126%
126 110 2 [1,3,4,6,48,50 ] 0.0000126%
127 118 2 [1,3,5,6,8,50 ] 0.0000126%
128 123 2 [1,2,4,6,8,10 ] 0.0000126%
129 149 2 [1,3,4,6,8,10 ] 0.0000126%
130 153 2 [1,3,5,6,8,10 ] 0.0000126%
131 155 2 [1,3,5,7,8,10 ] 0.0000126%
132 170 2 [1,3,5,7,48,50 ] 0.0000126%
133 178 2 [1,3,5,7,9,50 ] 0.0000126%
134 233 2 [1,3,5,7,9,11 ] 0.0000126%
135 16 1 [1,2,3,48,49,50 ] 0.0000063%
136 49 1 [1,2,4,47,49,50 ] 0.0000063%
137 169 1 [1,3,5,46,48,50 ] 0.0000063%

These results should be 100% accurate now since they are not from random 6 ball combos, they are from all possible 6 ball combos (out of 50 possible) counting each only once. If I multiply the boost amount by the occurring percentage of each bucket, I get an overall (weighted average) boost value of 503.4748449x. That should be the "mathematically" correct answer (using a computer).

Here is something else interesting. Bucket 20 has a boost factor of 504x. That is almost identical to the average of 503.47...x but just with a single case/bucket (out of 137). It seems very rare that something like that would happen for a problem so complex but that reinforces my observation and point that the boost factors are spread out rather uniformly over a 7x to 729x range.

Also here is something else interesting: Running the nested loops starting at {1,2,3,4,5,6] and proceeding sequentially revealed that bucket 137 (not sorted by frequency yet) was "hit" very early on (at 6 ball sequence [2,5,8,11,14,17]). It seems like any 6 balls sequence after that will fall into one of the already seen 137 buckets. This is somewhat surprising since the nested loops have to run up to [45,46,47,48,49,50].

Answer 3

You've already seen there are different cases of winning numbers $a_1 < \dots < a_6$. That is, the number of winning tickets under the off-by-one rule varies based on the gaps between the winning numbers. You can model the different cases as $7$-tuples $(x_0, x_1, x_2, x_3, x_4, x_5, x_6)$. Here $x_i$ denotes the gap between the $i$-th and $i+1$-th number for $1 \leq i \leq 5$, so $x_i = a_{i+1} - a_i$. The $x_0$ and $x_6$ denote the gap between the "edges", that is, the numbers 1 and 50, so $x_0 = a_1 - 1$ and $x_6 = 50 - a_6$.

For achieving the maximum number of winning tickets we have two "empty spots" around each $a_i$ that don't overlap with the other empty spots. Then, for each $a_i$ we have 3 matching numbers under the off-by-one rule, independently, so the number of winning tickets is $3^6 = 729$. The condition on the $x_i$ is that for $1 \leq i \leq 5$ we have $x_i \geq 2$ (for if $x_i = 1$ then we have one "overlapping gap" between two numbers), and we have $x_0, x_6 \geq 1$. Otherwise, we want the $x_i$ to sum to $50-6 = 44$. The number of winning numbers that meets these conditions is ${44 - 5-1\choose 7-1} = {38 \choose 6}$ (Stars and bars, where we first subtract 1 from each $x_i$ for $1 \leq i \leq 5$, so we're looking for 7-tuples of positive integers that sum to $44-5 = 39$)

The full answer can be computed by considering all different conditions for the $x_i$ . For $1 \leq i \leq 5$ we have 3 conditions: $x_i = 0 \vee x_i = 1 \vee x_i \geq 2$. For $i \in \{0, 6\}$ we have either $x_i = 0$ or $x_i \geq 1$.

For example, fixing $x_i = 1$ for a single $1 \leq i \leq 5$ and leaving the other conditions as in the maximum situation we just computed, we have a single "overlapping gap" between two numbers, hence the number of matching tickets will be $3^4 \cdot 8 = 648$. The number of winning numbers that match this will be ${39 \choose 5} \cdot 5$, where multiplication with 5 follows from that we can pick $i \in \{1, 2, 3, 4, 5\}$.

As we saw here, the $x_i$ do not play a unique role, i.e. they are basically symmetric (besides the difference between the "interior" ones and the ones at the edges). However, fixing two adjacent $x_i$ is different from fixing two non-adjacent $x_i$.

Answer 4

The probability of winning is given by \begin{align*} P(win) &= \frac{T(n+1,k)}{\dbinom{n}{k}^2} \end{align*} where $T(n,k)$ is computed by the recurrence relation \begin{align*} T(n,k) &= T(n-1,k) + 2*T(n-1,k-1) + T(n-2,k-1) - T(n-2,k-2)\\ T(0,0) = T(1,0) = T(2,0) = T(2,1) &= 1\\ T(1,1) = T(2,2) &= 0 \\ T(n,k) &= 0 \;\;\;\;\;\;\text{if $k<0$ or $k>n$} \end{align*} as given in A209414

Hence, for $n=50, k=6$, the resulting probability is \begin{align*} P(win) &= \frac{8000567708}{\dbinom{50}{6}^2}\approx 0.0000316836 \end{align*}

I have matched with simulations for small values and they seem to agree.

For example, in J:

   n=: 9
   k=: 5
   sim=: 3 : 0
a=:/:~k?n
win=:/:~k?n
k=(+/0=|a-win)+(+/1=|a-win)
)
   (+/%#)(sim"0)1e6#0

which gave about 0.28, close to actual $\dfrac{4446}{\dbinom{9}{5}^2}\approx 0.280045351473923$

Update

Some implementations,

In python:

def memoize(f):
    """ Memoization decorator for functions taking one or more arguments. """
    class memodict(dict):
        def __init__(self, f):
            self.f = f
        def __call__(self, *args):
            return self[args]
        def __missing__(self, key):
            ret = self[key] = self.f(*key)
            return ret
    return memodict(f)

@memoize
def T(n,k):
    if n == 0 and k == 0:
        return 1
    if n == 1 and k == 0:
        return 1
    if n == 2 and k == 1:
        return 1                
    if n == 2 and k == 0:
        return 1   
    if n == 1 and k== 1:
        return 0
    if n == 2 and k == 2:
        return 0
    if n < k or k< 0:     
        return 0
    return T(n-1,k) + 2*T(n-1,k-1) + T(n-2,k-1) - T(n-2,k-2)
nn = 50
kk = 6
print T(nn+1,kk)

The memoization decorator is taken from here

If a CAS is used, it's easier to implement. E.g., in FriCAS:

)set fun cache all A
T(0,0) == 1
T(1,0) == 1
T(2,0) == 1
T(2,1) == 1
T(1,1) == 0
T(2,2) == 0
T(n,k) == 
  if k<0 or k>n then 0
  else T(n-1,k) + 2*T(n-1,k-1) + T(n-2,k-1) - T(n-2,k-2)
T(51,6)

and Einar Rødland's formula:

)set fun cache all A
)set fun cache all B
A(n,0) == 1
B(n,0) == 1
A(n,k) == 
    if k>n then 0
    else A(n-1,k-1)+2*B(n-2,k-1)+A(n-1,k)
B(n,k) == 
    if k>n then 0
    else B(n-1,k-1)+A(n,k)
A(50,6)