わずかな食い違い

この画像は、大雨の後に撮影されたパティオのメッシュテーブルトップを示しています。 水滴がネットのいくつかの穴に残った。 これらのドロップの分布はどうですか？ それらは表面にランダムに散らばっていますか？ それらを配置した降雨のプロセスはかなりランダムに見えますが、私の意見では、グリッドに占有されている場所のパターンは不均一に単調に見えます。



分析を簡素化するために、テーブルトップのある写真の正方形部分（傘の穴を削除する）を選択し、この正方形内のすべての滴の座標を強調表示しました。 合計で394個のドロップがあり、青い点でマークしました。











繰り返しますが、このパターンはランダムプロセスの結果のように見えますか？



アメリカの科学者向けに 、シミュレートされたランダム性の2つのバージョン： pseudoとquasiを調査する記事を書いた後、この質問に出会いました。 擬似ランダム性の導入は不要です。 擬似ランダム平方選択アルゴリズムは、すべてのポイントが同じ選択確率を持ち、すべての選択が互いに独立していることを確認しようとします。 これは、メッシュワークトップに似た、斜めに回転したグリッドのメンバーシップで区切られた394個の擬似ランダムポイントの配列です。











準ランダム性はあまり知られていない概念です。 準ランダムポイントを選択するときの目標は、等確率または独立性ではなく、分布の均一性、つまり正方形の表面に沿ったポイントの最も均一な広がりです。 ただし、この目標をどのように達成するかはあまり明白ではありません。 以下に示す394個の準ランダムポイントの場合、 x座標は単純な算術級数を形成しますが、 y座標は数値を混合するプロセスによって変更されます。 （対応するアルゴリズムは、1930年代にオランダの数学者ヨハネス・ファン・デル・コープによって発明され、1950年代にクラウス・フリードリッヒ・ロスによって2次元に変換されました。 松下じり 。）











これらの点のセットのうち、 擬似または準のどちらが雨滴によりよくマッチしますか？ 3つのパターンすべてを簡約形式で比較できます。











各パターンには独自のテクスチャがあります。 擬似ランダムでは、集中したクラスターと大きなギャップがあります。 準ランダムポイントはより均等に配置されますが（いくつかの近接したポイントのペアがあります）、明確な小規模の繰り返しパターンも作成します。最も顕著なのは六角形構造であり、ほぼ結晶の均一性で繰り返されます。 液滴に関しては、それらはほぼ均一な密度で領域に分布しているように見えますが（これは準ランダムパターンに似ています）、テクスチャには格子構造ではなくベンドのヒントが含まれています（これは擬似ランダムの例のように見えます）。



「目で」パターンを研究する代わりに、その記述と分類に定量的なアプローチを試みることができます。 この目的のために、多くのツールがあります：動径分布関数、最近傍の統計、フーリエ法ですが、この問題を解決する主な理由は、主に準ランダム性を研究する過程で研究した新しいおもちゃで遊ぶ機会でした。 矛盾と呼ばれるこの品質（ およそTransl。：ロシア語で正しい用語を見つけることができなかったので、ご存じの場合はご連絡ください）は 、空間内の均一分布からの点集合の偏差を推定します。



発散の概念には多くのバリエーションがありますが、1つの測定スキームのみを検討します。 このアイデアは、さまざまな形状とサイズの長方形をパターンに重ね合わせ、その辺がx軸とy軸に平行になるようにすることです。 ドロップパターンに重ねられた長方形の3つの例を次に示します。











ここで、各長方形に囲まれたポイントの数を計算し、ポイントの分布が正方形全体で完全に均一だった場合、対応する領域で囲まれるべきポイントの数と比較します。 差の絶対値は不一致です $$$D（R）$ 長方形に関連付けられています $$$R$ ：

$$

$$D \左（R \右）= \左| N \ cdotエリア（R）-\＃\左（P \ cap R \右）\右|$$

どこで $$$N$ -ポイントの合計数、および $$$\＃\左（P \ cap R \右）$ -ポイント数 $$$P$ 長方形の中 $$$R$ 。 たとえば、左上隅の長方形は正方形の10％をカバーします。つまり、ポイントの「公正な」端数は0.1×394 = 39.4ポイントである必要があります。 実際、長方形には37ポイントしか含まれていません。つまり、長方形に関連付けられた不一致は| 39.4-37 | = 2.4。 長方形内のポイントの密度は、合計の平均よりも大きい場合も小さい場合もあります。 どちらの場合も、絶対値は正の不一致をもたらします。



パターン全体として、合計の不一致Dをその変化の最悪値、つまり言い換えると、正方形に重ねられたすべての可能な長方形に対して取られた最大の不一致を指定できます。 Van der Corputeは、任意の低い発散でポイントのセットを作成できるかどうか疑問に思いました。 $$$N$ 無限の傾向がある $$$D$ 常に一定の境界より下にありました。 答えは、少なくとも1次元または2次元ではありません。 最小成長率は $$$O \左（\ log N \右）$ 。 擬似ランダムパターンの分散は一般に高い $$$O \左（\ sqrt {N} \右）$ 。



与えられたポイントのセットに対して最大の発散を持つ長方形を見つける方法は？ 矛盾の定義を初めて読んだとき、問題の長方形の数が無限にあるため、それを計算することは絶対に不可能だと思いました。 しかし、熟考すると、矛盾を最大化できる候補矩形の有限セットしか存在しないことに気付きました。 これらは、4つの辺のそれぞれが少なくとも1つの点を通る長方形です。 （例外：候補長方形には、正方形の境界線上に辺がある場合もあります。）



次の長方形に出会ったと仮定します。











左側、上側、下側はポイントを通過しますが、右側は「空のスペース」にあります。 このような構成は、最大の発散を持つ長方形にすることはできません。 ポイントと交差するまで右端を左に移動できます。











この形状の変更により、長方形で囲まれたポイントの数を変更せずに長方形の面積が減少し、したがってポイントの密度が増加します。 エッジを反対側に移動することもできます。











ここで、囲まれたポイントの数を再度変更せずに面積を増やしました 。つまり、密度を下げました。 これらのアクションの少なくとも1つが増加します $$$D（R）$ 、初期構成と比較して。 したがって、四辺すべてが正方形のポイントまたはエッジに接する各長方形は、発散関数の極大値です。 この有限セット内のすべての長方形をリストすると、グローバルな最大値を見つけることができます。



別の迷惑な質問があります。長方形を「閉じた」（つまり、境界上の点が領域に含まれる）または「開いた」（境界上の点が除外される）と見なすべきかどうかです。 私はこのタスクを避け、閉じた境界と開いた境界の両方の結果を表に提示しました。 閉じた形式は、点の配置が密な長方形に最大の不一致を与え、開いた形式は、低密度の点での不一致を最大化します。



発散関数の極値のみを考慮して、計算問題を有限にしますが、それほど単純ではありません！ 四角とみなす必要がある長方形の数 $$$N$ ポイント（それぞれに異なる座標があります $$$x$ そして $$$y$ ）？ これは、単純な組み合わせの解決策を伴う非常に興味深い小さな問題であることが判明しました。 ここでは答えを説明しませんが、自分で処理できると思わない場合は、 OEISで見るか、 Benjamin、Quinn、Wurtzの短い記事を読むことができます。 私が言えることは、 N = 394の場合、長方形の数は6,055,174,225です-開いた長方形と閉じた長方形を別々に考慮すると2倍です。 長方形ごとに、394個のポイントのうちいくつが内側にあり、いくつが外側にあるかを調べる必要があります。 かなり大きな仕事。



計算コストを削減する1つの方法は、より単純な不一致の測定値に戻すことです。 2次元以上の準ランダムパターンに関するさまざまな文献では、「スターの不一致」またはD *と呼ばれる品質が使用されています。 アイデアは、正方形の左下隅に「取り付けられた」長方形のみを考慮することです（これは、 xy平面の原点と正常に一致します）。 この場合、長方形の数は合計に等しくなります $$$N ^ {2}$ 、またはN = 394の場合は約150,000。



雨滴パターンの全体的な発散星を定義する長方形は次のとおりです。











下部の濃い緑色の長方形は、正方形の約55％を覆い、完全に均等に分布した216.9ポイントを含む必要があります。 実際、238個のポイントが含まれています（「閉じた」長方形であると仮定）。つまり、差は21.1です。 コーナー（0,0）に結び付けられた他の長方形に大きな不一致はありません。 （注：グラフィック解像度の制限により、長方形D *は正方形の境界まで引き伸ばされているようです。実際、右端はx = 0.999395にあります。）



この結果は、雨滴のパターンの性質について何を教えていますか？ まあ、まず最初に、矛盾はかなり近いです $$$\ sqrt {N}$ （N = 394で19.8に等しい）と特に近くない $$$\ log N$ （自然対数の場合は6.0です）。 つまり、液滴パターンが擬似ランダムよりも準ランダムであることの確認は見つかりません。 上記の他のパタ​​ーンのD *値は、予想される範囲内にあります。擬似ランダムの場合は25.9、準ランダムの場合は4.4です。 外部印象とは反対に、雨滴の分布は、少なくともD *基準によれば、準ランダムな点よりも擬似的な点のセットのほうが共通点が多いようです。



Dの無限の発散の計算、つまり、固定された長方形D *だけでなく、 すべての長方形の調査についてはどうでしょうか？ 熟考すると、この場合、長方形の包括的な列挙は主な結論を変更できないと結論付けることができます。 Dが D *より小さくなることはありません。したがって、 $$$\ sqrt {N}$ に $$$\ log N$ 。 しかし、私はまだコンピューティングに興味がありました。 これらの60億の長方形のうち、どれが最大の不一致を持ちますか？ 勇敢な行為なしでこの質問に答えることは可能ですか？



Dの明白で単純なアルゴリズムは、すべての候補矩形を順番に生成し、それらの面積を測定し、内部のポイントをカウントし、プロセスで見つかった限界の不一致を追跡します。 このアルゴリズムを実装するプログラムは、数分で100の疑似ランダムまたは疑似ランダムポイント間の正確な不一致を判断できることがわかりました。 この結果は、 Nの大きな値を取得する動機付けになる可能性があります。 ただし、 Nが10増加するたびに実行時間はほぼ2倍になります。これは、 N = 394の場合、計算に数世紀かかることを示唆しています。



計算を高速化するために数日を費やしました。 実行時間のほとんどは、各長方形のポイントをカウントするプロシージャに費やされます。 特定のポイントが内側、外側、または境界上にあるかどうかを判断するには、8つの算術比較が必要です。 つまり、 N = 394の場合、60億個の長方形のそれぞれに対して3,000以上が実行されます。 私が発見した時間を節約する最も効果的な方法は、すべての比較の予備計算でした。 長方形の左下隅になる可能性のある各ポイントについて、上と右のパターン内のすべてのポイントのリストを事前に計算します。 長方形の潜在的な右上隅ごとに、下と左の同様のポイントのリストを収集します。 これらのリストは、角度座標でインデックス付けされたハッシュテーブルに格納されます。 各三角形について、2つのリストのセットの交差を取得するだけで、内部ポイントの数を計算できます。



このトリックのおかげで、 N = 394での予想リードタイムは2世紀から約2週間に短縮されました。 この優れた最適化により、さらなる改善に別の日を費やすことになりました。 ハッシュテーブルをN × N配列に置き換えると、状況が少し改善されました。 そして、最大のDを持つ可能性のある長方形にならない最小の三角形をすべて無視する方法を見つけました。これらの三角形にはポイントが少なすぎるか、面積が少なすぎるためです。 この改善により、最終的にリードタイムが一晩に短縮されました。 雨滴パターンの最大発散Dを持つ長方形を示す図を計算するのに6時間かかりました。











最大Dの長方形は、明らかに、同じ点のセットの長方形D *の小さな改良になりました。 長方形Dは204.3ポイントを「含む」必要がありますが、実際には229を含むため、 D = 24.7の不一致が生じます。 もちろん、正確な不一致が21.1ではなく24.7であることを知っていても、雨滴パターン自体の性質については何もわかりません。 実際、計算を行うたびに、学習する回数が減っていくようです。



このプロジェクトの作業を始めたとき、ドロップの分布を滑らかにするためにカウンタートップで何ができるのか、パターンを擬似ランダムよりも準擬似にするのかについて、独自の理論を持っていました。 そもそも、金属のグリッドではなく、ガラスの滑らかな表面にある滴について考えました。 2つの小さな液滴が接触するのに十分接近すると、それらは1つの大きな液滴に融合します。これは、この構成が表面張力に関連するエネルギーが少ないためです。 2つの隣接するメッシュセルが水で満たされていて、それらの間の金属が濡れている場合、水は1つのドロップから別のドロップに自由に流れることができます。 大きなドロップは小さなドロップのためにほぼ確実に成長し、後者は時間とともに消えます。 したがって、純粋にランダムな分布と比較して、隣接セルの液滴が不足することが予想されます。



そして、この考えはまだ私にとって非常に良いようです。 唯一の問題は、存在しない現象を説明することです。 不一致の計算がこれらの3つのパターンについて重要な何かを明らかにしたかどうかはわかりませんが、少なくとも測定値は、ドロップの分布が擬似ランダムの分布と異なることを証明できませんでした。 実際、パターンは異なって見えますが、そのような場合に感覚器官をどれだけ信頼できますか？ ドットをランダムに描くように人々に頼むと、ほとんどの人はドットをうまく作れません。通常、分布は滑らかすぎて均一になります。 おそらく、脳はランダム性を認識する際に同様の困難を経験します。



しかし、これらのパターンをより効果的に分離することを可能にする数学的特性があると思います。 他の誰かが検索に時間を費やすことに決めた場合、3つのポイントセットのxy座標はテキストファイルにあります 。



追加 ：これは簡単な推奨事項です。これまでに読んだことがある場合は、 コメントを読み続けてください。 彼らには多くの価値があります。 代わりの説明やアルゴリズムを提供し、私の分析の弱点を指摘してくれたすべての人々に感謝します。 themathsgeekに特に感謝します。themathsgeekは、差を計算するためのはるかに優れたプログラムを投稿してから40分後に書きました。 Iainにも感謝します。Iainは、実際の実験でランダムパターンの知覚に関する即興の推論をテストしました。