The fairness of playing card shuffles

%23%20%2F%2F%2F%20script%0A%23%20requires-python%20%3D%20%22%3E%3D3.12%22%0A%23%20dependencies%20%3D%20%5B%0A%23%20%20%20%20%20%22marimo%3D%3D0.23.9%22%2C%0A%23%20%20%20%20%20%22altair%3D%3D6.2.1%22%2C%0A%23%20%20%20%20%20%22numpy%3D%3D2.3.5%22%2C%0A%23%20%5D%0A%23%0A%23%20%5Btool.folio.export%5D%0A%23%20slug%20%3D%20%22shuffle-entropy%22%0A%23%20show_code%20%3D%20true%0A%23%20%2F%2F%2F%0A%0Aimport%20marimo%0A%0A__generated_with%20%3D%20%220.23.9%22%0Aapp%20%3D%20marimo.App(%0A%20%20%20%20width%3D%22medium%22%2C%0A%20%20%20%20app_title%3D%22The%20fairness%20of%20playing%20card%20shuffles%22%2C%0A)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20textwrap%0A%0A%20%20%20%20return%20mo%2C%20textwrap%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20The%20fairness%20of%20playing%20card%20shuffles%0A%0A%20%20%20%20For%20a%20shuffle%20to%20be%20fair%2C%20the%20order%20of%20the%20cards%20after%20the%20shuffle%20should%20not%20depend%20on%20the%20order%20of%20the%20cards%20before%20the%20shuffle.%20If%20someone%20knew%20where%20a%20card%20was%20before%20the%20shuffle%20and%20then%20tries%20to%20guess%20where%20it%20is%20after%20the%20shuffle%2C%20then%20if%20the%20shuffle%20was%20fair%2C%20they%20should%20have%20no%20edge%20over%20someone%20else%20guessing%20uniformly%20at%20random.%0A%0A%20%20%20%20The%20shuffle%20must%20have%20an%20element%20of%20randomness%20to%20achieve%20this.%20A%20deterministic%20shuffle%20leaves%20every%20card%20in%20an%20exactly%20known%20position%20in%20the%20deck%20so%20cannot%20be%20fair.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Shuffle%20types%0A%0A%20%20%20%20Here%20are%20definitions%20of%20a%20few%20common%20types%20of%20shuffle.%0A%0A%20%20%20%20%23%23%23%20Riffle%0A%0A%20%20%20%20Take%20the%20deck%20approximately%20in%20two%20halves%20and%20interleave%20the%20cards%20from%20each%20half%20with%20varying%20numbers%20of%20cards%20at%20each%20interleaf.%0A%0A%20%20%20%20%23%23%23%20Box%0A%0A%20%20%20%20Cut%20the%20deck%20approximately%20into%20four%20quarters%20and%20reverse%20the%20order%20of%20these%20quarters.%20There%20should%20be%20an%20element%20of%20randomness%20in%20the%20number%20of%20cards%20which%20go%20into%20each%20quarter%20-%20some%20distribution%20around%2013%20cards%20in%20each%20part.%0A%0A%20%20%20%20%23%23%23%20Cut%0A%0A%20%20%20%20As%20with%20box%2C%20cut%20the%20deck%20approximately%20in%20two%20and%20reverse%20their%20orders.%0A%0A%20%20%20%20%23%23%23%20The%20standard%20shuffle%20in%20the%20World%20Series%20of%20Poker%0A%0A%20%20%20%20Riffle%2C%20riffle%2C%20box%2C%20riffle%2C%20cut.%0A%0A%20%20%20%20%23%23%23%20Shuffle%20types%20as%20code%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20from%20collections.abc%20import%20Callable%0A%20%20%20%20from%20math%20import%20floor%2C%20log%0A%20%20%20%20import%20altair%20as%20alt%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20from%20numpy.typing%20import%20NDArray%0A%0A%20%20%20%20chart_line_width%3A%20float%20%3D%202.4%0A%0A%20%20%20%20def%20chart_config(chart%3A%20alt.Chart%20%7C%20alt.LayerChart)%20-%3E%20alt.Chart%20%7C%20alt.LayerChart%3A%0A%20%20%20%20%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20chart.configure_axis(labelFontSize%3D12%2C%20titleFontSize%3D13)%0A%20%20%20%20%20%20%20%20%20%20%20%20.configure_legend(labelFontSize%3D12%2C%20titleFontSize%3D13)%0A%20%20%20%20%20%20%20%20%20%20%20%20.configure_title(fontSize%3D16)%0A%20%20%20%20%20%20%20%20%20%20%20%20.configure_view(strokeWidth%3D0)%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20def%20inset_legend()%20-%3E%20alt.Legend%3A%0A%20%20%20%20%20%20%20%20return%20alt.Legend(%0A%20%20%20%20%20%20%20%20%20%20%20%20orient%3D%22top-right%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20padding%3D6%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20fillColor%3D%22white%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20strokeColor%3D%22%23ddd%22%2C%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20Callable%2C%0A%20%20%20%20%20%20%20%20NDArray%2C%0A%20%20%20%20%20%20%20%20alt%2C%0A%20%20%20%20%20%20%20%20chart_config%2C%0A%20%20%20%20%20%20%20%20chart_line_width%2C%0A%20%20%20%20%20%20%20%20floor%2C%0A%20%20%20%20%20%20%20%20inset_legend%2C%0A%20%20%20%20%20%20%20%20log%2C%0A%20%20%20%20%20%20%20%20np%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell%0Adef%20_(NDArray%2C%20np)%3A%0A%20%20%20%20def%20riffle(deck%3A%20NDArray%5Bnp.integer%5D)%20-%3E%20NDArray%5Bnp.integer%5D%3A%0A%20%20%20%20%20%20%20%20result%3A%20NDArray%5Bnp.float64%5D%20%3D%20np.random.rand(len(deck))%0A%20%20%20%20%20%20%20%20result%20%3D%20np.sort(result)%0A%20%20%20%20%20%20%20%20result%20%3D%202%20*%20result%20%25%201%0A%20%20%20%20%20%20%20%20return%20deck%5Bnp.argsort(result)%5D%0A%0A%20%20%20%20def%20box(deck%3A%20NDArray%5Bnp.integer%5D)%20-%3E%20NDArray%5Bnp.integer%5D%3A%0A%20%20%20%20%20%20%20%20deck_len%3A%20int%20%3D%20len(deck)%0A%20%20%20%20%20%20%20%20n1%3A%20int%20%3D%20np.random.binomial(deck_len%2C%200.25)%0A%20%20%20%20%20%20%20%20n2%3A%20int%20%3D%20np.random.binomial(deck_len%20-%20n1%2C%200.333333)%20%2B%20n1%0A%20%20%20%20%20%20%20%20n3%3A%20int%20%3D%20np.random.binomial(deck_len%20-%20n2%2C%200.5)%20%2B%20n2%0A%20%20%20%20%20%20%20%20return%20np.concatenate((deck%5Bn3%3A%5D%2C%20deck%5Bn2%3An3%5D%2C%20deck%5Bn1%3An2%5D%2C%20deck%5B%3An1%5D))%0A%0A%20%20%20%20def%20cut(deck%3A%20NDArray%5Bnp.integer%5D)%20-%3E%20NDArray%5Bnp.integer%5D%3A%0A%20%20%20%20%20%20%20%20return%20np.roll(deck%2C%20np.random.binomial(len(deck)%2C%200.5))%0A%0A%20%20%20%20def%20shuffle(deck%3A%20NDArray%5Bnp.integer%5D)%20-%3E%20NDArray%5Bnp.integer%5D%3A%0A%20%20%20%20%20%20%20%20return%20cut(riffle(box(riffle(riffle(deck)))))%0A%0A%20%20%20%20def%20perfect_shuffle(deck%3A%20NDArray%5Bnp.integer%5D)%20-%3E%20NDArray%5Bnp.integer%5D%3A%0A%20%20%20%20%20%20%20%20return%20deck%5Bnp.argsort(np.random.rand(len(deck)))%5D%0A%0A%20%20%20%20return%20box%2C%20cut%2C%20perfect_shuffle%2C%20riffle%2C%20shuffle%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Here's%20a%20graphical%20example%20of%20each%20type%20of%20shuffle.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20Callable%2C%0A%20%20%20%20NDArray%2C%0A%20%20%20%20alt%2C%0A%20%20%20%20box%2C%0A%20%20%20%20chart_config%2C%0A%20%20%20%20chart_line_width%3A%20float%2C%0A%20%20%20%20cut%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20np%2C%0A%20%20%20%20perfect_shuffle%2C%0A%20%20%20%20riffle%2C%0A%20%20%20%20shuffle%2C%0A)%3A%0A%20%20%20%20_deck_size%3A%20int%20%3D%2052%0A%20%20%20%20_deck%3A%20NDArray%5Bnp.integer%5D%20%3D%20np.arange(_deck_size)%0A%0A%20%20%20%20shuffle_functions%3A%20list%5BCallable%5B%5BNDArray%5Bnp.integer%5D%5D%2C%20NDArray%5Bnp.integer%5D%5D%5D%20%3D%20%5B%0A%20%20%20%20%20%20%20%20cut%2C%0A%20%20%20%20%20%20%20%20box%2C%0A%20%20%20%20%20%20%20%20riffle%2C%0A%20%20%20%20%20%20%20%20shuffle%2C%0A%20%20%20%20%20%20%20%20perfect_shuffle%2C%0A%20%20%20%20%5D%0A%0A%20%20%20%20shuffled_decks%3A%20list%5BNDArray%5Bnp.integer%5D%5D%20%3D%20%5B%0A%20%20%20%20%20%20%20%20shuffle_function(_deck)%20for%20shuffle_function%20in%20shuffle_functions%0A%20%20%20%20%5D%0A%0A%20%20%20%20x_labels%3A%20list%5Bstr%5D%20%3D%20%5B%22Before%22%2C%20%22After%22%5D%0A%20%20%20%20_charts%3A%20list%5Balt.Chart%20%7C%20alt.LayerChart%5D%20%3D%20%5B%5D%0A%20%20%20%20for%20shuffled_deck%2C%20shuffle_function%20in%20zip(shuffled_decks%2C%20shuffle_functions)%3A%0A%20%20%20%20%20%20%20%20_rows%3A%20list%5Bdict%5Bstr%2C%20int%20%7C%20str%5D%5D%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20_i%20in%20_deck%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_before_position%3A%20int%20%3D%20int(shuffled_deck%5B_i%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20_rows.append(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22card%22%3A%20int(_i)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22before_position%22%3A%20_before_position%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22label%22%3A%20x_labels%5B0%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22position%22%3A%20_before_position%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20_rows.append(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22card%22%3A%20int(_i)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22before_position%22%3A%20_before_position%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22label%22%3A%20x_labels%5B1%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22position%22%3A%20int(_i)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20_charts.append(%0A%20%20%20%20%20%20%20%20%20%20%20%20chart_config(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20alt.Chart(alt.Data(values%3D_rows)%2C%20title%3Dshuffle_function.__name__)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20.mark_line(opacity%3D0.7%2C%20strokeWidth%3Dchart_line_width)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20.encode(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20x%3Dalt.X(%22label%3AN%22%2C%20title%3DNone%2C%20sort%3Dx_labels)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20y%3Dalt.Y(%22position%3AQ%22%2C%20title%3D%22Card%20position%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3Dalt.Color(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22before_position%3AQ%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20scale%3Dalt.Scale(scheme%3D%22magma%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20legend%3DNone%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20detail%3D%22card%3AN%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20.properties(width%3D%22container%22%2C%20height%3D204)%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20mo.vstack(_charts%2C%20align%3D%22stretch%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20textwrap)%3A%0A%20%20%20%20mo.md(textwrap.dedent(r%22%22%22%0A%20%20%20%20A%20large%20number%20of%20shuffles%2C%20%60num_shuffles%60%2C%20are%20simulated%20using%20the%20shuffle%20defined%20above.%20For%20each%20shuffle%2C%20the%20final%20position%20of%20each%20card%20is%20kept%20track%20of%20in%20a%20%60deck_size%60%20%24%5Ctimes%24%20%60deck_size%60%20array%2C%20building%20up%20a%20histogram%20of%20final%20positions%20of%20each%20card.%0A%20%20%20%20%22%22%22))%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(NDArray%2C%20np%2C%20shuffle)%3A%0A%20%20%20%20deck_size%3A%20int%20%3D%2052%0A%20%20%20%20deck%3A%20NDArray%5Bnp.integer%5D%20%3D%20np.arange(deck_size)%0A%0A%20%20%20%20num_shuffles%3A%20int%20%3D%2030000%0A%20%20%20%20shuffle_weight%3A%20float%20%3D%201%20%2F%20num_shuffles%0A%0A%20%20%20%20position_distributions%3A%20NDArray%5Bnp.float64%5D%20%3D%20np.zeros(%5Bdeck_size%2C%20deck_size%5D)%0A%0A%20%20%20%20for%20_i%20in%20range(num_shuffles)%3A%0A%20%20%20%20%20%20%20%20shuffled%3A%20NDArray%5Bnp.integer%5D%20%3D%20shuffle(deck)%0A%20%20%20%20%20%20%20%20for%20position%20in%20range(deck_size)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20position_distributions%5Bshuffled%5Bposition%5D%5D%5Bposition%5D%20%2B%3D%20shuffle_weight%0A%20%20%20%20return%20deck_size%2C%20position_distributions%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20textwrap)%3A%0A%20%20%20%20mo.md(textwrap.dedent(r%22%22%22%0A%20%20%20%20Example%20histograms%20are%20shown%20below%20for%20the%20final%20position%20of%20a%20card%20which%20started%20at%20the%20top%20of%20the%20deck%2C%20another%20card%20which%20started%20in%20the%20middle%2C%20and%20one%20at%20the%20bottom.%0A%0A%20%20%20%20When%20trying%20to%20guess%20where%20the%20card%20on%20the%20bottom%20of%20the%20deck%20ended%20up%2C%20guessing%20that%20it's%20somewhere%20in%20the%20bottom%20half%20of%20the%20deck%20will%20be%20correct%20more%20than%20half%20the%20time%20because%20it%20hasn't%20been%20shuffled%20uniformly.%20The%20card%20which%20started%20in%20the%20middle%20of%20the%20deck%20is%20more%20uniformly%20distributed.%0A%20%20%20%20%22%22%22))%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20alt%2C%0A%20%20%20%20chart_config%2C%0A%20%20%20%20chart_line_width%3A%20float%2C%0A%20%20%20%20deck_size%3A%20int%2C%0A%20%20%20%20inset_legend%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20position_distributions%3A%20%22NDArray%5Bnp.float64%5D%22%2C%0A)%3A%0A%20%20%20%20_rows%3A%20list%5Bdict%5Bstr%2C%20float%20%7C%20int%20%7C%20str%5D%5D%20%3D%20%5B%5D%0A%20%20%20%20for%20card_label%2C%20card_index%20in%20%5B(%22Top%22%2C%200)%2C%20(%22Middle%22%2C%2025)%2C%20(%22Bottom%22%2C%2051)%5D%3A%0A%20%20%20%20%20%20%20%20for%20_position%2C%20_probability%20in%20enumerate(position_distributions%5Bcard_index%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_rows.append(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22card%22%3A%20card_label%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22position%22%3A%20_position%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22probability%22%3A%20_probability%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20distribution_chart%20%3D%20(%0A%20%20%20%20%20%20%20%20chart_config(%0A%20%20%20%20%20%20%20%20%20%20%20%20alt.Chart(alt.Data(values%3D_rows))%0A%20%20%20%20%20%20%20%20%20%20%20%20.mark_line(strokeWidth%3Dchart_line_width)%0A%20%20%20%20%20%20%20%20%20%20%20%20.encode(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20x%3Dalt.X(%22position%3AQ%22%2C%20title%3D%22Final%20card%20position%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20y%3Dalt.Y(%22probability%3AQ%22%2C%20title%3D%22Probability%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3Dalt.Color(%22card%3AN%22%2C%20title%3DNone%2C%20legend%3Dinset_legend())%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20.properties(width%3D%22container%22%2C%20height%3D360)%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20)%0A%0A%20%20%20%20bottom_half_probability%3A%20float%20%3D%20sum(%0A%20%20%20%20%20%20%20%20position_distributions%5Bdeck_size%20-%201%5D%5Bdeck_size%20%2F%2F%202%20%3A%5D%0A%20%20%20%20)%0A%20%20%20%20middle_half_probability%3A%20float%20%3D%20sum(%0A%20%20%20%20%20%20%20%20position_distributions%5Bdeck_size%20%2F%2F%202%5D%5Bdeck_size%20%2F%2F%202%20%3A%5D%0A%20%20%20%20)%0A%0A%20%20%20%20mo.vstack(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20distribution_chart%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22%22%22Probability%20of%20the%20bottom%20card%20ending%20up%20in%20the%20bottom%20half%20of%20the%20deck%3A%20%7Bbottom_half_probability%3A2.1%25%7D%0A%0A%20%20%20%20Probability%20of%20the%20middle%20card%20ending%20up%20in%20the%20bottom%20half%20of%20the%20deck%3A%20%7Bmiddle_half_probability%3A2.1%25%7D%0A%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20textwrap)%3A%0A%20%20%20%20mo.md(textwrap.dedent(r%22%22%22%0A%20%20%20%20%23%23%20Entropy%20of%20the%20shuffle%0A%0A%20%20%20%20Now%20each%20histogram%20of%20final%20card%20positions%20may%20be%20treated%20as%20a%20probability%20distribution.%20If%20a%20card%20in%20a%20particular%20position%20in%20the%20original%20deck%20is%20shuffled%20uniformly%20at%20random%20into%20every%20possible%20deck%20position%20by%20the%20shuffle%2C%20its%20probability%20distribution%20will%20be%20uniform%20and%20so%20it%20will%20have%20maximal%20entropy.%20If%20it's%20consistently%20shuffled%20into%20the%20same%20position%2C%20it%20will%20have%20minimum%20entropy.%0A%0A%20%20%20%20The%20entropy%2C%20%24S%24%2C%20when%20calculated%20using%20logarithm%20base%202%2C%20is%20measured%20in%20bits%20of%20information%2C%0A%0A%20%20%20%20%24%24S%20%3D%20%5Csum_i%20-p_i%20%5Clog_2(p_i)%24%24%0A%0A%20%20%20%20and%20so%20the%20entropy%20may%20be%20interpreted%20as%20the%20number%20of%20bits%20required%20to%20determine%20the%20card's%20final%20position%20in%20the%20deck%20after%20shuffling.%0A%20%20%20%20%22%22%22))%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(deck_size%3A%20int%2C%20log%2C%20position_distributions%3A%20%22NDArray%5Bnp.float64%5D%22)%3A%0A%20%20%20%20entropy_by_position%3A%20list%5Bfloat%5D%20%3D%20%5B0%20for%20_%20in%20range(deck_size)%5D%0A%20%20%20%20max_entropy%3A%20float%20%3D%20log(deck_size%2C%202)%0A%20%20%20%20for%20_i%20in%20range(deck_size)%3A%0A%20%20%20%20%20%20%20%20entropy_by_position%5B_i%5D%20%3D%20sum(%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20(0%20if%20probability%20%3D%3D%200%20else%20-probability%20*%20log(probability%2C%202))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20probability%20in%20position_distributions%5B_i%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20print(%22Maximum%20entropy%20%3D%20%7B%3A1.2%7D%20bits%22.format(max_entropy))%0A%20%20%20%20return%20entropy_by_position%2C%20max_entropy%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20The%20entropy%20of%20the%20final%20position%20distribution%20for%20each%20of%20the%20initial%20card%20positions%20is%20shown%20below.%20The%20cards%20near%20the%20middle%20of%20the%20deck%20all%20have%20nearly%20the%20maximum%20entropy%20of%205.7%20bits%20and%20so%20these%20cards%20are%20being%20shuffled%20well.%20Cards%20near%20the%20top%20and%20bottom%20begin%20to%20fall%20off%20down%20to%20a%20low%20of%205.3.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20alt%2C%0A%20%20%20%20chart_config%2C%0A%20%20%20%20chart_line_width%3A%20float%2C%0A%20%20%20%20entropy_by_position%3A%20list%5Bfloat%5D%2C%0A)%3A%0A%20%20%20%20_rows%3A%20list%5Bdict%5Bstr%2C%20float%20%7C%20int%5D%5D%20%3D%20%5B%0A%20%20%20%20%20%20%20%20%7B%22position%22%3A%20_position%2C%20%22entropy%22%3A%20_entropy%7D%0A%20%20%20%20%20%20%20%20for%20_position%2C%20_entropy%20in%20enumerate(entropy_by_position)%0A%20%20%20%20%5D%0A%0A%20%20%20%20chart_config(%0A%20%20%20%20%20%20%20%20alt.Chart(alt.Data(values%3D_rows))%0A%20%20%20%20%20%20%20%20.mark_line(strokeWidth%3Dchart_line_width)%0A%20%20%20%20%20%20%20%20.encode(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dalt.X(%22position%3AQ%22%2C%20title%3D%22Initial%20card%20position%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dalt.Y(%22entropy%3AQ%22%2C%20title%3D%22Entropy%20of%20shuffled%20position%2Fbits%22)%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20.properties(width%3D%22container%22%2C%20height%3D360)%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20textwrap)%3A%0A%20%20%20%20mo.md(textwrap.dedent(r%22%22%22%0A%20%20%20%20%23%23%20Trying%20some%20different%20shuffles%0A%0A%20%20%20%20After%20defining%20functions%20to%20do%20the%20shuffle%20testing%20and%20entropy%20calculation%2C%20any%20type%20of%20shuffle%20can%20be%20tested%20and%20their%20fairness%20can%20be%20compared%20using%20this%20entropy%20approach.%0A%20%20%20%20%22%22%22))%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Callable%2C%20NDArray%2C%20floor%2C%20log%2C%20np)%3A%0A%20%20%20%20def%20repeat_shuffle(%0A%20%20%20%20%20%20%20%20shuffle_function%3A%20Callable%5B%5BNDArray%5Bnp.integer%5D%5D%2C%20NDArray%5Bnp.integer%5D%5D%2C%0A%20%20%20%20%20%20%20%20num_shuffles%3A%20int%20%3D%2010000%2C%0A%20%20%20%20%20%20%20%20deck_size%3A%20int%20%3D%2052%2C%0A%20%20%20%20)%20-%3E%20NDArray%5Bnp.float64%5D%3A%0A%20%20%20%20%20%20%20%20deck_size%20%3D%20int(deck_size)%0A%20%20%20%20%20%20%20%20deck%3A%20NDArray%5Bnp.integer%5D%20%3D%20np.arange(deck_size)%0A%0A%20%20%20%20%20%20%20%20num_shuffles%20%3D%20int(num_shuffles)%0A%20%20%20%20%20%20%20%20shuffle_weight%3A%20float%20%3D%201%20%2F%20num_shuffles%0A%0A%20%20%20%20%20%20%20%20position_distributions%3A%20NDArray%5Bnp.float64%5D%20%3D%20np.zeros(%5Bdeck_size%2C%20deck_size%5D)%0A%0A%20%20%20%20%20%20%20%20for%20shuffle_index%20in%20range(num_shuffles)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20shuffle_index%20%25%20floor(num_shuffles%20%2F%202)%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print(%22Shuffling%20decks...%20%7B%3A.2%25%7D%22.format(shuffle_index%20%2F%20num_shuffles))%0A%20%20%20%20%20%20%20%20%20%20%20%20shuffled%3A%20NDArray%5Bnp.integer%5D%20%3D%20shuffle_function(deck)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20position%20in%20range(deck_size)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20position_distributions%5Bshuffled%5Bposition%5D%5D%5Bposition%5D%20%2B%3D%20shuffle_weight%0A%0A%20%20%20%20%20%20%20%20return%20position_distributions%0A%0A%20%20%20%20def%20entropy(distribution%3A%20NDArray%5Bnp.float64%5D)%20-%3E%20list%5Bfloat%5D%3A%0A%20%20%20%20%20%20%20%20deck_size%3A%20int%20%3D%20len(distribution)%0A%20%20%20%20%20%20%20%20entropy_by_position%3A%20list%5Bfloat%5D%20%3D%20%5B0%20for%20_%20in%20range(deck_size)%5D%0A%20%20%20%20%20%20%20%20for%20position%20in%20range(deck_size)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20entropy_by_position%5Bposition%5D%20%3D%20sum(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20(0%20if%20probability%20%3D%3D%200%20else%20-probability%20*%20log(probability%2C%202))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20probability%20in%20distribution%5Bposition%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20return%20entropy_by_position%0A%0A%20%20%20%20return%20entropy%2C%20repeat_shuffle%0A%0A%0A%40app.cell%0Adef%20_(Callable%2C%20NDArray%2C%20box%2C%20cut%2C%20entropy%2C%20log%2C%20np%2C%20repeat_shuffle%2C%20riffle)%3A%0A%20%20%20%20shuffles%3A%20list%5BCallable%5B%5BNDArray%5Bnp.integer%5D%5D%2C%20NDArray%5Bnp.integer%5D%5D%5D%20%3D%20%5B%0A%20%20%20%20%20%20%20%20lambda%20deck%3A%20riffle(riffle(box(riffle(cut(deck)))))%2C%0A%20%20%20%20%20%20%20%20lambda%20deck%3A%20cut(riffle(box(riffle(riffle(deck)))))%2C%0A%20%20%20%20%20%20%20%20lambda%20deck%3A%20cut(riffle(riffle(riffle(box(deck)))))%2C%0A%20%20%20%20%5D%0A%0A%20%20%20%20%23%20Simulate%20many%20shuffles%20and%20calculate%20the%20entropy%20of%20each%20one%0A%20%20%20%20distributions%3A%20list%5BNDArray%5Bnp.float64%5D%5D%20%3D%20%5B%0A%20%20%20%20%20%20%20%20repeat_shuffle(shuffle_function)%20for%20shuffle_function%20in%20shuffles%0A%20%20%20%20%5D%0A%20%20%20%20entropies%3A%20list%5Blist%5Bfloat%5D%5D%20%3D%20%5B%0A%20%20%20%20%20%20%20%20entropy(distribution)%20for%20distribution%20in%20distributions%0A%20%20%20%20%5D%0A%20%20%20%20max_entropies%3A%20list%5Bfloat%5D%20%3D%20%5B%0A%20%20%20%20%20%20%20%20log(len(distribution)%2C%202)%20for%20distribution%20in%20distributions%0A%20%20%20%20%5D%0A%20%20%20%20return%20distributions%2C%20entropies%2C%20max_entropies%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20alt%2C%0A%20%20%20%20chart_config%2C%0A%20%20%20%20chart_line_width%3A%20float%2C%0A%20%20%20%20distributions%3A%20%22list%5BNDArray%5Bnp.float64%5D%5D%22%2C%0A%20%20%20%20entropies%3A%20list%5Blist%5Bfloat%5D%5D%2C%0A%20%20%20%20inset_legend%2C%0A%20%20%20%20max_entropies%3A%20list%5Bfloat%5D%2C%0A%20%20%20%20max_entropy%3A%20float%2C%0A%20%20%20%20mo%2C%0A)%3A%0A%20%20%20%20_entropy_rows%3A%20list%5Bdict%5Bstr%2C%20float%20%7C%20int%20%7C%20str%5D%5D%20%3D%20%5B%5D%0A%20%20%20%20for%20shuffle_index%2C%20shuffle_entropy%20in%20enumerate(entropies)%3A%0A%20%20%20%20%20%20%20%20for%20_position%2C%20_entropy%20in%20enumerate(shuffle_entropy)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_entropy_rows.append(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22shuffle%22%3A%20%22Shuffle%20%7B%3A1%7D%22.format(shuffle_index)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22position%22%3A%20_position%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22entropy%22%3A%20_entropy%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20_entropy_chart%20%3D%20(%0A%20%20%20%20%20%20%20%20alt.Chart(alt.Data(values%3D_entropy_rows))%0A%20%20%20%20%20%20%20%20.mark_line(strokeWidth%3Dchart_line_width)%0A%20%20%20%20%20%20%20%20.encode(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dalt.X(%22position%3AQ%22%2C%20title%3D%22Card%20position%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dalt.Y(%22entropy%3AQ%22%2C%20title%3D%22Entropy%2Fbits%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20color%3Dalt.Color(%22shuffle%3AN%22%2C%20title%3DNone%2C%20legend%3Dinset_legend())%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20.properties(width%3D%22container%22%2C%20height%3D360)%0A%20%20%20%20)%0A%0A%20%20%20%20if%20not%20all(max_entropies%5B0%5D%20%3D%3D%20item%20for%20item%20in%20max_entropies)%3A%0A%20%20%20%20%20%20%20%20print(%22Invalid%20comparison%20-%20different%20max%20entropies%22)%0A%0A%20%20%20%20_max_entropy_line%20%3D%20(%0A%20%20%20%20%20%20%20%20alt.Chart(alt.Data(values%3D%5B%7B%22entropy%22%3A%20max_entropy%2C%20%22label%22%3A%20%22Max%22%7D%5D))%0A%20%20%20%20%20%20%20%20.mark_rule(strokeDash%3D%5B5%2C%205%5D%2C%20color%3D%22%23555%22%2C%20strokeWidth%3Dchart_line_width)%0A%20%20%20%20%20%20%20%20.encode(y%3D%22entropy%3AQ%22)%0A%20%20%20%20)%0A%0A%20%20%20%20example_start_positions%3A%20list%5Bint%5D%20%3D%20%5B0%2C%205%2C%2020%2C%2051%5D%0A%0A%20%20%20%20_example_charts%3A%20list%5Balt.Chart%20%7C%20alt.LayerChart%5D%20%3D%20%5B%5D%0A%20%20%20%20for%20start_position%20in%20example_start_positions%3A%0A%20%20%20%20%20%20%20%20_example_rows%3A%20list%5Bdict%5Bstr%2C%20float%20%7C%20int%20%7C%20str%5D%5D%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20shuffle_index%2C%20distribution%20in%20enumerate(distributions)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_position%2C%20_probability%20in%20enumerate(distribution%5Bstart_position%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_example_rows.append(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22shuffle%22%3A%20%22Shuffle%20%7B%3A1%7D%22.format(shuffle_index)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22position%22%3A%20_position%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22probability%22%3A%20_probability%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20_example_charts.append(%0A%20%20%20%20%20%20%20%20%20%20%20%20chart_config(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20alt.Chart(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20alt.Data(values%3D_example_rows)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20title%3D%22Card%20starting%20in%20position%20%7B%3A%7D%22.format(start_position)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20.mark_line(strokeWidth%3Dchart_line_width)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20.encode(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20x%3Dalt.X(%22position%3AQ%22%2C%20title%3D%22Card%20position%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20y%3Dalt.Y(%22probability%3AQ%22%2C%20title%3D%22Probability%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3Dalt.Color(%22shuffle%3AN%22%2C%20title%3DNone%2C%20legend%3Dinset_legend())%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20.properties(width%3D%22container%22%2C%20height%3D264)%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20mo.vstack(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20chart_config(_entropy_chart%20%2B%20_max_entropy_line)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.vstack(_example_charts%2C%20align%3D%22stretch%22)%2C%0A%20%20%20%20%20%20%20%20%5D%2C%0A%20%20%20%20%20%20%20%20align%3D%22stretch%22%2C%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A